5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback - I see all your points are valid, don't know how I missed some of those :) \$\endgroup\$ – Damjan Ostrelic Oct 17 at 21:20
  • \$\begingroup\$ After getting another variable with enumerate, how do you keep it in sync with simulated[i] throughout the changes? Rather seems inconvenient. \$\endgroup\$ – Heap Overflow Oct 17 at 22:45
  • \$\begingroup\$ @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. \$\endgroup\$ – Reinderien Oct 17 at 22:51
  • \$\begingroup\$ 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. \$\endgroup\$ – Heap Overflow Oct 17 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.