6
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ (majorly is quite different from mainly or essentially.) \$\endgroup\$
    – greybeard
    Dec 4, 2016 at 19:17
  • \$\begingroup\$ @greybeard, you mean different? Confused. \$\endgroup\$
    – Lin Ma
    Dec 6, 2016 at 2:48
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – greybeard
    Dec 6, 2016 at 3:31
  • \$\begingroup\$ @greybeard, thanks, changed to mainly to reduce any confusions. If you have any thoughts on my original question, it will be great. :) \$\endgroup\$
    – Lin Ma
    Dec 6, 2016 at 6:10

1 Answer 1

3
+50
\$\begingroup\$

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)
\$\endgroup\$
4
  • \$\begingroup\$ 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? \$\endgroup\$
    – Lin Ma
    Dec 8, 2016 at 5:04
  • \$\begingroup\$ BTW, your overall coding style is much better than mine, love it and learning. My only question for your code is above comment. :) \$\endgroup\$
    – Lin Ma
    Dec 8, 2016 at 5:07
  • 1
    \$\begingroup\$ True about the dict lookup being faster (O(1)) , but for a 8 elements list that doesn't matter much. \$\endgroup\$
    – Guillaume
    Dec 8, 2016 at 6:16
  • \$\begingroup\$ Thanks for all the help Guillaume, mark your reply as answer and grant bounty points. \$\endgroup\$
    – Lin Ma
    Dec 11, 2016 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.