# 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* `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:*

*0*2

*1*3

*2*5

*3*4

*4*6

*5*7

*6*8

*7*

*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:

## 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:

*0*0

*1*1

*2*2

*3*

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)

- Sally (1) bribes John (0)
- Tom (2) bribes John (0) and then Sally(1)
- 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* *-2**from 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?

*0*3

*1*1

*2*0

*3*

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?

*0*3

*1*1

*2*0

*3*

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.*

#### 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

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