Das Leben ist ein Labyrinth: Wir gehen den falschen Weg, bevor wir laufen lernen

30

Eingang:

Ein Labyrinth mit den Zeichen:

  • -- (horizontale Wand);
  • | (vertikale Wand);
  • + (Verbindung);
  • (Gehfläche);
  • I (Eingang);
  • U (Ausfahrt).

Dh eine Eingabe könnte so aussehen:

 +--+--+--+--+--+--+--+--+--+--+ 
I               |     |        | 
 +  +--+--+--+  +  +  +  +--+  + 
 |           |     |  |  |     | 
 +--+--+--+  +--+--+  +  +  +--+ 
 |           |     |     |     | 
 +  +--+--+  +  +--+--+  +--+  + 
 |     |     |     |     |     | 
 +--+  +  +--+--+  +--+--+  +  + 
 |     |        |        |  |  | 
 +  +--+--+--+  +--+--+  +  +  + 
 |     |     |     |        |  | 
 +--+  +  +--+--+  +--+--+--+--+ 
 |  |  |                 |     | 
 +  +  +--+--+--+  +--+  +  +  + 
 |     |        |  |  |  |  |  | 
 +--+--+  +  +--+  +  +  +--+  + 
 |        |     |     |  |     | 
 +  +--+--+--+  +  +  +  +  +--+ 
 |           |     |  |         U
 +--+--+--+--+--+--+--+--+--+--+

Ausgabe:

Der effizienteste Weg vom Eingang zu bekommen , um den Ausgang des Labyrinths (durch das Labyrinth), angedeutet durch die Zeichen anzeigt , links, rechts, oben und unten gehen sollte (dh >; <; ^; v).

Herausforderungsregeln:

  • Sie können die Eingabe in jedem vernünftigen Format vornehmen. String-Array, Single-String mit Zeilenumbrüchen, 2D-Char-Array usw. sind mögliche Eingabeformate.
  • Die Ausgabe kann aus vier verschiedenen Zeichen bestehen. Das heißt ><^v; →←↑↓; ⇒⇐⇑⇓; RLUD; 0123; ABCD; etc.).
  • Sie können Leerzeichen oder Zeilenumbrüche in die Ausgabe einfügen, wenn Sie dies bevorzugen. Dies ist optional.
  • Die Schritte werden pro Quadrat gezählt (siehe vier +Symbole für die Quadrate) und nicht pro Zeichen.
  • Das Labyrinth kann eine Größe von 5 x 5 bis 15 x 15 haben und wird immer ein Quadrat sein (es gibt also keine Testfälle für 5 x 10 Labyrinthe).
  • Sie können davon ausgehen, dass jedes Labyrinth von Anfang bis Ende einen oder mehrere gültige Pfade hat, und Sie geben immer den kürzesten aus (siehe Testfälle 4 und 5).
  • Wenn es mehrere Pfade mit derselben Länge gibt, können Sie auswählen, welche ausgegeben werden sollen (siehe Testfall 6).
  • Sie können die Grenzen des Labyrinths nicht überschreiten (siehe Testfälle 7 und 8).

Allgemeine Regeln:

  • Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.
    Lassen Sie sich von Code-Golf-Sprachen nicht davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, für jede Programmiersprache eine möglichst kurze Antwort zu finden.
  • Für Ihre Antwort gelten Standardregeln. Daher dürfen Sie STDIN / STDOUT, Funktionen / Methode mit den richtigen Parametern und vollständige Programme verwenden. Ihr Anruf.
  • Standardlücken sind verboten.
  • Fügen Sie nach Möglichkeit einen Link mit einem Test für Ihren Code hinzu.
  • Fügen Sie ggf. auch eine Erklärung hinzu.

Testfälle:

1. Input:
 +--+--+--+--+--+--+--+--+--+--+ 
I               |     |        | 
 +  +--+--+--+  +  +  +  +--+  + 
 |           |     |  |  |     | 
 +--+--+--+  +--+--+  +  +  +--+ 
 |           |     |     |     | 
 +  +--+--+  +  +--+--+  +--+  + 
 |     |     |     |     |     | 
 +--+  +  +--+--+  +--+--+  +  + 
 |     |        |        |  |  | 
 +  +--+--+--+  +--+--+  +  +  + 
 |     |     |     |        |  | 
 +--+  +  +--+--+  +--+--+--+--+ 
 |  |  |                 |     | 
 +  +  +--+--+--+  +--+  +  +  + 
 |     |        |  |  |  |  |  | 
 +--+--+  +  +--+  +  +  +--+  + 
 |        |     |     |  |     | 
 +  +--+--+--+  +  +  +  +  +--+ 
 |           |     |  |         U
 +--+--+--+--+--+--+--+--+--+--+ 

1. Output:
>v>>>vv<v>>v>v>>vvv>>>

2. Input:
 +--+--+--+--+--+ 
