3 Approaches to Solving the New Year Chaos Logic Problem

In my spare time, I’ve endeavored to solve algorithmic problems.

Such tasks are common in engineering interviews. To be clear, Revelry usually foregoes testing of this type (I agree), and how often I have to solve such problems, day-to-day, is debatable. And yet, I find intrinsic value in exercising such muscles. I enjoy the challenge of solving logic problems.

The latest upon which I happened is New Year Chaos, whereof one variation can be found here.

The Logic Problem: New Year Chaos

HackerRank summarizes the challenge as an example of solving logic problems:

It’s New Year’s Day and everyone’s in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by 1 from 1 at the front of the line to n at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n = 8 and Person 5 bribes Person 4, the queue will look like this: 1, 2, 3, 5, 4, 6, 7, 8.

Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

Three Approaches to Solving

In the vein of Eric Elliott (who was quoting Ken Beck), I shall summarize what amounted to three approaches:

• The wrong way;
• The concise way; and
• The fast way.

To me, the prompt seemed not too difficult. I quickly roughed out a solution. My code passed all the preliminary test cases, and I felt content that I had arrived upon an answer.

First Attempt (i.e., The Wrong Way)

Here’s the code I wrote for solving logic problems like this below:

defmodule NewYearChaos.Incorrect do
  @doc """
  Collection contains at least one briber?

  Provided a list, returns a boolean, indicating whether the first
  element precedes any other elements of higher value.
  """
  def briber?([first | rest]) do
    Enum.any?(rest, &(first > &1))
  end

  @doc """
  Calculate bribes.

  Provided a collection with a briber (i.e., `first`) at its head,
  calculate the offset of said briber from its initial position in the
  queue.
  """
  def calculate_bribes([first | _rest] = coll, index) do
    if briber?(coll), do: abs(index - first), else: 0
  end

  @doc """
  Get minimum bribes.

  Provided a queue of venal individuals, calculate the minimum number
  of bribes required to achieve the state of the queue.

  Our first clause is our ingress. Provided a list, initialize our
  algorithm with a one-based index and a variable of `total_bribes` at
  `0`.

  Our second clause is the egress. Once we reach the end of our list,
  denoted by `[]`, return `total_bribes`.

  Our final clause is the crux. For each item in our queue, calculate
  the number of times such an individual bribed others (i.e.,
  `current_bribes`). In cases where `current_bribes` exceeds `2`,
  return `Too chaotic`. In all other cases, add `current_bribes` to
  our accumulator.
  """
  def get_minimum_bribes(list), do: get_minimum_bribes(list, 1, 0)
  def get_minimum_bribes([], _index, total_bribes), do: total_bribes

  def get_minimum_bribes([_first | rest] = coll, index, total_bribes) do
    current_bribes = calculate_bribes(coll, index)

    if current_bribes > 2 do
      "Too chaotic"
    else
      total_bribes = total_bribes + current_bribes
      get_minimum_bribes(rest, index + 1, total_bribes)
    end
  end
end

And here are the test cases, of which all passed:

describe "NewYearChaos.Incorrect.get_minimum_bribes/1" do
  test """
  returns `Too chaotic` when collection requires that one person bribe
  more than two people
  """ do
    [2, 5, 1, 3, 4]
    |> Incorrect.get_minimum_bribes()
    |> Kernel.==("Too chaotic")
    |> assert()

    [5, 1, 2, 3, 7, 8, 6, 4]
    |> Incorrect.get_minimum_bribes()
    |> Kernel.==("Too chaotic")
    |> assert()
  end

  test "returns the correct number of minimum bribes" do
    [2, 1, 5, 3, 4]
    |> Incorrect.get_minimum_bribes()
    |> Kernel.==(3)
    |> assert()

    [1, 2, 5, 3, 7, 8, 6, 4]
    |> Incorrect.get_minimum_bribes()
    |> Kernel.==(7)
    |> assert()

    [1, 2, 5, 3, 4, 7, 8, 6]
    |> Incorrect.get_minimum_bribes()
    |> Kernel.==(4)
    |> assert()
  end
end

But there was something critically awry with the solution. I learned as much when I diversified the inputs I fed to my algorithm. Let’s examine a queue that is only slightly more complicated.

[3, 2, 1]

For such a case, my first-pass falls short. get_minimum_bribes/1 will return 2, which proves incorrect.

To illustrate why, observe the queue alongside a one-based index:

[3, 2, 1] # The queue
[1, 2, 3] # A one-based index

Should we employ an index-based strategy, as I do above, we would note that:

• 3, a briber, is offset from its index by 2; but
• 2, also a briber, is not offset from its one-based index.

Our function totals 2 bribes when it should return 3. How might we know as much?

When in doubt, examine, once more, the data. Such an endeavor often feels colorless, yet ultimately proves useful.

[3, 2, 1] # The queue
[1, 2, 3] # A one-based index

When we calculate bribes, it should be clear that:

• 3 bribed 2 and 1; and
• 2 bribed 1.

We should total 3 bribes.

Is it not apparent, then, why my index-based strategy fails?

It does not account for cases in which an individual, having received bribes, should be further back in the queue. Because there is no offset between 2 and its index, our first approach would deem such an individual honest (i.e., 2 aligns with its index) when the said person is, in fact, quite corrupt.

The Second Attempt (i.e., The Concise Way)

Let’s revise my original algorithm. We’ll use an approach that approximates our reasoning in evaluating the outlying case above.

