Ggthjy

My code given below will produce the correct output but it tends to take way too much time with larger data thus timing out for some of the test cases. I've linked to the problem description here:

It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride!

There are n people queued up, and each person wears a sticker indicating their initial position in the queue (i.e. 1, 2, ..., n - 1, n: with the first number denoting the frontmost position).

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 place in line. One person can bribe at most two other persons.

That is to say, if n = 8 and Person 5 bribes Person 4, the queue will look like this:
1, 2, 3, 5, 4, 6, 7, 8.

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!

Note: Each Person X wears sticker X, meaning they were initially the X^th person in queue.

Input Format

The first line contains an integer, T, denoting the number of test cases.
Each test case is comprised of two lines; the first line has n (an integer indicating the number of people in the queue), and the second line has n space-separated integers describing the final state of the queue.

Constraints

$$ 1 leq T leq 10 $$
$$ 1 leq n leq 10^5 $$

Subtasks

For 60% score $$1 leq n leq 10^3$$
For 100% score $$1 leq n leq 10^5$$

Output Format

Print an integer denoting the minimum number of bribes needed to get the queue into its final state; print Too chaotic if the state is invalid (requires Person X to bribe more than 2 people).

Sample Input

2

5

2 1 5 3 4

5

2 5 1 3 4

Sample Output

3

Too chaotic

Any help/advice/suggestion is welcome.

#!/bin/python3



import sys



inp0 = sys.stdin.read()

inp1 = inp0.split('n')

T = int(inp1[0])

del inp1[0]



# Swaps the i'th and (i-1)'th elements and returns the list

def swap(intermediate_q,i):

    intermediate_q[i],intermediate_q[i-1] = intermediate_q[i-1],intermediate_q[i]

    return(intermediate_q)



# Increment bribes and total_bribes 

def compute_bribes(bribes,total_bribes):

    if(bribes+1==3):

        return (-1,-1)

    return (bribes+1,total_bribes+1)



for i in range(0,(2*T)-1,2):

    n = int(inp1[i])

    final_q = list(int(i) for i in inp1[i+1].split(' '))

    initial_q = list(i+1 for i in range(n))

    total_bribes,chaos_flag=0,0

    for i in range(n):

        bribes = 0

        # If the position in the initial/transition queue is not equal to the position in the final queue

        # final_q is the input against which swaps are made in my initial_q. 

        if(final_q.index(initial_q[i]) != initial_q.index(initial_q[i])):

            index_in_initial_q = initial_q.index(final_q[i])

            index_in_final_q = final_q.index(final_q[i])

            while(index_in_initial_q != index_in_final_q):

                initial_q = swap(initial_q,index_in_initial_q)

                bribes,total_bribes = compute_bribes(bribes,total_bribes)

                if(bribes == -1):

                    print("Too chaotic")

                    chaos_flag=1

                    break

                index_in_initial_q-=1

        if(chaos_flag == 1):

            break

    if (chaos_flag == 1):

        continue

    print(total_bribes)

Code organisation

You've tried to split your logic into smallish functions which is a good idea but you could go further. You should try to write a function that handles the input/output part and a function which takes a well defined input (with the most relevant data types as an argument) and computes whatever needs to be computed before returning it (such a function should not do any input parsing or print anything except for debug purposes).

In you case, the most logical input such a function would take is the queue. The corresponding data type would be a list of int and the return type would be an integer (or None).

If you do so, you have smaller independant logical parts which are easier to understand, to maintain and to tests. Among other things, you can write unit tests based on the examples provided to ensure the computation works well.

In you case, moving the different pieces of logic around, you get something like:

#!/bin/python3



import sys



# Swaps the i'th and (i-1)'th elements and returns the list

def swap(intermediate_q,i):

    intermediate_q[i],intermediate_q[i-1] = intermediate_q[i-1],intermediate_q[i]

    return(intermediate_q)



# Increment bribes and total_bribes 