I   |        |  | 
 +  +--+--+  +  + 
 |        |  |  | 
 +  +--+  +  +  + 
 |  |  |     |  | 
 +  +  +--+  +  + 
 |        |     | 
 +--+  +  +--+--+ 
 |     |         U
 +--+--+--+--+--+ 

2. Output:
>vvv>>v>>>

3. Input:
 +--+--+--+--+--+ 
U      |        | 
 +  +  +--+--+  + 
 |  |     |     | 
 +--+--+  +  +--+ 
 |        |     | 
 +  +--+--+--+  + 
 |  |     |     | 
 +  +  +  +  +--+ 
 |     |         I
 +--+--+--+--+--+ 

3. Output:
<<<^<v<^^>>^<^<<

4. Input (test case with two valid paths):
 +--+--+--+--+--+ 
U      |        | 
 +  +  +--+--+  + 
 |  |           | 
 +--+--+  +  +--+ 
 |        |     | 
 +  +--+--+--+  + 
 |  |     |     | 
 +  +  +  +  +--+ 
 |     |         I
 +--+--+--+--+--+ 

4. Output:
<<^>^<^<<^<<     (<<<^<v<^^>>^<^<< is less efficient, and therefore not a valid output)

5. Input (test case with two valid paths):
                               I
+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+
|     |              |                    |  |
+  +  +  +--+--+--+  +  +--+--+  +--+--+  +  +
|  |     |        |     |        |     |     |
+--+--+--+  +--+  +  +--+--+--+--+  +--+--+--+
|     |  |  |  |     |     |           |     |
+  +  +  +  +  +--+  +  +  +  +--+--+  +--+  +
|  |        |        |  |     |        |     |
+  +--+--+--+  +--+--+  +  +--+  +--+--+  +--+
|  |     |     |        |  |     |     |     |
+  +--+  +  +--+  +--+--+  +--+--+  +  +--+  +
|  |     |        |     |           |        |
+  +  +--+--+--+--+  +  +--+--+--+  +--+  +--+
|     |     |        |        |  |     |     |
+--+--+--+  +  +--+--+  +--+  +  +--+  +--+  +
|              |     |     |        |  |  |  |
+  +--+--+--+--+  +  +  +--+--+--+  +  +  +  +
|     |  |     |  |  |        |        |  |  |
+--+  +  +  +  +  +  +--+--+  +  +  +--+  +  +
|     |     |  |  |  |           |  |     |  |
+--+  +--+--+  +  +  +  +--+--+--+  +  +  +  +
|     |        |  |  |     |        |  |  |  |
+  +--+  +--+--+  +  +--+--+  +  +--+  +  +  +
|        |     |  |     |     |  |     |  |  |
+--+--+--+  +  +  +--+  +  +--+--+  +--+  +  +
|  |        |        |     |        |     |  |
+  +  +--+--+--+--+  +--+--+  +--+--+  +--+  +
|  |              |              |     |     |
+  +  +  +--+--+--+--+--+--+--+--+  +--+  +--+
|     |                                |     |
+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+
                            U

5. Output:
v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv<^<v<<v>v>>>>>>>v     (v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv>v>>>^>>^>^^>vvv<v<v<<v is less efficient, and therefore not a valid output)

6. Input:
 +--+--+--+--+--+
I               |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |               U
 +--+--+--+--+--+

6. Output:
>>v>v>v>v> or >v>v>v>v>> or >>>>>vvvv> or etc. (all are equally efficient, so all 10-length outputs are valid)

7. Input:
 I  U
+  +  +--+--+--+
|  |        |  |
+  +--+--+  +  +
|     |     |  |
+--+  +  +--+  +
|        |  |  |
+  +--+  +  +  +
|     |        |
+--+  +--+--+  +
|     |        |
+--+--+--+--+--+

7. Output:
vv>v>^>^<<^

8. Input:
 +--+--+--+--+--+
 |     |        |
 +  +--+  +--+  +
I   |     |  |  |
 +  +  +--+  +  +
U   |     |  |  |
 +--+--+  +  +  +
 |     |     |  |
 +  +--+--+--+  +
 |               
 +--+--+--+--+--+

8. Output:
>v<

Labyrinthe, die mit diesem Tool erstellt wurden (und in einigen Fällen geringfügig geändert wurden).

code-golf path-finding maze Kevin Cruijssen
quelle
10
Ich habe eine kürzere Lösung für den dritten Testfall gefunden! v<<<<<<^^^^^(Denken Sie immer über den Tellerrand hinaus)
Leo
2
Wenn man nachweisen kann, dass der Code die kürzeste Lösung ergibt, wenn genügend Zeit und Speicher vorhanden sind, konkurriert er dann? Auch bei einer wirklich langen Laufzeit (Ende des Universums Mode)?
Yytsi
1
@ JackBates Es ist ein Witz. Er geht buchstäblich um die Kiste herum zum Ausgang: D
Yytsi
1
Ich denke der erste Testfall ist falsch, es sollte sein >v>>>vv<v>>v>v>>vvv>>>.
smls
1
@KevinCruijssen Zum Beispiel eine Lösung, die jede Kombination von "v ^ <>" auf eine Länge von bis zu der Anzahl leerer Kästchen im Labyrinth prüft. Die richtige Lösung wird vorhanden sein, die Berechnung nimmt jedoch astronomische Zeit in Anspruch.
Yytsi

