Danke, Onkel (die Geschichte)

Mein leicht verrückter Onkel ist kürzlich in die Weltraumkolonien aufgebrochen und hat mir sein Palettenwarengeschäft übergeben. Das rechteckige Lager ist bis auf das eine Quadrat neben der Tür voll mit Warenpaletten, und ich habe gerade die erste Liste von Paletten erhalten, die von Kunden bestellt wurden und heute versandt werden sollen.

Glücklicherweise habe ich eine sorgfältig geschriebene Karte, wo sich jede Palette befindet, und mein verrückter Onkel hat mehrere Miniroboter konstruiert, die eine Palette in einen angrenzenden Raum bewegen können, ähnlich wie bei einem verschiebbaren 15-Puzzle. Es ist mir egal, wo die Paletten landen, ich möchte nur, dass die Paletten auf der Liste in der richtigen Reihenfolge an der Tür ankommen.

Die Frage ist, welche Befehlsreihe muss ich den Robotern geben, um die erforderlichen Paletten abzurufen?

Die Herausforderung

Gegeben

die Größe des Gitters (Zeilen, Spalten)
Eine Liste der Paletten (nach ihrem aktuellen Standort), die der Reihe nach abgerufen werden sollen

Sie müssen eine Liste von Rasterpositionen ausgeben, die der zu verschiebenden Position und der Richtung entsprechen. Wenn nur eine Richtung verfügbar ist, können Sie diese optional weglassen. Die Paletten werden sofort nach der Ankunft an der Tür entfernt (an einer Ecke Index N in den Beispielen).

Gearbeitetes Beispiel

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)

Grenzen und Freiheiten

Die maximale Rastergröße beträgt 100 x 100
Herausforderung ist Code-Golf
Die Lösung muss innerhalb von 2 Minuten auf einem realen Computer ausgeführt werden
Sie können Ihre Indizierung, Befehlssyntax, Eingabestrukturen usw. auswählen, sofern dies konsistent ist.
Ich habe mich dafür entschieden, die Rasterpositionen für die Befehle zu verwenden, aber möglicherweise können Sie stattdessen den Wert im Element (plus eine Richtung) ausgeben, da diese eindeutig sind.
Wenn Sie eine Animation des Staates machen wollten (besonders für ein großes Raster), wäre das sicher unterhaltsam!

Beispiele

A: 3x2, 1 Palette

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

C: 3x2, 4 Kartons

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 Kartons

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

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

F: 100x100, 3 in der Nähe der Tür

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

Sandbox-Link

code-golf sliding-puzzle Phil H.
quelle

Wenn die Felder 2 und 3 angefordert werden, ist es dann illegal, dass 3 an der Tür vorbeikommen, während Sie 2 in Richtung Tür bewegen?

Jonah

@ Jonah: Nein, oder keines der Szenarien wäre lösbar, wenn die erste Box nicht n-1 oder nc wäre. Das einzige Besondere an dem Raum an der Tür ist, dass die nächste Palette auf der Liste sofort von meinem exzentrischen Gabelstaplerfahrer entfernt wird, wenn sie dort ankommt.

Phil H

Sliding Retrieval