CODEWITHSUNDEEP
pythonarraysalgorithmsorting
Ash
Ash

Reputation: 387

Unexpected behavior of python code while solving a hackerranks problem called Lily's Homework

Link to the problem: https://www.hackerrank.com/challenges/lilys-homework/forum

Summary: We have to find the minimum no. of swaps required to convert an array into sorted array. It can be sorted in ascending or descending order. So, here is the array I want to sort: 

arr = [3, 4, 2, 5, 1]

We sort it in ascending order we need 4 swaps, and 2 swaps when in descending order.

For descending: -Swap 5 and 3 and then swap 3 and 2

Now, I have written a python code to solve this test case. Here is the code:

arr = [3, 4, 2, 5, 1]
arr2 = arr[:]

count = 0; count2 = 0; n = len(arr)

registry = {}
for i in range(n):
    registry[arr[i]] = i

sorted_arr = sorted(arr)


#######################first for loop starts#########################
#find no. of swap required when we sort arr is in ascending order.
for i in range(n-1):

    if arr[i] != sorted_arr[i]:        
        index = registry[sorted_arr[i]]

        registry[sorted_arr[i]],registry[arr[i]]= i, index
        temp = arr[i]
        arr[i],arr[index]=sorted_arr[i],temp

        count = count + 1    
###################first for loop ends#######################

# re-initalising registry and sorted_arr for descending problem.
registry = {}
for i in range(n):
    registry[arr2[i]] = i

sorted_arr = sorted(arr2)
sorted_arr.reverse()

print(arr2)             #unsorted array
print(registry)         #dictionary which stores the index of the array arr2
print(sorted_arr)       #array in descending order.


#find no. of swap required when array is in descending order.
for i in range(n-1):
    print('For iteration i = %i' %i)
    if arr2[i] != sorted_arr[i]:
        print('\tTrue')
        index = registry[sorted_arr[i]]

        registry[sorted_arr[i]],registry[arr[i]]= i, index
        temp = arr2[i]
        arr2[i],arr2[index]=sorted_arr[i],temp

        print('\t '+ str(arr2))
        count2 = count2 + 1

    else:
        print('\tfalse')
        print('\t '+ str(arr2))



print('######Result######')
print(arr)
print(count)

print(arr2)
print(count2)

Here's the problem: When I run the code, the second for loop i.e. the for loop for descending gives wrong value of count which is 3. But, when I comment the first for loop, i.e. the for loop for ascending it gives correct value of count which is 2.

I want to know why for loop 2 changes output when for loop 1 is present.

The output I get when loop 1 is NOT commented.

arr2: [3, 4, 2, 5, 1]
Registry: {3: 0, 4: 1, 2: 2, 5: 3, 1: 4}
sorted_arr: [5, 4, 3, 2, 1]
For iteration i = 0
    True
     [5, 4, 2, 3, 1]
For iteration i = 1
    false
     [5, 4, 2, 3, 1]
For iteration i = 2
    True
     [2, 4, 3, 3, 1]
For iteration i = 3
    True
     [2, 4, 3, 2, 1]
######Result######
[1, 2, 3, 4, 5]
4
[2, 4, 3, 2, 1]
3

Upvotes: 1

Views: 94

Answers (1)

trincot
trincot

Reputation: 350147

The error is in your second loop, where you have:

registry[sorted_arr[i]],registry[arr[i]]= i, index

This should be:

registry[sorted_arr[i]],registry[arr2[i]]= i, index

Generally, it is a bad idea to work with such arr and arr2 variables. Instead make two functions, and pass arr as argument to the function call. The function should then make a local copy of that array ( [:]) before mutating it. All other variables should be local to the function. That way the two algorithms use their own variable scope and there is no risk of "leaking" accidently a wrong variable into the other algorithm.

Upvotes: 2

Related Questions