Antworten:

7

Retina , 338 281 275 273 261 Bytes

¶U
¶&
+`·(\w.+)$
|$1
((.)+I.+¶.+¶(?<-2>.)+)·
$1v
+`((.)*)\+(.).*(¶(?<-2>.)*.)((\w)|·)·?
$1$4$.4$3$6
·v
-v
G`1
·U
&
{`\B·\d+.(\w+)
$1K$&
(\w+)·\d+.\B
$&$1r
(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v
)`\D(\d+).\B(?=.+¶.*\D\1·(\w+))
$&$2A
^.+\d·(\w+)
&$1A
M!`&\w+
I|&

Probieren Sie es online!

Anmerkungen

  • Aufgrund signifikanter Leerzeichen werden alle Leerzeichen ( 0x20) ·sowohl in dieser Antwort als auch in der TIO-Verknüpfung durch interpunct ( ) ersetzt . Das Programm funktioniert einwandfrei, wenn die Leerzeichen wiederhergestellt sind.
  • Verwendet AvKr für oben, unten, links und rechts. Diese können außer durch beliebige Buchstaben ersetzt werdenI .
  • Für den 15 × 15-Testfall benötigt TIO ungefähr 40 Sekunden. Sei geduldig. Überarbeitung des Teils, um den kürzesten Weg zu finden, sobald der Weg den Ausgang erreicht. Es stellte sich heraus, dass das viel Zeit in Anspruch nahm.
  • Konnte bei Labyrinthen mit einer Breite von 66 oder mehr Zellen vollständig brechen, kann jedoch Labyrinthe beliebiger Höhe verarbeiten. Ein Fix für eine beliebige Breite benötigt +1 Byte.

Erläuterung

Das Programm besteht aus 3 Phasen:

  • EIN Konstruktionsphase zum Konvertieren des Labyrinths in ein kompaktes Format, mit dem einfacher gearbeitet werden kann (siehe unten).
  • Eine Füllphase , um das Labyrinth mithilfe eines Flutfüllalgorithmus tatsächlich zu lösen.
  • Eine Rückkehrphase , um den kürzesten Weg am Ausgang zurückzugeben.

Format

Da das ursprüngliche Labyrinthformat ziemlich unhandlich ist, konvertiert der erste Teil des Programms es in ein anderes Format.

Zellen

Im Originalformat wird jede Zelle als 2 × 3-Region dargestellt:

+               <top wall>      <top wall>
<left wall>     <data/space>    <space>

Da die rechte Spalte keine Informationen enthält, identifiziert das Programm Zellen als 2 × 2-Bereiche mit einem + oben links.

Dies lässt uns mit 3 Arten von Zellen:

  • Ich Zellen : Zellen, die sich ordnungsgemäß im Labyrinth befinden.
  • R-Zellen : Zellen rechts vom Labyrinth. Diese werden durch die Polsterung des Eingangs oder Ausgangs erzeugt. Zum Beispiel der AusgangU in Testfall 1 in einer R-Zelle.
  • B-Zellen : Zellen, die sich unterhalb des Labyrinths befinden. Wie R-Cells werden diese durch Auffüllen erstellt.

Im neuen Format werden Zellen als Zeichenfolge variabler Länge dargestellt:

<left wall> <column number> <top wall/exit marker> <path>

Die linke und obere Wand werden aus dem Originalformat kopiert. Die Spaltennummer basiert auf der horizontalen Position der Zelle und dient zur Ausrichtung (Identifizierung von Zellen direkt übereinander / untereinander). Pfad ist eine alphabetische Zeichenfolge, die während der Füllphase verwendet wird, um den kürzesten Pfad zum Erreichen dieser Zelle zu speichern. Pfad- und Ausgangsmarkierung werden weiter erläutert.

Halbzellen

Obwohl die meisten Labyrinthe Zellen sind, gibt es Regionen im Labyrinth, die keine Zellen sind:

  • R Halbzellen : Wenn keine richtige Polsterung vorhanden ist, wird die+ s entlang der rechten Wand keine Zellen, da sie sich in der letzten Spalte befinden.
  • L Halbzellen : Wenn noch Platz vorhanden ist, können sich dort keine Zellen bilden, da +links von ihnen keine vorhanden sind . Beispielsweise befindet sich der Eingang Iin Testfall 1 in einer L-Halbzelle.

Technisch gesehen befinden sich T-Halbzellen oberhalb des Labyrinths (wenn es einen oberen Abstand gibt) und B-Halbzellen (entlang der unteren Wand, wenn es keinen unteren Abstand gibt), aber sie werden nicht im neuen Format dargestellt.

