# 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,

1. 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;
2. 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} -> {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 -> 0
2, 2 -> 6
5, 7 -> 2
1, 1 -> 7
6, 5 -> 1
3, 3 -> 5
1, 7 -> 3

• (majorly is quite different from mainly or essentially.) Dec 4, 2016 at 19:17
• @greybeard, you mean different? Confused. Dec 6, 2016 at 2:48
• I had to look up majorly: seems to see most use in informal American English, with an interpretation of to a high degree (from very to extremely). Merriam-Webster was the one source I encountered listing first what I presume you intend: primarily - to go on to join the pack in the Defined for English Language Learners section. Dec 6, 2016 at 3:31
• @greybeard, thanks, changed to mainly to reduce any confusions. If you have any thoughts on my original question, it will be great. :) Dec 6, 2016 at 6:10

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)

• Thanks Guillaume for the code and vote up. I think input.index(car_id) time complexity is O(n) for look-up index for a value, while a dictionary look-up is O(1), so my method is more efficient? Dec 8, 2016 at 5:04
• BTW, your overall coding style is much better than mine, love it and learning. My only question for your code is above comment. :) Dec 8, 2016 at 5:07
• True about the dict lookup being faster (O(1)) , but for a 8 elements list that doesn't matter much. Dec 8, 2016 at 6:16
• Thanks for all the help Guillaume, mark your reply as answer and grant bounty points. Dec 11, 2016 at 5:03