New Year Chaos (HackerRank problem) - find minimum swap count

Question

The goal of the function is to find and print the minimum number of swaps (bribes) in what was initially a sorted array of ints - https://www.hackerrank.com/challenges/new-year-chaos/problem

problem image

I have passed this problem with the following code:

def minimumBribes(q):
 bribeCount = 0
 simulated = list(range(1, len(q) + 1))
 for i in range(0, len(q)):
 if q[i] > i+3:
 print("Too chaotic")
 return
 for i in range(0, len(simulated)):
 if simulated[i] == q[i]:
 continue
 while(simulated[i] != q[i]):
 # do 2 bribes
 if i + 3 == q[i]:
 simulated[i + 2], simulated[i + 1] = simulated[i + 1], simulated[i + 2]
 simulated[i + 1], simulated[i] = simulated[i], simulated[i + 1]
 bribeCount += 2
 # do 1 bribe
 else:
 simulated[i + 1], simulated[i] = simulated[i], simulated[i + 1]
 bribeCount += 1
 print(bribeCount)

My approach was to first scan through the array to determine whether it is valid, as 1 person can only bribe (swap) twice, hence the first for loop. Then I go through each entry in my initial state array(simulated) and do swaps until the simulated entry at position i matches that in the final array at the same position.

I'm wondering if there is a better way to do this or whether something can be improved in my approach? I rarely do while loops like this as it seems it could go infinite, but I guess it's okay for this problem as we know only 2 swaps are possible for any entry.

Answer 1

Some minor stuff:

This if:

 if simulated[i] == q[i]:
 continue

is redundant and can be removed, due to the predicate on your while. The while would execute zero times and have the same effect as if you continued.

The while itself:

 while(simulated[i] != q[i]):

should drop the outer parens.

The range here:

for i in range(0, len(simulated)):

should drop the 0, because that's the default.

Since you use both i and simulated[i], you should iterate using enumerate instead of range (though this won't be the case if you delete the if; continue). Getting a value from enumerate won't be helpful during the value swaps that you do later.

About the value swaps, this block:

 if i + 3 == q[i]:
 simulated[i + 2], simulated[i + 1] = simulated[i + 1], simulated[i + 2]
 simulated[i + 1], simulated[i] = simulated[i], simulated[i + 1]
 bribeCount += 2
 # do 1 bribe
 else:
 simulated[i + 1], simulated[i] = simulated[i], simulated[i + 1]
 bribeCount += 1

should collapse to

 if i + 3 == q[i]:
 simulated[i + 2], simulated[i + 1] = simulated[i + 1], simulated[i + 2]
 bribeCount += 1
 simulated[i + 1], simulated[i] = simulated[i], simulated[i + 1]
 bribeCount += 1

• Dostrelith: Thanks for the feedback - I see all your points are valid, don't know how I missed some of those :)
• Kelly Bundy: After getting another variable with enumerate, how do you keep it in sync with simulated[i] throughout the changes? Rather seems inconvenient.
• Reinderien: @HeapOverflow enumerate only applies to the current state of the code, where there's a separate continue which would use the item from enumerate. If that's deleted, there's no advantage to enumerate.
• Kelly Bundy: I'd say it doesn't apply to the current state, either. Sure, it would make the condition in the if shorter, but then during the while you either have the inconvenience of keeping in sync or if you don't keep in sync, you have the confusion of that. Unless you del the variable between the if and the while, at which point I'd say it's worse than the current state that never created the extra variable in the first place.