Die oberste Zeile einer Halbzelle wird entfernt, wenn Vollzellen in derselben Zeile erstellt werden. Daher werden Halbzellen im neuen Format wie dargestellt

<wall/exit marker>? <path>

Eine R-Halbzelle ist eben |. Eine L-Halbzelle hat genau Iwie der Pfad nur die Ausgangsmarkierung und einen leeren Pfad oder nur eine leere Wand.

Ein- und Ausgänge

Befindet sich der Eingang links, rechts oder unten im Labyrinth, wird die Eingangsmarkierung Inatürlich als Pfad in die (Halb-) Zelle eingefügt, die bei der Rückkehr zum endgültigen Pfad entfernt werden kann.

Befindet sich der Eingang oberhalb des Labyrinths, wird während der Bauphase der erste Schritt (nach unten) unternommen, da T-Halbzellen während der Bauphase entfernt werden. Auf diese Weise bleibt ein funktionsfähiger Pfad in einer vollen Zelle erhalten. Die obere Wand wird danach geschlossen.

Wenn sich der Ausgang links, rechts oder unten im Labyrinth befindet, wird er Unatürlich in die (Halb-) Zelle aufgenommen. Um nicht als Pfad verwechselt zu werden, &wird anstelle von die Nicht-Alphanum-Ausgangsmarkierung verwendetU . Die Ausgangsmarkierung ist in eine Zelle oder Halbzelle eingebettet (wie oben angegeben).

Befindet sich der Ausgang oberhalb des Labyrinths, ist dies das einzige Loch, das über der obersten Zellenreihe liegen kann (da das Loch für den Eingang, falls vorhanden, bereits geschlossen ist). Jeder Pfad, der dieses Loch erreicht, kann das Labyrinth durch einen Aufwärtsschritt verlassen.

Schließlich muss jede B-Zelle, die den Eingang oder Ausgang enthält, ihre linke Wand schließen, um zu verhindern, dass das Labyrinth durch Gehen entlang der B-Zellen "aufgelöst" wird. Ein- und Ausgänge in R-Zellen oder L-Halbzellen müssen nicht weiter verarbeitet werden, da der Flood-Fill-Algorithmus keine vertikalen Bewegungen zu / von ihnen zulässt.

Beispiel

Als Beispiel der erste Testfall

·+--+--+--+--+--+--+--+--+--+--+·
I···············|·····|········|·
·+··+--+--+--+··+··+··+··+--+··+·
·|···········|·····|··|··|·····|·
·+--+--+--+··+--+--+··+··+··+--+·
·|···········|·····|·····|·····|·
·+··+--+--+··+··+--+--+··+--+··+·
·|·····|·····|·····|·····|·····|·
·+--+··+··+--+--+··+--+--+··+··+·
·|·····|········|········|··|··|·
·+··+--+--+--+··+--+--+··+··+··+·
·|·····|·····|·····|········|··|·
·+--+··+··+--+--+··+--+--+--+--+·
·|··|··|·················|·····|·
·+··+··+--+--+--+··+--+··+··+··+·
·|·····|········|··|··|··|··|··|·
·+--+--+··+··+--+··+··+··+--+··+·
·|········|·····|·····|··|·····|·
·+··+--+--+--+··+··+··+··+··+--+·
·|···········|·····|··|·········U
·+--+--+--+--+--+--+--+--+--+--+·

ist

I·3-·6-·9-·12-·15-|18-·21-|24-·27-·30-|33·
·|3··6-·9-·12-|15··18·|21·|24·|27-·30·|33·
·|3-·6-·9-·12·|15-·18-|21··24·|27··30-|33·
·|3··6-|9-·12·|15··18-|21-·24·|27-·30·|33·
·|3-·6·|9··12-·15-|18··21-·24-|27·|30·|33·
·|3··6-|9-·12-|15··18-|21-·24··27·|30·|33·
·|3-|6·|9··12-·15-·18··21-·24-|27-·30-|33·
·|3··6·|9-·12-·15-|18·|21-|24·|27·|30·|33·
·|3-·6-·9·|12··15-|18··21·|24·|27-·30·|33·
·|3··6-·9-·12-|15··18·|21·|24··27··30-·33&

im neuen Format. Sie können andere Labyrinthe konvertieren hier .

Konstruktionsphase

Die Bauphase umfasst die ersten 13 Programmzeilen.

¶U
¶&

Konvertiert Exit in L-Halbzelle in Exit-Marker

+`·(\w.+)$
|$1

Fügt links vom Eingang und Ausgang Wände in B-Zellen hinzu

((.)+I.+¶.+¶(?<-2>.)+)·
$1v

Macht den ersten Schritt, wenn der Eingang über dem Labyrinth liegt

+`((.)*)\+(.).*(¶(?<-2>.)*.)((\w)|·)·?
$1$4$.4$3$6

