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_positionto 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) flags[new_pos] = True new_pos = car_new_position[original_positions[new_pos]] result.append(move_chain) print result if __name__ == "__main__": carMove([-1,1,2,3,7,6,4,5], [4,6,5,1,7,3,2,-1])
[set([0, 2, 6, 7]), set([1, 3, 5]), set()]