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

user_13134749 0
Viewed 56

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?

while-loop python-3.x python
1 Answers

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]]))
user_144920010
Related