Führt die eigentliche Konvertierung durch

·v
-v

Schließt das obere Eingangsloch

G`1

Behält nur Zeilen mit einem 1. Da Labyrinthe mindestens 5 Zellen breit sind und Spaltennummern in Schritten von 3 auftreten, muss eine Zeile mit Zellen neuen Formats eine Spaltennummer zwischen 10 und 19 enthalten.

·U
&

Konvertiert Exit in R-Zelle oder B-Zelle in Exit-Marker

Phase füllen

Die Füllphase setzt sich aus den nächsten 8 Zeilen des Programms zusammen. Es verwendet einen Flood-Fill-Algorithmus, um alle Zellen mit dem kürzesten Weg zu füllen, der vom Eingang dorthin führt.

{`

Versetzt die gesamte Füllphase in eine Schleife, um das gesamte Labyrinth zu füllen.

\B·\d+.(\w+)
$1K$&

Jede Zelle, die sich nach links bewegen kann, tut dies. Eine Zelle kann sich nach links bewegen, wenn

  1. Es hat einen nicht leeren Pfad
  2. es hat eine leere linke Wand; und
  3. Die Zelle oder L-Halbzelle links davon hat einen leeren Pfad
(\w+)·\d+.\B
$&$1r

Dann tut dies jede Zelle, die sich nach rechts bewegen kann. Eine Zelle kann sich nach rechts bewegen, wenn

  1. Es hat einen nicht leeren Pfad
  2. die Zelle rechts davon hat eine leere linke Wand; und
  3. Die Zelle rechts davon hat einen leeren Pfad
