Algorithm to park cars with minimal moves

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.

Here is my code, my major idea is to find a parking chain (cycle), and move the chain together, for example, in my above example,

• Find a chain (cycle): car 1 move to position of car 3, car 3 move to position of car 6, car 6 move to position of car 1, etc.

• Leverage empty slot to move the chain, in above example, I move car 6 to empty slot, then move car 3 to car 6 position, then move car 1 to car 3 position, finally move car 6 back from empty slot to car 1 position.

Have two questions on my code,

• I use a dictionary car_new_position to facilitate look-up for car ID and new position, is it good or any smarter ideas to not using the dictionary and achieve the same algorithm time complexity?

• I treat empty slot the same as car (with ID -1) in the algorithm, not sure if I treat this way correctly, or I should treat empty slot in some different way?

```
from collections import defaultdict

def carMove(original_positions, new_positions):

car_new_position = defaultdict(int) # build a dictionary to map car to new position
for i in range(len(new_positions)):
car_new_position[new_positions[i]]=i
result=[]
flags=[False]*len(original_positions)
for i in range(len(original_positions)):
if not flags[i]:
move_chain=set()
move_chain.add(i)
flags[i] = True
new_pos = car_new_position[original_positions[i]]
while new_pos not in move_chain:
move_chain.add(new_pos)

Ways you can improve your current code:

• Follow PEP8, it builds consistency. Your assignments have either a space either side or no spaces. Pick one style, preferably the one with a single space either side.

• You can use enumerate if you need to loop through both indexes and values of a list.

• You can remove one level of indentation by inverting your if check, if flags[i] and using continue.

• You can move the move_chain.add(i) and car_new_position[original_positions[i]] into the while loop.

This is by using new_pos = i, without adding it to the move_chain.

• If you don't follow (4), rather than using move_chain = set(); move_chain.add(i) use move_chain = {i}.

• You can move the logic for setting flags to true out of the while loop.

I prefer this as it's not needed to make the while loop work,
and so makes the code less complex.

• Don't print rather than return from a function.

• Changing your flags to a set can remove some code. I prefer sets, but it's probably slower.

def car_move(original_positions, new_positions):
    car_new_position = defaultdict(int)
    for i, pos in enumerate(new_positions):
        car_new_position[pos] = i
    result = []
    flags = set()
    for i in range(len(original_positions)):
        if i in flags:
            continue
        move_chain, new_pos = set(), i
        while new_pos not in move_chain:
            move_chain.add(new_pos)
            new_pos = car_new_position[original_positions[new_pos]]
        flags |= move_chain
        result.append(move_chain)
    print result

But what does your output even mean?
Take:

>>> carMove([-1,1,2,3,-1,4,5,6,-1], [-1,2,3,1,-1,5,6,4,-1])
[set([0, 8]), set([1, 2, 3]), set([8, 4]), set([5, 6, 7])]

What does this mean?
Do I have to move the cars ten times?
Do I need to notice that the set([0, 8]) is two empty car slots?
Why does the cycle 1, 2, 3 not have any empty car slots?
The output is unintuitive.

Instead, using the same idea of moving cycles you can make intuitive output.
By actually moving the cars.

Take the following:

>>> car_move([-1,1,2,3,-1,4,5,6,-1], [-1,2,3,1,-1,5,6,4,-1])
1, 1 -> 8
2, 2 -> 1
3, 3 -> 2
1, 8 -> 3
4, 5 -> 8
5, 6 -> 5
6, 7 -> 6
4, 8 -> 7
8

Sure it prints the moves, rather than returning them. But it's much simpler to understand.
Car1 moves from the first index to the eighth one. Car2 second index to first.
And there is a total of eight moves.

To make this you can:

-
Remove move_chain and flags, as we'll use other things.
This should get you something like:

def car_move(input, output):
    position = dict()
    for i, pos in enumerate(output):
        position[pos] = i
    for i in range(len(input)):
        if i in ...:
            continue
        new_pos = i
        while new_pos not in ...:
            new_pos = position[input[new_pos]]
    print result

-
Fix the conditions:

• If the input and output value are the same, we'll skip that position.

• While the input and output of the index are not the same.

• Add a previous index and a current index to the while loop.

-
Add a swap function and call it in the while loop.

This function will swap the inputs, update the positions and print the swap.

-
We'll add a check to see if i's value is empty, if not swap it with an empty one.
Otherwise we may be swapping cars, not moving them to empty spaces.

And so should get you:

def car_move(input, output, empty=0):
    swaps = 0
    def swap(a, b):
        nonlocal swaps
        swaps += 1
        input[a], input[b] = input[b], input[a]
        position[input[a]] = a
        position[input[b]] = b
        #print(input)
        print('{0}, {1} -> {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:
            swap(start, position[empty])
        index = start
        while output[index] != input[index]:
            prev_index = index
            index = position[output[prev_index]]
            swap(index, prev_index)
    return swaps

This is better as it finds the swaps, and adds a blank swap if needed.
It can also be changed quite easily to return an array of swaps, rather than print swaps and output the amount.
The biggest down side to my code is it requires nonlocal, a Python 3 only keyword, to increase the amount of swaps in the swap function.
But if you change it to output the actual swaps, then this is not needed.
As you can mutate a list in another scope. And would work in both Python 2 and Python 3.

StackExchange Code Review Q#145174, answer score: 3