defmodule NewYearChaos.Concise do
  @moduledoc """
  Solves the `New Year Chaos` prompt.

  N.B.: For clarity, our algorithm does not account for the case in
  which the queue is too chaotic.
  """

  @doc """
  Get minimum bribes.

  Provided a queue of venal individuals, calculate the minimum number
  of bribes required to achieve the state of the queue.

  Our first clause is our ingress. Provided a list, reverse it --
  which will enable us to pattern-match our arguments later.
  Initialize the number of `total_bribes` at `0`.

  Our second clause is our egress. Once we reach the end of our list,
  denoted by `[]`, return `total_bribes`.

  Our final clause is the crux. For every item in our queue, examine
  all items that precede it. For each item that exceeds our current
  item, increment our accumulator. Use recursion to iterate through
  the rest of the queue.
  """
  def get_minimum_bribes(list) do
    list |> Enum.reverse() |> get_minimum_bribes(0)
  end

  def get_minimum_bribes([], total_bribes) do
    total_bribes
  end

  def get_minimum_bribes([first | rest], total_bribes) do
    current_bribes =
      Enum.reduce(rest, total_bribes, &if(&1 > first, do: &2 + 1, else: &2))

    get_minimum_bribes(rest, current_bribes)
  end
end

Unlike our former algorithm, which would fail, our new solution should check out:

defmodule NewYearChaos.Concise.Test do
  use Algorithms.DataCase
  alias NewYearChaos.Concise

  describe "NewYearChaos.Concise.get_minimum_bribes/1" do
    test "returns the correct number of minimum bribes" do
      [3, 2, 1]
      |> Concise.get_minimum_bribes()
      |> Kernel.==(3)
      |> assert()
    end
  end
end

Alas, it will not prove robust.

I encountered exceptions when subjecting the algorithm to any considerable stress. When I passed it a queue of 100 thousand integers, I occasioned a timeout error after sixty seconds. It was vital to improve the algorithm’s efficiency.

Such a task would not prove easy. And I set out on many erroneous coding paths, fraught with complexity. But with patience and a little luck, I began asking some fruitful questions.

Final Attempt (i.e., The Fast Way)

Rather than enumerate through our list, and perform thorough calculations for every number, what if we took our corrupt queue and restored its integrity? What if we shepherded all these venal individuals back to their original positions? And what if, while doing so, we tallied the bribes used by our dishonest patrons?

A couple items become clear.

So much of the work we do to repair the queue to order involves the swapping of persons. And when you’ve swapped enough positions in your head, you may happen upon a looming familiarity. And that familiarity may originate from exercises in bubble sort.

The variation upon which I settled tracks an accumulator, summing the total times in which the algorithm performs a swap.

Here’s the crux of the operation, which proves quite performant.

defmodule NewYearChaos.Fast do
  defp apply_bubble_sort([first, next | rest], accum) when first > next do
    {rest, accum} = apply_bubble_sort([first | rest], accum + 1)
    {[next | rest], accum}
  end

  defp apply_bubble_sort([first, next | rest], accum) do
    {rest, accum} = apply_bubble_sort([next | rest], accum)
    {[first | rest], accum}
  end

  defp apply_bubble_sort(list, accum) do
    {list, accum}
  end

  def bubble_sort(list, accum) when is_list(list) do
    {sorted_list, accum} = apply_bubble_sort(list, accum)
    if sorted_list == list, do: accum, else: bubble_sort(sorted_list, accum)
  end
end

When operating on a queue of 100,000 numbers, we average an execution time of 0.04 seconds.

Finally, you will notice that I have omitted a special case that we must handle: whenever we provide a queue in which some person has bribed more than two people, we should return an output of "Too chaotic".

If we wanted to, we could venture to accommodate this case inside our bubble_sort/2 function. But I would prefer not to. I like the purity of our bubble_sort/2 algorithm. It does one thing well — and nothing more. Why obfuscate its purpose by embedding other calculations? Except for serious performance implications (and from what I can tell, there are none), I would prefer to allocate such handling to its own function — one with its own unique purpose. Let’s try that.

@doc """
Too chaotic?

Provided a list, determine whether any one person has bribed more than
2 people. Uses an index to ensure no person is more than two places
ahead.
"""
def too_chaotic?([]), do: false

def too_chaotic?([{first, index} | rest]) do
  if first - index > 2, do: true, else: too_chaotic?(rest)
end

def too_chaotic?([first | _rest] = coll) when is_integer(first) do
  coll |> Enum.with_index(1) |> too_chaotic?()
end

Our primary function, which integrates our work, should resemble:

def get_minimum_bribes(list, accum) do
  if too_chaotic?(list), do: "Too chaotic", else: bubble_sort(list, accum)
end

Conclusion

In this article, I set out to solve the New Year Chaos prompt using Elixir. My endeavors culminated in three distinct approaches. The first was patently incorrect. It employed an index-based tactic that fell short in certain cases. The second strategy, which combined Enum.reduce/3 with recursion, proved functional and concise — but it lacked vigor. Finally, I settled upon a familiar algorithm (i.e., bubble sort) that is comparatively swift. After solving the crux of the problem, I illustrated separately a means by which we can return an alternate output of "Too chaotic". Hopefully you enjoyed my 3 approaches for solving logic problems, now go solve some of your own! 

---

Code Elixir Problem Solving