Gracias tío (la historia)

Mi tío un poco loco se fue recientemente a las colonias espaciales y me pasó su negocio de paletas. El almacén rectangular está lleno de paletas de productos, excepto el cuadrado de la puerta, y acabo de recibir la primera lista de paletas ordenadas por los clientes que se enviarán hoy.

Afortunadamente, tengo un mapa cuidadosamente escrito de dónde está cada paleta, y mi tío loco diseñó varios mini robots que pueden mover una paleta a un espacio adyacente, como un rompecabezas deslizante de 15. Sin embargo, no me importa dónde terminen las paletas, solo quiero que las paletas de la lista lleguen en orden a la puerta.

La pregunta es, ¿qué serie de comandos debo dar a los robots para recuperar las paletas requeridas?

El reto

Dado

El tamaño de la cuadrícula (filas, columnas)
Una lista de paletas (por su ubicación actual) para recuperar en orden

Debe generar una lista de posiciones de cuadrícula correspondientes a qué posición se va a mover y en qué dirección. Si solo hay 1 dirección disponible, opcionalmente puede omitir eso. Los palets se retirarán inmediatamente al llegar a la puerta (en una esquina, índice N en los ejemplos).

Ejemplo trabajado

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)

Límites y libertades

El tamaño máximo de la cuadrícula es 100x100
El desafío es el código golf
La solución debe ejecutarse en 2 minutos en una máquina del mundo real
Puede elegir su indexación, sintaxis de comandos, estructuras de entrada, etc., siempre que sea coherente.
Elegí usar las ubicaciones de la cuadrícula para los comandos, pero posiblemente podría emitir el valor en el elemento en su lugar (más una dirección) ya que son únicos.
Si quisieras hacer una animación del estado (especialmente para una cuadrícula grande), ¡estoy seguro de que sería entretenido!

Ejemplos

A: 3x2, 1 paleta

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
__ [03]

B: 15 rompecabezas, 1 caja

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 __[01]

C: 3x2, 4 cajas

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 cajas

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

4x1: 01 02 03 [ ]
Req: 03,02,01 (only valid order)
Optimal solution: 03,02,03E,01,02E,03E

F: 100x100, 3 cerca de la puerta

100x100
Req: 9900,9899,9898
Result: 9000,9989,9000S,9898,9898E,9000S

Enlace de caja de arena

code-golf sliding-puzzle Phil H
fuente

Si se solicitan las casillas 2 y 3, ¿es ilegal que 3 pasen por la puerta mientras se mueven 2 hacia la puerta?

Jonás

@ Jonás: No, o ninguno de los escenarios sería solucionable a menos que el primer cuadro fuera n-1 o nc. Lo único especial sobre el espacio junto a la puerta es que cuando llega el siguiente palé de la lista, mi operador excéntrico de montacargas lo quita de inmediato.

Phil H

Recuperación deslizante