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.
Learning Python?
I mostly use Python throughout this blog as I find it to be a clean and intuitive language that is well-suited to HackerRank challenges.
If you're unfamiliar with Python (or just want to brush up), checkout Best Python Courses According to Data Analysis for course recommendations.
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:
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 bribeso = 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:
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 -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?
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?
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.
