Algorithm to park cars with minimal moves (2nd version) I'm working on a car move problem. Suppose we have origin parking position for each car, [-1,1,2,3,7,6,4,5] (which means first position is empty, car with ID 1 parked at 2nd position, car with ID 2 parked at 3rd position), we want to find the minimal move to re-park car as specific desired positions. For example specific desired position [4,6,5,1,7,3,2,-1] means car with ID 4 parked at first position, car with ID 6 parked as 2nd position, etc. -1 means empty parking lot to utilize.

My 2nd version of code is based on the great thought and implementation from Joe (Algorithm to park cars with minimal moves), since it is new code, I make a new post other than changing the original post.

Here is my code, my major idea for what I think Joe's code needs some change,


Each time we move car a from position x to position y, we just make a move, we are not swap, which is first point I change Joe's code. I change (move) position of car a to position y and then update position y to empty;
Based on logic of 1st item, I think we should check for output[index] != empty, other than check for output[index] != input[index] to end of internal while loop.


My code mainly based on Joe's code,

def car_move_v2(input, output, empty=0):
    # print move from position a to positive b
    def print_move(a, b):
        input[b] = input[a]
        input[a] = empty
        position[input[a]] = a
        position[input[b]] = b
        print('{0}, {1} -&gt; {2}'.format(input[b], a, b))
    position = {
        pos: index
        for index, pos in enumerate(input)
    }
    for start in range(len(input)):
        if input[start] == output[start]:
            continue
        if input[start] != empty:
            print_move(start, position[empty])
        index = start
        while output[index] != empty:
            prev_index = index
            index = position[output[prev_index]]
            print_move(index, prev_index)
    return

if __name__ == "__main__":
    car_move_v2([-1,1,2,3,7,6,4,5], [4,6,5,1,7,3,2,-1],-1)


Output,

4, 6 -&gt; 0
2, 2 -&gt; 6
5, 7 -&gt; 2
1, 1 -&gt; 7
6, 5 -&gt; 1
3, 3 -&gt; 5
1, 7 -&gt; 3
Why do you need a separate position dict, that you have to maintain whenever you move a car ? You can just use input.index(car_id) anytime you need to get a car position.
Also your print_move() function is almost useless, since it just swaps 2 positions, one of which is assumed to be empty. That could be written in a single line. 

Here are my proposed improvements, with an modified move() that takes the car id to move and the target free slot, and returns the new freed slot:

def car_move_v2(initial_slots, target_slots, EMPTY=None):
    current_slots = initial_slots # will use as working slots
    def move(car, free_slot):
        "move car to free_slot, returns the newly freed slot"
        assert current_slots[free_slot] == EMPTY, "Slot {0} is not free".format(free_slot)
        car_slot = current_slots.index(car)
        current_slots[free_slot], current_slots[car_slot] = current_slots[car_slot], EMPTY
        print('car {0} moved from {1} to {2}, {3}'.format(car, car_slot, free_slot, current_slots))
        return car_slot

    for slot, (current_car, target_car) in enumerate(zip(current_slots, target_slots)):
        if current_car == target_car: # if car is already in target position, do not move
            continue
        elif current_car != EMPTY: # if there is an unwanted car in the slot, move it to the empty slot
            free_slot = move(current_car, current_slots.index(EMPTY))
        else:
            free_slot = slot
        # at this point we have a free slot to work with
        while target_slots[free_slot] != EMPTY:
            other_target_car = target_slots[free_slot]
            free_slot = move(other_target_car, free_slot) # move that car to the current free pos


if __name__ == "__main__":
    car_move_v2(initial_slots=[None,1,2,3,7,6,4,5], target_slots=[4,6,5,1,7,3,2,None], EMPTY=None)