How can I reduce the execution time of the given Python code?

Question

The question statement here is:

We have a list of animals in which i-th animal contains 4 items(index, a, b, and c). Initially, animal 0 is king, while everyone else queues up with animal 1 at the front of the queue and animal n−1 at the back. The animal at the front of the queue will challenge the king to a fight, and the animal with greater strength will win the fight. The winner will become king, while the loser joins the back of the queue.

An animal who wins 3 times consecutively will be crowned ruler for the whole zoo. The strength of each animal depends on how many consecutive fights he won. Animal i has strength a with 0 consecutive win, b with 1 consecutive win, and c with 2 consecutive wins. Initially, everyone has 0 consecutive win.

For all animals, a>b and c>b. Also, the values of a, b, c are distinct (all 3n values are pairwise different).

The function that I have created works, but there is an issue with the time complexity of the function.

Function:

def competition(arr):
fights = 0
wins = 1
strength_k = arr[0][1]
while wins != 4:
    king = 0
    strength_k = arr[0][wins]
    challenger = 1
    strength_c = arr[1][1]
    if strength_k > strength_c:
        wins += 1
        arr.append(arr[1])
        arr.pop(1)
    else:
        wins = 2
        arr.append(arr[0])
        arr.pop(0)
    fights += 1
    if fights >= 3 and arr[0][0] == 0:
        if arr[1][0] == 1:
            return "-1 -1"
return f"{arr[0][0]} {fights}"

, where arr will look like:

[[0, 5, 1, 2], [1, 10, 8, 11], [2, 9, 0, 3], [3, 7, 4, 6]]

The function will return the new king index along with the number of fights taken.

Sample output for this specific arr will be "-1 -1" as the animals will fight infinitely without any result.

Note:

I think there is an issue with my termination, where I terminate the loop(for no result) when the king is again 0 and the challenger is 1.

Can anyone help me in decreasing the time complexity of the same?

It seems to me this question is more suited to be asked in the Code Review Forum. Code Review is a question and answer site for peer programmer code reviews. — itprorh66
– itprorh66, Commented Mar 4, 2021 at 16:56
@Purusharth Malik If the animal loses, does its strength reset? As in, does its strength return back to a or it remains on the last strength he reached before losing? — Omar AlSuwaidi
– Omar AlSuwaidi, Commented Mar 4, 2021 at 17:26
@OmarAlSuwaidi On losing, the strength of the animal resets to A and it is sent back to the end of the queue. — Purusharth Malik
– Purusharth Malik, Commented Mar 4, 2021 at 17:30
@Purusharth Malik Are you sure that when the animal loses its strength resets to a regardless of its previous wins? Because in this case, the loop will run infinitely without a winner for your given array. — Omar AlSuwaidi
– Omar AlSuwaidi, Commented Mar 4, 2021 at 18:38
Yes @OmarAlSuwaidi, for the given array, the answer is supposed to be "-1 -1" i.e there will be no winner. I just can't seem to figure out the condition for which I will deem a case as infinitely running. — Purusharth Malik
– Purusharth Malik, Commented Mar 4, 2021 at 18:50

Omar AlSuwaidi · Accepted Answer · 2021-03-04 19:56:58Z

Check the comments in the code for brief explanations:

def competition(arr):
    str_k = 1  # Start by comparing strength "a"
    fights = 0
    winners = []
    while True:
        j = 1
        while arr[0][str_k] >= arr[j][1]:
            fights += 1
            winners.append(arr[0][str_k])
            str_k += 1  # Increment strength everytime animal wins
            j += 1  # Fight the next animal
            if str_k > 3:  # 3 consecutive wins = King
                return f"King of the zoo: {arr[0][0]} with {fights} fights"
        fights += 1
        if arr[j][1] in winners:  # If the winner animal has already won before and was NOT crowned king and won AGAIN, then we are repeating the cycle thus terminate
            return "-1 -1"
        winners.append(arr[j][1])
        str_k = 2  # Start from strength "b" since it already won once
        temp = arr[0]
        arr[0] = arr.pop(j)  # Put winner animal in front
        arr.append(temp)  # Send losing animal to the back


print(competition([[0, 5, 1, 2], [1, 10, 8, 11], [2, 9, 0, 3], [3, 7, 4, 6]]))

Collectives™ on Stack Overflow

How can I reduce the execution time of the given Python code?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related