Algorithm to park cars with minimal moves
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:

&gt;&gt;&gt; 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:

&gt;&gt;&gt; car_move([-1,1,2,3,-1,4,5,6,-1], [-1,2,3,1,-1,5,6,4,-1])
1, 1 -&gt; 8
2, 2 -&gt; 1
3, 3 -&gt; 2
1, 8 -&gt; 3
4, 5 -&gt; 8
5, 6 -&gt; 5
6, 7 -&gt; 6
4, 8 -&gt; 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} -&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:
            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.