hackerrank new year chaos code optimization

Question

I'm trying to optimize my solution for Hackerranks's 'New Year Chaos' problem. The gist of the problem goes like this

There's a queue of n people, labeled 1 through n, and each person can bribe the person directly in front of them to swap places and get closer to the front of the queue (in this case, index 0 of the list/array). Each person can only bribe a maximum of two times (and they cannot bribe someone who has already bribed them)

You are given the order of the people after all of the bribes have taken place and your job is to determine how many bribes took place to get to that point. For example, if you were given [3, 2, 1] then the answer would be 3 bribes (person 3 bribed person 1, 2 and person 2 bribed person 1).

My solution was, for each person I, count the number of people to the left of I that have a label greater than I (they would've had to bribe person I to get to the left of them). To complicate things (slightly), some of the test cases given would only be possible if someone bribed more than 2 times (i.e. [4, 1, 2, 3] - person 4 bribed person 3, then 2, then 1 to get to the front). If this is the case, simply output "Too chaotic"

Anyway here's the code:

# n is the number of people in the list
# q is the order of the people after the bribery has taken place ex. [1, 3, 2, 5, 4]

for I in range(1, n + 1): # for each person I in the list
    index = q.index(I)
    if I - index > 3: # more than two bribes
        bribes = "Too chaotic"
        break
    for j in range(index): # for each number to the left of I, if greater than I, count it as a bribe
        if q[j] > I: 
            bribes = bribes + 1
print bribes

My problem is that the code times out with some of the larger test cases (you're only given so much time for each test case to run). How can I optimize the algorithm so that it doesn't time out? Should I be trying this problem in another language?

Answer 1

An optimization to your solution would be to start the nested loop from q[i] - 2 instead of 0. Since no one can jump ahead of its original position by more than 2, so any value higher than q[i] can only be till index q[i] -2.

Something like:

for(int j = Math.max(0, q[i] - 2); j < i; j++) {
    if(q[j] > q[i]) {
      bribe++;
    }
}

Answer 2

def minimumBribes(q):
    bribes = 0
    for i in range(len(q)-1,-1,-1):
        if q[i] - (i + 1) > 2:
            print('Too chaotic')
            return
        for j in range(max(0, q[i] - 2),i):
            if q[j] > q[i]:
                bribes+=1
    print(bribes)

Answer 3

The final optimization is in the inner loop, to exclude all those people who were never in a position to offer the current person a bribe.

You already halt this loop when you reach the current persons final position because obviously no-one behind their final position gave them a bribe...

But what about all those people in front? This person could, at best, get to two positions in front of where they started, by issuing two bribes. But no-one in front of that was ever in a position to offer them a bribe, so we can exclude everyone further forward.

Thus the inner loop ranges from two spots in front of my start position to my final position. Which chops out a lot of iterations when the list gets lengthy.

def minimumBribes(q):
    bribes = 0
    for final_pos, start_pos in enumerate(q):
        # Abort if anyone is more than two bribes ahead of where they started
        if  final_pos + 1 < start_pos - 2:
            print('Too chaotic')
            return
        # Count the number of people who started behind me, who are ahead of my
        # final position. Conduct the search between two spots forward of where
        # I started, thru to the person in front of me in the end; as these are
        # the only people to have potentially bribed me.
        potential_bribers = range(max(start_pos - 2, 0), final_pos)
        bribes += [q[briber] > start_pos for briber in potential_bribers].count(True)
    print(bribes)

I may be able to work these puzzles out, but never ever can I do it within their timeframes. Which is why I didn't even bother an attempt the last time a potential employer put a hacker rank test in front of me. They can have the braniacs, the rest us mere mortals have stackoverflow.

Answer 4

Just came across this problem, took me some time but here's a nice clean solution that is optimized for larger test cases (and passes 10/10 on HackerRank). I realise it takes a slightly different approach to yours but thought I'd share as it is working nicely and might still help.

A key point that helped me is that for any given person X in the queue, the furthest you'll need to look for a person that overtook them is 1 spot in front of where person X started. People can be overtaken more than 2 times, so for example, person 1 can end up at the back of the queue even if the queue is 1000 people long. However, person Y can't end up more than two places ahead of where they began (otherwise they must have overtaken more than twice). This is the reason you can be sure you don't need to look further than 1 place in front of where person X began (2 places in front of the nearest possible overtaker) for the people that overtook them.

def minimumBribes(q):

    count = 0
    tooChaotic = False

    for i in range(len(q)):

        # to translate between q[i] and the position in a zero-indexed python list, you have to add 1, so here it's i+3 rather than i+2

        if q[i] > i + 3:
            print("Too chaotic")
            tooChaotic = True
            break
        else:

            # q[i]-2 rather than q[i]-1 since python is zero-indexed but the people in the queue start at 1

            start = max(0, q[i]-2)
            for j in range(start, i):
                    if q[j] > q[i]:
                        count += 1

    if tooChaotic == False:
        print(count)