(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v

Dann tut dies jede Zelle, die sich nach unten bewegen kann. Eine Zelle kann sich nach unten bewegen, wenn

  1. Es hat einen nicht leeren Pfad
  2. es hat mindestens eine Zelle oder Halbzelle rechts von sich (dh es ist keine R-Zelle)
  3. Die Zelle darunter (dh die Zelle in der nächsten Zeile mit derselben Spaltennummer) hat eine leere obere Wand oder die Ausgangsmarkierung. und
  4. Die Zelle darunter hat einen leeren Pfad

Beachten Sie, dass L-Halbzellen nicht nach unten verschoben werden können, da sie keine Spaltennummern haben.

\D(\d+).\B(?=.+¶.*\D\1·(\w+))
$&$2A

Dann tut dies jede Zelle, die in der Lage ist, sich nach oben zu bewegen. Eine Zelle kann aufsteigen, wenn

  1. Es hat einen nicht leeren Pfad
  2. Es hat eine leere obere Wand
  3. die Zelle darüber hat mindestens eine Zelle oder Halbzelle rechts davon; und
  4. Die Zelle darüber hat einen leeren Pfad

Rückkehrphase

Die Rückkehrphase besteht aus den letzten 5 Zeilen des Programms. Diese Phase sucht nach dem in die Ausgangszelle gefüllten Pfad und gibt ihn zurück.

Das Pfadmuster am Ausgang hängt davon ab, wo sich der Ausgang befindet:

  1. Wenn sich der Ausgang in einer L-Halbzelle befindet, ist diese Halbzelle & <path>
  2. Wenn sich der Ausgang in einer R-Zelle oder B-Zelle befindet, ist dies die Zelle <left wall> <column number> & <path>
  3. Wenn sich der Ausgang in einer T-Halbzelle befindet, befindet sich die zum Ausgang führende I-Zelle, wie oben angegeben, <left wall> <column number> · <path>in der obersten Reihe.
^.+\d·(\w+)
&$1A

Findet eine Zelle in der obersten Zeile mit einer leeren oberen Wand und einem nicht leeren Pfad. Dies erledigt den letzten Fall, indem der letzte Schritt und die Ausgangsmarkierung hinzugefügt werden.

M!`&\w+

Stimmt mit einem nicht leeren Pfad überein und gibt ihn nach einer Ausgangsmarkierung zurück.

I|&

Entfernt die Ausgangsmarkierung und das IPräfix des Pfads.

TwiNight
quelle
Warum das AvKr? Haben sie eine Bedeutung / sind sie Abkürzungen für oben, unten, links und rechts in Ihrer Muttersprache oder gibt es einen anderen Grund, warum Sie diese bestimmten Zeichen gewählt haben?
Kevin Cruijssen
@ KevinCruijssen Einfach, weil ich alphanumerische Zeichen verwenden muss und AvKrdie Pfeile in Alphanum am nächsten sind.
TwiNight
12

Perl 6 , 259 295 Bytes

{my \a=S:g/(.)$0+/{$0 x($/.comb+.5)*2/3}/;sub f (\c,\v,*@p) {with (c ne any v)&&a.lines».comb[+c[0];+c[1]] ->$_ {for (/\s/??10011221!!/I/??a~~/^\N*I|I\N*$/??2101!!1012!!'').comb X-1 {f [c Z+$^a,$^b],(|v,c),@p,chr 8592+$++}
take @p if /U/}}
[~] (gather f a~~/(\N+\n)*(.)*I/,[]).min(+*)[1,3...*]}

Wie es funktioniert

  1. my \a = S:g/ (.) $0+ /{ $0 x ($/.chars + .5) * 2/3 }/;

Dies drückt das Labyrinth zusammen, so dass das Innere jeder Zelle 1x1 statt 2x1 Leerzeichen enthält:

 + - + - + - + - + - + - + - + - + - + - + 
Ich | | | Ich | | |
 + + - + - + + + + - + - + + + 
 | | | | | | | |
 + + - + + + + + - + + + + 
 | | | | | -> | | | | |
 + + + - + + + + + - + + + 
 | | | | | |
 + - + + + - + - + - + + + - + - + 
 | | U | | U
 + - + - + - + - + - + - + - + - + - + - +

  1. sub f (\c,\v,*@p) {
    with (c ne any v) &&                   # If the coordinate wasn't visited yet
         lines».comb[+c[0];+c[1]] -> $_ {  # and a character exists there...
        for (                          # For each vector...
             /\s/ ?? 10011221 !!       #  from a cell: (0,-1), (-1,0), (0,1), (1,0)
             /I/  ?? a~~/^\N*I|I\N*$/
                      ?? 2101          #  from a top/bottom entrance: (1,0), (-1,0)
                      !! 1012          #  from a left/right entrance: (0,-1), (0,1)
                  !! ''                #  otherwise: none
            ).comb X-1 {
            f                       #   Recurse with arguments:
                [c Z+ $^a, $^b],    #     c plus the vector
                (|v, c),            #     v with c appended
                @p, chr 8592 + $++  #     p with the correct Unicode arrow appended
        }
        take @p if /U/
    }
}

Dies ist die rekursive Pfadfindungsfunktion. Es werden drei Parameter benötigt: Die aktuelle Koordinatec=(y,x) , die Liste der bereits besuchten Koordinaten vund der bisher zurückgelegte Pfad p(als Liste der Pfeilzeichen).

Wenn das Zeichen an der aktuellen Koordinate ein Leerzeichen ist, kehrt es zu seinen vier Nachbarn zurück.
Wenn das Zeichen an der aktuellen Koordinate a ist I, wird auf die beiden Nachbarn zurückgegriffen, die nicht "am Rande" liegen, um Lösungen zu zwingen, durch das Labyrinth und nicht um dieses herum zu gehen.
Wenn das Zeichen an der aktuellen Koordinate a ist U, wird takedie akkumulierte Pfadzeichenfolge aufgerufen.

  1. [~] (gather f a ~~ /(\N+\n)*(.)*I/, []).min(+*)[1,3...*]

Die rekursive Funktion wird zunächst mit der Koordinate des Buchstabens aufgerufen I , die mit einem regulären Ausdruck gefunden wird.

Das gather Schlüsselwort sammelt alle Werte, die takeinnerhalb der Funktion aufgerufen wurden, dh alle gültigen nichtzyklischen Pfade durch das Labyrinth.

Der kürzeste Weg wird gewählt, jeder zweite Pfeil wird fallengelassen, um der Tatsache Rechnung zu tragen, dass zwei identische Bewegungen erforderlich sind, um von einer Zelle zur nächsten zu gelangen, und die verbleibenden Pfeile werden verkettet, um die Zeichenfolge zu bilden, die vom Lambda zurückgegeben wird.

smls
quelle
Zuallererst ein toller Job, als Erster meine Herausforderung zu meistern! :) Schlau, wie Sie die beiden Felder in eins geändert haben, um die tatsächliche Bewegung / Zählung zu vereinfachen. +1 von mir. Trotzdem wurden nach einigen Kommentaren zwei neue Testfälle hinzugefügt. Können Sie diese Funktion auch für Ihre Lösung überprüfen? (
Hat
@ KevinCruijssen: Es ging um das Labyrinth in den neuen Testfällen. :( Ich habe den Code jetzt korrigiert. Tio.run unterstützt Perl 6, aber aus irgendeinem Grund funktioniert dies dort nicht ... hat es vielleicht eine zu alte Perl 6-Version?
smls
Gute Arbeit bei der Korrektur des Codes. Es tut mir leid, dass Sie die Regel angegeben haben, nach der Sie Ihre Antwort bereits veröffentlicht haben, aber Chapeau, dass Sie sie so schnell korrigiert haben. Und bezüglich der TIO-Version habe ich keine Ahnung. Nicht wirklich mein Fachwissen ..
Kevin Cruijssen
Da Sie vor vier Monaten die ersten waren, die meine Herausforderung beantworteten, gab ich Ihnen die Prämie. :) Und das Accept ist für die etwas kürzere Retina-Antwort.
Kevin Cruijssen
5

Python 2: 302 Bytes

from re import*
r=lambda x:[''.join(_)for _ in zip(*x)][::-1]
z=',l)for l in s]'
def f(s,b=1,o=0,n=0):
 exec("s=[sub('(..).(?!$)',r'\\1'%s;"%z+"s=r([sub(' I ','+I+'%s);"%z*4)*b+"t=[sub('I  ','@@I'"+z
 if'I U'in`s`or n>3:return`o%4`+n/4*`s`
 return min(`o%4`+f(t,0,o,4*(t==s)),f(r(s),0,o+1,n+1),key=len)

Übernimmt die Eingabe als ein Array von Zeichenfolgen mit derselben Länge. Druckt 0für rechts, 1für unten, 2für links und 3für oben.

Erläuterung

Ich habe einen anderen Ansatz gewählt als die anderen Antworten. Allgemeine Idee: Suchen Sie rekursiv, indem Sie den kürzesten Weg zwischen der Geradeausfahrt und dem Drehen des Boards um 90 Grad finden.

from re import*
r=lambda x:[''.join(_)for _ in zip(*x)][::-1] #Rotates the board counterclockwise
z=',l)for l in s]'    #Suffix for hacky exec golfing
def f(s,b=1,o=0,n=0): #b is 1 on initial call, 0 on every recursion
                      #o is orientation
                      #n is number of rotations
 exec("s=[sub('(..).(?!$)',r'\\1'%s;"%z  #Squeeze the maze
      +"s=r([sub(' I ','+I+'%s);"%z*4)   #Add walls around the I to keep it in the maze
      *b                                 #Only if b is 1
      +"t=[sub('I  ','@@I'"+z            #Attempt to move right

 if'I U'in`s`or n>3:return`o%4`+n/4*`s`  #If the I is next to the U, return the orientation
                                         #If there were 4 rotations, return a long string
 return min(                             #Return the path with the shortest length:
            `o%4`+f(t,0,o,4*(t==s)),       #Moving forward if possible
            f(r(s),0,o+1,n+1),             #Rotating the board
        key=len)

Probieren Sie es online!

deltaepsilon3
quelle
3
Willkommen bei PPCG! Dies ist eine großartige erste Antwort, und ich bin beeindruckt, dass Sie beschlossen haben, als erstes eine ziemlich harte Herausforderung zu meistern. Schlau ist auch, wie Sie Wände um das herum verlegen, um Izu verhindern, dass der Weg außerhalb des Labyrinths verläuft. Genießen Sie Ihren Aufenthalt und +1 von mir. :)
Kevin Cruijssen
2

JavaScript (ES6), 356 Byte

a=>(a=a.map(s=>s.filter((_,i)=>!i|i%3)),g=([x,y])=>a[y]&&a[y][x],o=[],c=([x,y],m="",v=[])=>[[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(p=[x+j,y+k],!m&(!y|y>a[l="length"]-2)==i%2|v.includes(""+p)||(g(p)<"!"?c(p,m+"v>^<"[i],[...v,""+p]):g(p)=="U"?o.push(m.replace(/(.)\1/g,"$1")):0))),a.map((h,i)=>h.map((k,j)=>k=="I"&&c([j,i]))),o.sort((a,b)=>a[l]-b[l])[0])

Übernimmt die Eingabe als 2D-Zeichenfeld. Jede Zeile muss links mit einem Leerzeichen aufgefüllt sein und darf kein Leerzeichen am Ende enthalten, unabhängig davon, wo sich die Start- / Endpunkte befinden.

Verwendet die Idee von smls, das Labyrinth zu zerquetschen, um jede Zelle 1x1 zu machen und wiederholte Pfeile aus der Ausgabe zu entfernen.

Ungolfed und erklärt

a=>(
    a=a.map(s=>s.filter((_,i)=>!i|i%3)),    // squish the maze to 1x1 cells
    g=([x,y])=>a[y]&&a[y][x],               // helper func to get maze value
    o=[],                                   // resulting movesets
    c=([x,y], m="", v=[]) =>                // recursive func to search
                                            // takes current point, moves, and visited spots
        [[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(// for each direction
            p=[x+j,y+k],
            !m & (!y | y>a[l="length"]-2) == i%2 |  // if first move, prevent moving out of maze
                v.includes(""+p) || (               // also prevent if already visited
                    g(p)<"!" ?                      // is this a space?
                        c(p, m+"v>^<"[i], [...v,""+p]) // check this spot recursively
                    : g(p)=="U" ?                   // if this the end?
                        o.push(                     // add moves to moveset
                            m.replace(/(.)\1/g,"$1")) // with double arrows removed
                    : 0
                )
        )),

    a.map((h,i)=>h.map((k,j)=>      // find the starting "I" and
        k=="I" && c([j,i])          // begin recursion at that point
    )),

    o.sort((a,b)=>a[l]-b[l])[0]     // get shortest path
)

Testschnipsel

Code-Snippet anzeigen

Justin Mariner
quelle
1

Retina , 416 Bytes

T` `+`^.*| ?¶.|.*$
I
#
{+` (\w)
d$1
+`(\w) 
$1a
+`(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m`(^(.)*\w.*¶(?<-2>.)*(?(2)(?!))) 
$1w
^
w¶
w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1
{`^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2# 
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2 $5#
}`^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6 
s`U.*

(a|d)\1\1?
$1
ss
s
ww
w

Probieren Sie es online! Wenn ich diese Frage gesehen hätte, als sie ursprünglich veröffentlicht wurde, ist dies wahrscheinlich die Antwort, die ich gegeben hätte. Ich schreibe sie trotzdem, obwohl es in Retina eine viel bessere Antwort gibt. Erläuterung:

T` `+`^.*| ?¶.|.*$

Füllen Sie den Rand aus. Dadurch wird vermieden, dass Sie außerhalb des Labyrinths herumlaufen (z. B. für Testfall 7).

I
#

Platzieren Sie eine nicht alphabetische Markierung am Eingang.

{+` (\w)
d$1
+`(\w) 
$1a
+`(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m`(^(.)*\w.*¶(?<-2>.)*(?(2)(?!))) 
$1w

Überschwemmung vom Ausgang bis zum Eingang. Verwenden Sie bei jedem Schritt einen Buchstaben, um die beste Richtung anzugeben (wasd - das ist Gamern vielleicht vertraut; ich hatte auch über hjkl nachgedacht, fand es aber zu verwirrend). Ziehen Sie es außerdem vor, die gleiche Richtung zu wiederholen. Dadurch wird vermieden, dass zwei vertikal benachbarte Zellen nach links / rechts verschoben werden.

^
w¶

Angenommen, der erste Schritt ist unten.

w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1

Wenn sich jedoch links oder rechts vom Eingang ein Buchstabe befindet, ändern Sie diesen in den ersten Schritt.

{`^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2# 
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2 $5#
}`^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6

Bewegen Sie den Marker in die Richtung des letzten Zuges, lesen Sie die Richtung des nächsten Zuges von dem Feld ab, in das sich der Marker bewegt, und fügen Sie diese zur Liste der Richtungen hinzu. Dies wiederholt sich, bis das Uerreicht ist.

s`U.*

Löschen Sie alles nach den Anweisungen, da es nicht mehr benötigt wird.

(a|d)\1\1?
$1
ss
s
ww
w

Das ursprüngliche Raster ist auf einem 3 × 2-Layout. Während wir uns vertikal bewegen, wenn wir horizontal im Zick-Zack verfahren, optimiert die Überflutungsfüllung die Bewegung und bewegt nur 3n-1-Zeichen horizontal. Wenn wir also durch drei teilen, müssen wir aufrunden. Vertikal teilen wir einfach durch 2.

Ich habe auch eine echte quadratische Rasterlösung untersucht, bei der die Zeichenmatrix selbst quadratisch ist und kein 3 × 2-Layout mit optionalem Rand. Wahrscheinlich nicht konform mit der Frage, reduzierte die Fähigkeit zu transponieren die Anzahl der Bytes auf 350: Probieren Sie es online aus!

Neil
quelle
Schöne Antwort, +1! Ich sehe in Ihrem TIO-Link, dass Sie zwei -um die Eingangs- und Ausgangszeichen hinzugefügt haben. Da die Herausforderung hauptsächlich darin besteht, durch das Labyrinth zu gehen, denke ich, ist das in Ordnung, aber ich bin gespannt: Was waren die Probleme, als Sie diese Wände nicht über / unter dem Iund platziert hatten U? Können Sie auch überprüfen, ob dies für Testfall 7 mit Iund Uoben anstelle von Seiten funktioniert ? TIO überschreitet das 60-Sekunden-Limit, daher kann ich es nicht selbst testen. Obwohl ich Ihre Erklärung gelesen habe, wie man zuerst versucht, standardmäßig herunterzufahren, gehe ich davon aus, dass es gut funktionieren sollte.
Kevin Cruijssen
@KevinCruijssen Die "sekundäre" Antwort funktioniert für Testfall 7, erfordert jedoch zusätzliche Zeichen: Probieren Sie es online aus! Fortsetzung ...
Neil
@KevinCruijssen Die "Haupt" -Antwort hatte einen Fehler, bei dem es überhaupt nicht gelang, den Ausgang in der obersten Zeile zu bewältigen. Es hat auch einen ähnlichen Fehler wie die "sekundäre" Antwort, bei der es bevorzugt ist, außerhalb des Labyrinths herumzulaufen, wenn es kann. (Außerdem habe ich die 60-Sekunden-Grenze nicht erreicht.)
Neil,
Eigentlich könnte ich beide Antworten korrigieren, indem ich den Rand ausfülle. Das mache ich später, wenn ich Zeit habe.
Neil