Obrigado, tio (a história)

Meu tio levemente louco recentemente partiu para as colônias espaciais e passou o negócio de artigos de paletes para mim. O armazém retangular está cheio de paletes de mercadorias, exceto um quadrado ao lado da porta, e acabei de receber a primeira lista de paletes encomendadas pelos clientes a serem enviadas hoje.

Felizmente, tenho um mapa cuidadosamente escrito de onde está cada palete, e meu tio louco projetou vários mini robôs que podem mover um palete para um espaço adjacente, como um quebra-cabeça deslizante de 15 peças. Eu não me importo onde os paletes acabam, só quero que os paletes da lista cheguem em ordem pela porta.

A questão é: que série de comandos devo dar aos robôs para recuperar os paletes necessários?

O desafio

Dado

o tamanho da grade (linhas, colunas)
uma lista de paletes (por sua localização atual) para recuperar em ordem

Você deve exibir uma lista de posições de grade correspondentes a qual posição deve ser movida e qual direção. Se houver apenas 1 direção disponível, você pode omitir isso opcionalmente. Os paletes serão removidos imediatamente após a chegada pela porta (em um canto, índice N nos exemplos).

Exemplo trabalhado

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)

Limites e liberdades

O tamanho máximo da grade é 100x100
Desafio é código-golfe
A solução deve ser executada em 2 minutos em alguma máquina do mundo real
Você pode escolher sua indexação, sintaxe de comando, estruturas de entrada e assim por diante, desde que consistente.
Eu escolhi usar os locais da grade para os comandos, mas é possível que você possa emitir o valor no elemento (mais uma direção), pois eles são únicos.
Se você quisesse fazer uma animação do estado (especialmente para uma grade grande), tenho certeza que seria divertido!

Exemplos

A: 3x2, 1 palete

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 quebra-cabeças, 1 caixa

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 caixas

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 caixas

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

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

F: 100x100, 3 perto da porta

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

Link sandbox

code-golf sliding-puzzle Phil H
fonte

se as caixas 2 e 3 forem solicitadas, é ilegal que 3 passem pela porta enquanto você move 2 em direção à porta?

Jonah

@ Jonah: Não, ou nenhum dos cenários seria solucionável, a menos que a primeira caixa fosse n-1 ou nc. A única coisa especial sobre o espaço ao lado da porta é que, quando o próximo palete da lista chegar lá, ele será imediatamente removido pelo meu operador de empilhadeira excêntrico.

Phil H

Recuperação deslizante