Thanks, Uncle (the story)
My slightly mad uncle recently left for the space colonies, and passed his pallet goods business to me. The rectangular warehouse is full of pallets of goods except for the one square by the door, and I've just received the first list of pallets ordered by customers to be sent out today.
Fortunately I have a carefully written map of where each pallet is, and my mad uncle engineered several mini robots which can move a pallet into an adjacent space, much like a sliding 15-puzzle. I don't care where the pallets end up, though, I just want the pallets on the list to arrive in order by the door.
The question is, what series of commands must I give the robots in order to retrieve the required pallets?
- the size of the grid (rows, cols)
- a list of pallets (by their current location) to retrieve in order
You must output a list of grid positions corresponding to which position is to be moved, and which direction. If there is only 1 direction available you may optionally omit that. The pallets will be removed immediately upon arrival by the door (at one corner, index N in the examples).
01 02 label the contents A B 03 04 C D 05[ ] E _ Request: 03 (contents is C) Command 0: 04 D moves into the (only) adjacent space at index 06 Result: A B C _ E D Command 1: 03 C moves into the (only) adjacent space at index 04 Result: A B _ C E D Command 2: 05 A B E C _ D Command 3: 06 A B E C D _ Command 4: 04 A B E _ D[C] (C removed having arrived by the door)
Limits and freedoms
- Maximum grid size is 100x100
- Challenge is code-golf
- Solution must execute within 2 minutes on some real-world machine
- You can choose your indexing, command syntax, input structures and so on, as long as it's consistent.
- I've chosen to use the grid locations for the commands, but conceivably you could emit the value in the element instead (plus a direction) as they are unique.
- If you wanted to make an animation of the state (especially for a large grid), I'm sure that would be entertaining!
A: 3x2, 1 pallet
01 02 03 04 05 [__] Request: pallet at 03 Valid solution: 05,03,04,06,05 This leaves the following state: 01 02 04 05 __ 
B: 15-puzzle, 1 box
01 02 03 04 05 06 07 08 09 10 11 12 13 14[ ] Request: box 01 Valid solution: 14,13,12,11,06,01,02,07,12,11,06,07,12,11,06,07,08,13,12,11,06,07,08,09,14,13,08,09,10,15,14 02 07 03 04 05 08 12 13 10 14 06 11 09 __
C: 3x2, 4 boxes
01 02 03 04 05[ ] Request: 02,04,01,05 Valid solution: 04,02,01,03,05,06,04,05,02,06,03S,05E Pallet taken at: ^ ^ ^ ^ Indicating directions with NSEW Final state: 03 __ __ __ __ __
D: 10x10, 2 boxes
10x10, request boxes at 13,12 (row 1, cols 2 & 1 with 0-index) Valid solution: (90,80..20, 19,18..12, 22,32..92, 93,94..100) x 15, 90.
E: 4x1, all
4x1: 01 02 03 [ ] Req: 03,02,01 (only valid order) Optimal solution: 03,02,03E,01,02E,03E
F: 100x100, 3 near the door
100x100 Req: 9900,9899,9898 Result: 9000,9989,9000S,9898,9898E,9000S