Solution to HackerRank's New Year Chaos in Python

Full solution and animated visualization for this medium difficulty array challenge.

I've been going through some HackerRank challenges recently and figured I'd take a few of the more interesting challenges and do a full code breakdown with an animated visualization.

Though there are often several possible solutions to most HackerRank challenges, I'll try and choose the most elegant and optimized solutions for code/visualization breakdowns.

HackerRank: New Year Chaos challenge

Difficulty: medium

Description:

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 1from 1at the front of the line to nat 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:

1021325344657687

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!

Sample input and output:

sample input

2
5
2 1 5 3 4
5
2 5 1 3 4
Out:

output

3
Too chaotic

Animated solution

Important

Notice that HackerRank chose to have the origin index start at 1 (e.g., 1,2,3). We adjust the queue index to 0 for teaching purposes. Check the optional final solution variant at the bottom of this article for the version that doesn't include this extra loop.

Code breakdown

First initialize our bribes counter:

solution

def minimum_bribes(q):
    bribes = 0
    q = [i-1 for i in q]
    for i, o in enumerate(q):
        cur = i

        if o - cur > 2:
            print("Too chaotic")
            return
        
        for k in q[max(o - 1, 0):i]:
            if k > o:
                bribes += 1

    print(bribes)
    

Next, we enumerate through the main array.

i = Person's current position after bribes
o = Person's original position before any bribes took place

solution

def minimum_bribes(q):
    bribes = 0
    q = [i-1 for i in q]
    for i, o in enumerate(q):
        cur = i

        if o - cur > 2:
            print("Too chaotic")
            return
        
        for k in q[max(o - 1, 0):i]:
            if k > o:
                bribes += 1

    print(bribes)
    

Next, we can check if a Person has bribed someone else more than 2 times.

If the origin position - current position is greater than 2, we know this Person has given bribes more than 2 times. If a person gives a bribe to someone else, the briber always moves forward one step, so the furthest they could ever move forward would be 2 steps from their place of origin before returning the "Too chaotic" message.

solution

def minimum_bribes(q):
    bribes = 0
    q = [i-1 for i in q]
    for i, o in enumerate(q):
        cur = i

        if o - cur > 2:
            print("Too chaotic")
            return
        
        for k in q[max(o - 1, 0):i]:
            if k > o:
                bribes += 1

    print(bribes)
    

Too Chaotic example:

30011223

In this case Person 3 had to bribe 2,1 and 0 to get from position 3 to position 0.

Finally, we need to loop between origin position -1 and current position.

Each person who bribed the current person swaps places with that person.

Example:

Original positions: John(0), Sally(1), Tom(2), Jim(3)

  1. Sally (1) bribes John (0)
  2. Tom (2) bribes John (0) and then Sally(1)
  3. Jim (3) bribes John (0) then Sally (1)

Final positions: Tom(2), Jim(3), Sally(1), John(0)

Sally (1) ended at position 3. If we check each position between Sally's new position (3) and her origin position -1 (1-1=0) we can see every bribe she has taken.
o = 1 : Sally's origin position pre-bribes

i = 2 : Sally's current position post-bribes

So we check queue [ o-1 : i ]. If we look above that means when we're on Sally, we'll check placements 0 and 1, therefore finding that Sally took Bribes from both Jim and John.

solution

def minimum_bribes(q):
    bribes = 0
    q = [i-1 for i in q]
    for i, o in enumerate(q):
        cur = i

        if o - cur > 2:
            print("Too chaotic")
            return
        
        for k in q[max(o - 1, 0):i]:
            if k > o:
                bribes += 1

    print(bribes)
    

Let's break it down a little further

Remember we only care about who received a bribe, who gave the bribe is irrelevant to this part of our algorithm.

This means that if Sally takes a bribe from Tom, Tom swaps with her to her origin position. Now Tom can give someone else 1 more bribe, this would put him at -1 position from Sally's origin point. In order to be able to count Tom's bribe, we have to check back -1 placement from her origin. There is no way a briber can go further than -1 place from the bribee's origin point unless they give out more than 2 bribes (remember, greater than 2 bribes is too chaotic).

If the challenge allowed a max of 3 bribes instead of 2 before chaos then we would have to check -2from the bribee's origin, max of 4 would be -3, etc.

Here are a couple of example snapshots to help illustrate:

Was number 3 bribed?

20311203

In this scenario, cur_pos is at Jim (3). We check in the range [ max(3-1,0) : 1 ]. Only Tom (2) is in range and he didn't bribe Jim because his origin position (2) is less than Jim's (3).

Was number 1 bribed?

20311203

In this scenario, cur_pos is at Sally (1 ) who's currently at position 2. We check in range [max(1-1,0):2]. Both Tom (2) and Jim (3) bribed Sally as their queue numbers are higher than Sally (1).

Full solution:

*As noted at the top, remember to adjust for hackerrank's origin index starting at 1 instead of 0.

solution

def minimum_bribes(q):
    bribes = 0
    q = [i-1 for i in q]
    for i, o in enumerate(q):
        cur = i

        if o - cur > 2:
            print("Too chaotic")
            return
        
        for k in q[max(o - 1, 0):i]:
            if k > o:
                bribes += 1

    print(bribes)

Multiple solutions

There are multiple ways of solving this problem but I found the above solution both elegant and fast. You will lose points on this challenge for slow (e.g., O(n2)) solutions.

Code without extra off-by-one loop

without_extra_loop

def minimum_bribes(q):
    bribes = 0

    for i, o in enumerate(q):
        cur = i + 1

        if o - cur > 2:
            print("Too chaotic")
            return
        
        for k in q[max(o - 2, 0):i]:
            if k > o:
                bribes += 1

    print(bribes)

Hopefully this helps to understand how to solve the New Year Chaos problem in an optimized and elegant way.

Author:

*no spam, just fresh content