there is a parking lot with only one empty spot given the initial state of the parking lot and the final state each step we are only allowed to move a car out of its place and move it into the empty spot the goal is to find out the least movement needed to rearrange the parking lot from the initial state to the final state say the initial state is an array 1 2 3 0 4 where 1 2 3 4 are different cars and 0 is the empty spot and the final state is 0 3 2 1 4 we can swap 1 with 0 in the initial array to get 0 2 3 1 4 and so on each step swap with 0 only edit now also prints the sequence of changes in states output of this example initial 1 2 3 0 4 final 0 3 2 1 4 steps 4 sequence 0 2 3 1 4 2 0 3 1 4 2 3 0 1 4 0 3 2 1 4 e g 4 0 2 3 1 4 2 0 3 1 4 2 3 0 1 4 0 3 2 1 4 thus 1 2 3 0 4 zero 3 true cartomove final3 1 pos initial index1 0 switched 0 3 0 2 3 1 4 zero 0 f initial1 final1 switched 0 1 2 0 3 1 4 zero 1 t cartomove final1 3 pos initial index3 2 switched 1 2 2 3 0 1 4 zero 2 t cartomove final2 2 pos initial index2 0 switched 0 2 0 3 2 1 4 initial final prevent changes in original initial list of each step in sequence if zero isn t where it should be what should be where zero is and where is it e g 4 0 2 3 1 4 2 0 3 1 4 2 3 0 1 4 0 3 2 1 4 thus 1 2 3 0 4 zero 3 true car_to_move final 3 1 pos initial index 1 0 switched 0 3 0 2 3 1 4 zero 0 f initial 1 final 1 switched 0 1 2 0 3 1 4 zero 1 t car_to_move final 1 3 pos initial index 3 2 switched 1 2 2 3 0 1 4 zero 2 t car_to_move final 2 2 pos initial index 2 0 switched 0 2 0 3 2 1 4 initial final
def garage(initial, final):

    initial = initial[::]      
    seq = []                   
    steps = 0
    while initial != final:
        zero = initial.index(0)
        if zero != final.index(0):  
            car_to_move = final[zero]   
            pos = initial.index(car_to_move)         
            initial[zero], initial[pos] = initial[pos], initial[zero]
        else:
            for i in range(len(initial)):
                if initial[i] != final[i]:
                    initial[zero], initial[i] = initial[i], initial[zero]
                    break
        seq.append(initial[::])
        steps += 1

    return steps, seq