def compute_bribes(bribes,total_bribes):

    if(bribes+1==3):

        return (-1,-1)

    return (bribes+1,total_bribes+1)



def get_number_brides(queue):

    """Take a queue (list of int) as a parameter and return the number of brides or None."""

    n = len(queue)

    initial_q = list(i+1 for i in range(n))

    total_bribes = 0

    for i in range(n):

        bribes = 0

        # If the position in the initial/transition queue is not equal to the position in the final queue

        # queue is the input against which swaps are made in my initial_q. 

        if(queue.index(initial_q[i]) != initial_q.index(initial_q[i])):

            index_in_initial_q = initial_q.index(queue[i])

            index_in_queue = queue.index(queue[i])

            while(index_in_initial_q != index_in_queue):

                initial_q = swap(initial_q,index_in_initial_q)

                bribes,total_bribes = compute_bribes(bribes,total_bribes)

                if(bribes == -1):

                    return None

                index_in_initial_q-=1

    return total_bribes



def test_stdio():

    inp0 = sys.stdin.read()

    inp1 = inp0.split('n')

    T = int(inp1[0])

    del inp1[0]

    print("inp1", inp1)

    for i, val in enumerate(inp1):

        if i % 2 == 1:

            ret = get_number_brides([int(v) for v in val.split(' ')])

            print('Too chaotic' if ret is None else ret)



def unit_tests():

    assert get_number_brides([2, 1, 5, 3, 4]) == 3

    assert get_number_brides([2, 5, 1, 3, 4]) is None



if __name__ == "__main__":

    unit_tests()

    # test_stdio()

Among the nice benefits, because the function is now used for a single test case, I can return directly from the most relevant place and this is no need for a chaos_flag anymore (if you were to keep such a flag, it'd be a good idea to use the Boolean type).

Style

Python has a Style Guide called PEP 8 which is definitly worth having a look at and following. In your case, the spacing (both vertical and horizontal) is not quite perfect and so is the usage of useless parenthesis.

Fixing this, you get:

#!/bin/python3



import sys





# Swaps the i'th and (i-1)'th elements and returns the list

def swap(intermediate_q, i):

    intermediate_q[i], intermediate_q[i-1] = intermediate_q[i-1], intermediate_q[i]

    return(intermediate_q)





# Increment bribes and total_bribes

def compute_bribes(bribes, total_bribes):

    if bribes + 1 == 3:

        return (-1, -1)

    return (bribes + 1, total_bribes + 1)





def get_number_brides(queue):

    """Take a queue (list of int) as a parameter and return the number of brides or None."""

    n = len(queue)

    initial_q = list(i + 1 for i in range(n))

    total_bribes = 0

    chaos_flag = False

    for i in range(n):

        bribes = 0

        # If the position in the initial/transition queue is not equal to the position in the final queue

        # queue is the input against which swaps are made in my initial_q.

        if queue.index(initial_q[i]) != initial_q.index(initial_q[i]):

            index_in_initial_q = initial_q.index(queue[i])

            index_in_queue = queue.index(queue[i])

            while index_in_initial_q != index_in_queue:

                initial_q = swap(initial_q, index_in_initial_q)

                bribes, total_bribes = compute_bribes(bribes, total_bribes)

                if bribes == -1:

                    return None

                index_in_initial_q -= 1

    return total_bribes





def test_stdio():

    inp0 = sys.stdin.read()

    inp1 = inp0.split('n')

    T = int(inp1[0])

    del inp1[0]

    print("inp1", inp1)

    for i, val in enumerate(inp1):

        if i % 2 == 1:

            ret = get_number_brides([int(v) for v in val.split(' ')])

            print('Too chaotic' if ret is None else ret)





def unit_tests():

    assert get_number_brides([2, 1, 5, 3, 4]) == 3

    assert get_number_brides([2, 5, 1, 3, 4]) is None



if __name__ == "__main__":

    unit_tests()

    # test_stdio()

I have no time to go any further but I hope this will help you, another reviewer and future me to take over.

Python3

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)