Hexagonale Labyrinthzeit!

27

Zeit für eine weitere Labyrinth-Herausforderung, aber nicht so, wie Sie es kennen.

Die Regeln für diese Herausforderung unterscheiden sich ein wenig von den meisten Labyrinthherausforderungen. Die Kacheltypen sind wie folgt definiert:

  • S: Der Ort auf dem Labyrinth, an dem Sie beginnen
  • E: Der Ort, an den Sie gelangen möchten
  • 0: Mauer, die man nicht überqueren kann
  • +: Boden, den Sie überqueren können

Sie können in eine von sechs Richtungen fahren: nach oben links, nach oben rechts, nach links, nach rechts, nach unten links oder nach unten rechts.

\ /
-S-
/ \

Das Labyrinth wird nicht gewickelt. Das Ziel ist es, die kürzeste Pfadzeichenfolge zu finden, von der aus Sie Szu gelangen E.

Eingang:

Die Eingabe erfolgt durch durch Leerzeichen getrennte Linien wie bei den gezeigten Labyrinthen. Nach einer Zeile folgt kein Leerzeichen.

Ausgabe:

Eine Reihe von R, Lund Fwo

  • R Dreht Sie um 60 Grad nach rechts (im Uhrzeigersinn)
  • L Dreht Sie nach links (gegen den Uhrzeigersinn) um 60 Grad
  • F Bewegt Sie um ein Feld in die Richtung, auf die Sie zeigen

Sie fangen an zu zeigen left-up

Der kürzeste Weg wird anhand der Länge der erzeugten Zeichenfolge und nicht anhand der Anzahl der besuchten Positionen gezählt. Ihr Programm muss den kürzesten Pfad als Lösung ausgeben.

Wenn das Labyrinth nicht lösbar ist, sollten Sie ausgeben Invalid maze!.

( >>>ist die Ausgabe)

     0 0 0 0
    0 + 0 + 0
   0 0 0 + + 0
  0 + 0 + 0 + 0
 0 0 + + 0 0 + 0
0 0 + 0 + 0 0 + 0
 E 0 + 0 0 + + 0 
  + + 0 + 0 + 0
   0 0 0 0 0 +
    + 0 + + +
     0 S 0 0

>>>RFRFFLFLFRFFLFFFLFLFFRFLFLFRFRFRF

  + 0 0 0 0 0 0
 0 0 0 0 0 + + 0
0 0 E 0 + 0 0 + 0
 0 0 0 0 0 0 0 +
  0 + 0 0 + + +
   0 0 + + 0 0
    S + 0 0 0

>>>Invalid maze!

0 E S

>>>LF


 E + 0
0 + + +
 0 0 S
  + +

>>>FFLF

  E
 0 +
0 + +
 0 +
  S

>>>RFFLFF

 0 E + 0 0
0 + 0 0 + +
 + 0 + + + 0
  + 0 + 0 + 0
   + + + 0 S

>>>FFLFLFFRFRFFRFF

 E 0 + + 0
0 + 0 + + 0
 + + + 0 + 0
  + 0 0 0 0 0
   + + + + 0
    + 0 S 0

>>>FLFFRFFRFLF

(Beachten Sie, dass einige der Labyrinthe andere Lösungen haben, die dieselbe Länge haben, aber hier nicht aufgeführt sind.)

J Atkin
quelle
27
In der Hoffnung auf eine Hexagony-Lösung ...
bkul
3
Ich werde eine Hexagony-Lösung mit 500 Punkten belohnen.
Lirtosiast
@ Lirtosiast2 Jahre später, ich denke, Sechseck könnte eine Strecke für dieses Problem sein;)
J Atkin
Warten wir noch ein paar Jahre.
user202729
Kann es einen nachgestellten Zeilenumbruch geben?
user202729

Antworten:

17

Python 2, 291 Bytes

def f(M):
 Y=map(max,M).index("S");X=M[Y].find("S");V={()};Q=[(0,0,0,1,"")]
 while Q:
    try:x,y,u,v,p=s=Q.pop(0);c=(Y>=y<=X-2*x)*ord(M[Y-y][X-2*x-y])
    except:c=0
    if c==69:return p
    if{c%2*s[:4]}-V:V|={s[:4]};Q+=(x+u,y+v,u,v,p+"F"),(x,y,-v,u+v,p+"R"),(x,y,u+v,-u,p+"L")
 return"Invalid maze!"

Eine Funktion, fdie das Labyrinth als eine Liste von Zeilen aufnimmt und eine Lösung zurückgibt, falls eine vorhanden ist.

Erläuterung

Führt eine Breitensuche im Diagramm der Positions- / Richtungspaare durch, um den kürzesten Weg von Snach zu finden E.

Interessant ist die Suche nach einer kompakten Methode zur Darstellung von Positionen und Richtungen auf einem hexagonalen Gitter, die ein einfaches "Steppen" (dh Bewegen in eine bestimmte Richtung) und Drehen zulässt. Es ist verlockend, hier komplexe Zahlen zu verwenden, um Koordinaten auf einem "echten" hexagonalen Gitter darzustellen, aber dies ist aus einer Reihe von Gründen keine sehr gute Idee, von denen der schwerwiegendste die Tatsache ist, dass wir ein √3 einstecken müssen irgendwo, wo es funktioniert (sin 60 ° = √3 / 2), was bei Verwendung von Gleitkommazahlen kein Problem ist, wenn wir absolute Präzision benötigen (z. B. um die Zustände zu verfolgen, die wir bereits besucht haben;) Sie können versuchen, Ihre JavaScript-Konsole zu starten Math.sqrt(3)*Math.sqrt(3) == 3und zu tippen, und sich selbst davon überzeugen.

Aber wir können einen kleinen Trick benutzen! Anstatt komplexe Zahlen zu verwenden, definieren wir hexagonale Zahlen in ähnlicher Weise als ein Paar reeller Zahlen a + bh , wobei h eine ähnliche Rolle spielt wie das imaginäre i, wenn es sich um komplexe Zahlen handelt. Genau wie bei komplexen Zahlen können wir das Paar ( a , b ) mit einem Punkt auf der Ebene verknüpfen , an dem die reale Achse nach rechts zeigt, die imaginäre Achse nach 60 °, und beide schneiden das reguläre Sechseck der Einheit, wenn das reelle und das reelle die Imaginärteile sind jeweils gleich 1. Die Zuordnung dieses Koordinatensystems zu den Zellen des Labyrinths ist trivial.

Abbildung 1

Im Gegensatz zu i wird die Konstante h durch die Beziehung h 2 = h - 1 definiert (das Auflösen nach h könnte einige Einsichten ergeben.) Und das war's! Hexagonale Zahlen können unter Verwendung der obigen Beziehung ähnlich wie komplexe Zahlen addiert und multipliziert werden: ( a + bh ) + ( c + dh ) = ( a + c ) + ( b + d ) , h , und ( a + bh ) · ( c + dh ) = ( ac - bd ) + ( ad + bc + bd ) h
. Diese Operationen haben dieselbe geometrische Interpretation wie ihre komplexen Gegenstücke: Addition ist Vektoraddition und Multiplikation ist Skalierung und Rotation. Um eine hexgonale Zahl um 60 ° gegen den Uhrzeigersinn zu drehen, multiplizieren wir sie mit h :
( a + bh ) · h = - b + ( a + b ) h , und um dieselbe Zahl um 60 ° im Uhrzeigersinn zu drehen, teilen wir durch h :
( a + bh ) / h = ( a +bh ) · (1 - h ) = (a + b) - ah . Zum Beispiel können wir die nach rechts zeigende hexagonale Einheit 1 = (1, 0) als vollen Kreis gegen den Uhrzeigersinn durch sechsmaliges Multiplizieren mit h annehmen:
(1, 0) · h = (0, 1) ); (0,1) h = (-1,1); (-1, 1) h = (-1, 0); (-1, 0) · h = (0, -1); (0, -1) · h = (1, -1);
(1, -1) · h = (1, 0).

Das Programm verwendet auf diese Weise hexagonale Zahlen, um die aktuelle Position im Labyrinth und die aktuelle Richtung darzustellen, in die angegebene Richtung vorzurücken und die Richtung nach links und rechts zu drehen.

Ell
quelle
31

Hexagony , 2437 Bytes

Das lang erwartete Programm ist hier:

(.=$>({{{({}}{\>6'%={}{?4=$/./\_><./,{}}{<$<\?{&P'_("'"#<".>........_..\></</(\.|/<>}{0/'$.}_.....><>)<.$)).><$./$\))'"<$_.)><.>%'2{/_.>(/)|_>}{{}./..>#/|}.'/$|\})'%.<>{=\$_.\<$))<>(|\4?<.{.%.|/</{=....$/<>/...'..._.>'"'_/<}....({{>%'))}/.><.$./{}{\>$\|$(<><$?..\\<.}_>=<._..\(/.//..\}\.)))))<...2/|$\){}/{..><>).../_$..$_>{0#{{((((/|#.}><..>.<_.\(//$>))<(/.\.\})'"#4?#\_=_-..=.>(<...(..>(/\")<((.\=}}}\>{}{?<,|{>/...(...>($>{)<.>{=P&/(>//(_.)\}=#=\4#|)__.>"'()'\.'..".(\&P'&</'&\$_></}{)<\<0|\<.}.\"\.(.(.(/(\..{.>}=P/|><.(...(..."/<.{"_{{=..)..>})<|><$}}/\}}&P<\(/._...>\$'/.>}/{}}{)..|/(\'.<(\''"")$/{{}})<..'...}}>3#./\$<}|.}|..$.><${{}/>.}}{{<>(""''/..>){<}\?=}{\._=/$/=_>)\{_\._..>)</{\=._.....>(($>}}<.>5#.\/}>)<>-/(.....{\<>}}{{/)\$>=}}}))<...=...(\?{{{?<\<._...}.><..\}}/..>'P&//(\......(..\})"'/./&P'&P{}}&P'<{}\{{{({{{(.\&P=<.><$"&1}(./'"?&'&"\.|>}{?&"?&'P&/|{/&P''</(\..>P&{/&/}{}&'&},/"&P'&?<.|\}{&?"&P'&P'<._.>"&}\(>))<\=}{}<.{/}&?"&"&/"&"?&}\.|>?&"?&{{}}?&//x'&{((<._\($|(}.\/}{/>=&'P&"&/".{3?<.|\"&P'&P}{}&P'<.>&{}}?&"&'P&\=}}<.}/2?".?''5?"/?1{(}\."..../{},<../&//&"&P'&P'&"&"</{}}{{/>"?1''?.'({/}}{}<..>?&"?&}}$>)|P/<.>"&'P&'P&"&"&{/........._/"\$#1}/._.........|,($<'"}'?/_$P#"$0'${)$})$)|........(>/\.#1?<$<|.....>?&}$>=?&"?&/1$..>I;n;v;a;l;i;d;P0;m;a\|\"(}}({=/..$_...\"&P=},}}&P'<.|><....................;...>1"(}}){=/_....>'P&'P&}}_?&/#.>}?4'%\/<...@;1P;e;z<._><>"))'?=<.$$=..\&P}{&</\"><_'|/'&=}<.>{{.<.........|>(/>3")}}){=/=/_.>}P&"?/"<).}_.>?4{=:<.|_...........\$\2$'>4")}}({/."\{&P'&?/><.?|>P...."/=(>(/./(}{{\..>(<>(<>?5'"((..'/...#,</,}{{\.......;.F>..\(...}....._.._..._..._........__..'$......\.<R..$.>))<$}{{&P'&?}<.\$$.\...................$\.<>L\.\(('_"\>}P&"?&{/__/=(.(<.>_)..<...>....\..._.<.....&?=\}=&?"&<.."'>.\>))<.|>))\.|$.>&"?&{{}=P&}?&=}/{\.>&{{P/{">)<|\{<(|\(_(<>\_\?"&P'&P}{{{&<=_.>\&\?"&?<|'{/(/>{{/_>.{/=/\\.>'P&"?&"?&"?/._(\)\\>?&"/_|.>/.$/|$..\\><..\&?}{{}&P'&<}.._>{<|\{}<._$>-")<.>_)<|{)$|..>}=P&"?&"?/...{"./>'P&/=_\{?(/>(<>\(|)__.\&?}}{}&P<}.$.\&P'&P'&<\})))&=<\)<'.'_,><.>"?&'P&'/.|>?&{{}?&"?/>&"?&"?&}}<.".(\\\&?={&P<{..\"&?"&P'&<.?....|.$'\$/\"/.,.>{}{}=/..>&'P&}{{}P/\{}&P{(&?"&?"<'.(\&?"&<}..\?"&?"&<.>P&={}}?&}}P&'P&/.'.>&"?/..>P&}}{{P/\}&P'&?={&?<$}=\"."\P'<{..\'&P'&<....>'P&{}P&"?&{{<\\..>&/$.>}{?&"?/|'$&.P&$P\$'&P={(/..\P\\.\{&?"&?\...\?{{}=<$&P'&P<.,./<?\...{}=P\"&<.>=P&""'?&'P&'/$.#1.>{?1#=$\&'P/\}&P'&?={(,}<._?_&\&?{=&{*=}4<.>P&"?&"?&'P&/1_$>}?&}}=?&){?/\{}&P'&?={&?#<$

Probieren Sie es online!

"Lesbare" Version:

                             ( . = $ > ( { { { ( { } } { \ > 6 ' % = { } { ? 4 = $ / .
                            / \ _ > < . / , { } } { < $ < \ ? { & P ' _ ( " ' " # < " .
                           > . . . . . . . . _ . . \ > < / < / ( \ . | / < > } { 0 / ' $
                          . } _ . . . . . > < > ) < . $ ) ) . > < $ . / $ \ ) ) ' " < $ _
                         . ) > < . > % ' 2 { / _ . > ( / ) | _ > } { { } . / . . > # / | }
                        . ' / $ | \ } ) ' % . < > { = \ $ _ . \ < $ ) ) < > ( | \ 4 ? < . {
                       . % . | / < / { = . . . . $ / < > / . . . ' . . . _ . > ' " ' _ / < }
                      . . . . ( { { > % ' ) ) } / . > < . $ . / { } { \ > $ \ | $ ( < > < $ ?
                     . . \ \ < . } _ > = < . _ . . \ ( / . / / . . \ } \ . ) ) ) ) ) < . . . 2
                    / | $ \ ) { } / { . . > < > ) . . . / _ $ . . $ _ > { 0 # { { ( ( ( ( / | #
                   . } > < . . > . < _ . \ ( / / $ > ) ) < ( / . \ . \ } ) ' " # 4 ? # \ _ = _ -
                  . . = . > ( < . . . ( . . > ( / \ " ) < ( ( . \ = } } } \ > { } { ? < , | { > /
                 . . . ( . . . > ( $ > { ) < . > { = P & / ( > / / ( _ . ) \ } = # = \ 4 # | ) _ _
                . > " ' ( ) ' \ . ' . . " . ( \ & P ' & < / ' & \ $ _ > < / } { ) < \ < 0 | \ < . }
               . \ " \ . ( . ( . ( / ( \ . . { . > } = P / | > < . ( . . . ( . . . " / < . { " _ { {
              = . . ) . . > } ) < | > < $ } } / \ } } & P < \ ( / . _ . . . > \ $ ' / . > } / { } } {
             ) . . | / ( \ ' . < ( \ ' ' " " ) $ / { { } } ) < . . ' . . . } } > 3 # . / \ $ < } | . }
            | . . $ . > < $ { { } / > . } } { { < > ( " " ' ' / . . > ) { < } \ ? = } { \ . _ = / $ / =
           _ > ) \ { _ \ . _ . . > ) < / { \ = . _ . . . . . > ( ( $ > } } < . > 5 # . \ / } > ) < > - /
          ( . . . . . { \ < > } } { { / ) \ $ > = } } } ) ) < . . . = . . . ( \ ? { { { ? < \ < . _ . . .
         } . > < . . \ } } / . . > ' P & / / ( \ . . . . . . ( . . \ } ) " ' / . / & P ' & P { } } & P ' <
        { } \ { { { ( { { { ( . \ & P = < . > < $ " & 1 } ( . / ' " ? & ' & " \ . | > } { ? & " ? & ' P & /
       | { / & P ' ' < / ( \ . . > P & { / & / } { } & ' & } , / " & P ' & ? < . | \ } { & ? " & P ' & P ' <
      . _ . > " & } \ ( > ) ) < \ = } { } < . { / } & ? " & " & / " & " ? & } \ . | > ? & " ? & { { } } ? & /
     / x ' & { ( ( < . _ \ ( $ | ( } . \ / } { / > = & ' P & " & / " . { 3 ? < . | \ " & P ' & P } { } & P ' <
    . > & { } } ? & " & ' P & \ = } } < . } / 2 ? " . ? ' ' 5 ? " / ? 1 { ( } \ . " . . . . / { } , < . . / & /
   / & " & P ' & P ' & " & " < / { } } { { / > " ? 1 ' ' ? . ' ( { / } } { } < . . > ? & " ? & } } $ > ) | P / <
  . > " & ' P & ' P & " & " & { / . . . . . . . . . _ / " \ $ # 1 } / . _ . . . . . . . . . | , ( $ < ' " } ' ? /
 _ $ P # " $ 0 ' $ { ) $ } ) $ ) | . . . . . . . . ( > / \ . # 1 ? < $ < | . . . . . > ? & } $ > = ? & " ? & / 1 $
  . . > I ; n ; v ; a ; l ; i ; d ; P 0 ; m ; a \ | \ " ( } } ( { = / . . $ _ . . . \ " & P = } , } } & P ' < . |
   > < . . . . . . . . . . . . . . . . . . . . ; . . . > 1 " ( } } ) { = / _ . . . . > ' P & ' P & } } _ ? & / #
    . > } ? 4 ' % \ / < . . . @ ; 1 P ; e ; z < . _ > < > " ) ) ' ? = < . $ $ = . . \ & P } { & < / \ " > < _ '
     | / ' & = } < . > { { . < . . . . . . . . . | > ( / > 3 " ) } } ) { = / = / _ . > } P & " ? / " < ) . } _
      . > ? 4 { = : < . | _ . . . . . . . . . . . \ $ \ 2 $ ' > 4 " ) } } ( { / . " \ { & P ' & ? / > < . ? |
       > P . . . . " / = ( > ( / . / ( } { { \ . . > ( < > ( < > ? 5 ' " ( ( . . ' / . . . # , < / , } { { \
        . . . . . . . ; . F > . . \ ( . . . } . . . . . _ . . _ . . . _ . . . _ . . . . . . . . _ _ . . ' $
         . . . . . . \ . < R . . $ . > ) ) < $ } { { & P ' & ? } < . \ $ $ . \ . . . . . . . . . . . . . .
          . . . . . $ \ . < > L \ . \ ( ( ' _ " \ > } P & " ? & { / _ _ / = ( . ( < . > _ ) . . < . . . >
           . . . . \ . . . _ . < . . . . . & ? = \ } = & ? " & < . . " ' > . \ > ) ) < . | > ) ) \ . | $
            . > & " ? & { { } = P & } ? & = } / { \ . > & { { P / { " > ) < | \ { < ( | \ ( _ ( < > \ _
             \ ? " & P ' & P } { { { & < = _ . > \ & \ ? " & ? < | ' { / ( / > { { / _ > . { / = / \ \
              . > ' P & " ? & " ? & " ? / . _ ( \ ) \ \ > ? & " / _ | . > / . $ / | $ . . \ \ > < . .
               \ & ? } { { } & P ' & < } . . _ > { < | \ { } < . _ $ > - " ) < . > _ ) < | { ) $ | .
                . > } = P & " ? & " ? / . . . { " . / > ' P & / = _ \ { ? ( / > ( < > \ ( | ) _ _ .
                 \ & ? } } { } & P < } . $ . \ & P ' & P ' & < \ } ) ) ) & = < \ ) < ' . ' _ , > <
                  . > " ? & ' P & ' / . | > ? & { { } ? & " ? / > & " ? & " ? & } } < . " . ( \ \
                   \ & ? = { & P < { . . \ " & ? " & P ' & < . ? . . . . | . $ ' \ $ / \ " / . ,
                    . > { } { } = / . . > & ' P & } { { } P / \ { } & P { ( & ? " & ? " < ' . (
                     \ & ? " & < } . . \ ? " & ? " & < . > P & = { } } ? & } } P & ' P & / . '
                      . > & " ? / . . > P & } } { { P / \ } & P ' & ? = { & ? < $ } = \ " . "
                       \ P ' < { . . \ ' & P ' & < . . . . > ' P & { } P & " ? & { { < \ \ .
                        . > & / $ . > } { ? & " ? / | ' $ & . P & $ P \ $ ' & P = { ( / . .
                         \ P \ \ . \ { & ? " & ? \ . . . \ ? { { } = < $ & P ' & P < . , .
                          / < ? \ . . . { } = P \ " & < . > = P & " " ' ? & ' P & ' / $ .
                           # 1 . > { ? 1 # = $ \ & ' P / \ } & P ' & ? = { ( , } < . _ ?
                            _ & \ & ? { = & { * = } 4 < . > P & " ? & " ? & ' P & / 1 _
                             $ > } ? & } } = ? & ) { ? / \ { } & P ' & ? = { & ? # < $

Getestet mit Esoteric IDE: Bei einigen größeren Testfällen tritt möglicherweise ein Timeout für TIO auf, aber alle wurden überprüft. Vielen Dank an Timwi, das wäre ohne die IDE nicht möglich gewesen.

Es gibt ziemlich viel leeren Raum, also hätte ich das vielleicht auf ein Sechseck mit einer Seitenlänge von 28 passen können (anstatt auf ein Sechseck mit einer Seitenlänge von 29), aber das wird eine gewaltige Aufgabe, also werde ich es wahrscheinlich nicht versuchen.

Grundlegende Erklärung

Klicken Sie auf die Bilder für eine größere und detailliertere Version.

Funktionen

Funktionen
Hinweis: Unterteilungen sind im Allgemeinen korrekt, können jedoch gelegentlich eine grobe Vermutung sein.

Dieser Code ist ziemlich "funktional" - so sehr es Hexagony erlaubt. Es gibt acht Hauptfunktionen in diesem Code, die im obigen Diagramm gekennzeichnet sind und nach den Nummern benannt sind, mit denen sie aufgerufen werden (ihre Befehlszeigernummern sind also die Nummer mod 6). In (grober) Reihenfolge des Aufrufs sind dies (zitierte Namen sind Speicherstellen im Speicher, die später erläutert werden):

  • S: Die Ausgangsfunktion - liest die Eingabe und richtet das „Referenzarray“ ist , dann startet den „-Pfad stack“ mit den drei Pfaden F, Rund Lbereit für die Hauptverarbeitung. Der Befehlszeiger 0 bewegt sich zu Funktion 0, während die Ausführung zu Funktion 1 bewegt wird.
  • 1 (-11): Die Hauptfunktion - verwendet 2, um einen Pfad zu erhalten, 3, um dessen Gültigkeit zu überprüfen, und wenn gültig, wird zweimal die Funktion -110 / -10 verwendet und dann 4 dreimal, um die neuen Pfade in den Pfad zu kopieren Stack ", indem er zu sich selbst zurückkehrt. Kann die Funktion 5 aufrufen, wenn sich der Pfad am Endpunkt befindet.
  • 2: Liefert den nächsten Pfad vom "Pfadstapel" zur Verarbeitung, ruft die Funktion -1 auf, wenn keine Pfade mehr auf dem Stapel sind. Kehrt zu Funktion 1 zurück.
  • 3: Nimmt ein Paar von Werten sowie die Verschiebungsnummer und überprüft das "Referenzarray", um festzustellen, ob der aktuelle Pfad an einer gültigen Position geendet hat. Eine gültige Position ist entweder der Start innerhalb der ersten 3 Züge oder eine beliebige Position +innerhalb von 2 Zügen, nachdem diese zuerst erreicht wurde. Kehrt zu Funktion 1 zurück.
  • -10 / -110: Kopiert den aktuellen Pfad. Kehrt zu Funktion 1 zurück.
  • 0: Hilft der Funktion 1, die Bewegungsrichtung mit zu steuern F . Kehrt zu Funktion 1 zurück.
  • 4: nimmt eine Kopie des Strompfades und mit der Funktion 1 ändert sie in den gleichen Weg mit entweder vernetzte F, Roder Langehängt. Kehrt zu Funktion 1 zurück.
  • 5: Nimmt den Pfad und druckt den korrekten Pfad aus (z. B. FFLF) und beendet dann das Programm.
  • -1: Druckt Invalid maze!und beendet.
  • (Doppelpfeile): Aus Platzgründen musste die Funktion 1 / -11 in den Raum über der Funktion -1 verschoben werden.

Erinnerung

Speicherlayout
Hinweis: Nochmals vielen Dank an Esoteric IDE für das Diagramm

Der Speicher besteht aus drei Hauptteilen:

  • Referenzarray: Das Raster wird in Spalten mit einem Abstand von 2 gespeichert, wobei bei jedem Schritt ein Wert angegeben wird:
    • 0 steht entweder für a ,0 oder einen gültigen Ort, der vorher zugegriffen wurde Züge mehr als die Stelle in einem beliebigen Richtung zu verlassen wäre erforderlich.
    • 1 steht für ein +noch nicht erreichtes.
    • (höhere Zahl) steht für die Zugnummer, bei der genügend Züge ausgeführt wurden, um den Ort in eine beliebige Richtung zu verlassen.
    • 10 stellt auch eine neue Zeile dar: Diese werden nie erreicht, wenn sie unmittelbar auf das letzte Nicht-Leerzeichen folgen.
  • Schiene: Besteht aus -1s mit einem einzelnen Zeichen -2links und ermöglicht die schnelle Rückkehr des Speicherzeigers zum Kernverarbeitungsbereich.
  • Pfadstapel: Speichert jeden der nicht getesteten Pfade in der Reihenfolge der Pfad-ID (die direkt mit der Zugnummer zusammenhängt, sodass die kürzeren Pfade zuerst getestet werden). Der Pfad wird wie folgt gespeichert:
    Pfadlayout
    • Rot: Die Drehung am Ende des aktuellen Pfads: 0 für nach oben links und im Uhrzeigersinn auf 5
    • Move: die aktuelle Zugnummer (Anleitung - 1)
    • Pfad: der Strompfad, in quartären gespeicherten F, R, Lwie 1, 2, 3jeweils
    • x / y: Koordinaten am Ende des aktuellen Pfades: x + 1 -1s richtig, dann y-Wert hoch (obwohl y = 0 ohnehin als 1 verarbeitet wird, um die Schiene von den Referenzdaten zu trennen)

Andere wichtige Speicherorte:

  1. Das x / y von Ewird hier gespeichert.
  2. Dieser Bereich wird zum Überführen von Pfaden in den und aus dem Speicher verwendet.
  3. Dieser Ort ist das Zentrum, in dem jeder Pfad während der Verarbeitung gespeichert wird.
Boboquack
quelle
Der nächste Schritt besteht darin, Ihr Programm durch Ihr Programm zu führen, um die kürzeste Labyrinthroute zu finden.
Veskah
Ich weiß, dass es jemand posten wird. Endlich ... / Ich habe auch einen anderen Plan, der wahrscheinlich weniger Code enthalten sollte als deiner. Habe eigentlich nie Zeit es umzusetzen.
user202729
@ user202729 wäre interessant, davon zu hören. Ich würde sagen, diese Methode kann wahrscheinlich mindestens zwei Größen kleiner gespielt werden, aber es gibt mit ziemlicher Sicherheit etwas Besseres.
Boboquack
1
Ich warte nur auf @lirtosiast.
J Atkin
1
Entschuldigen Sie die Verspätung.
Lirtosiast
6

Python 3, 466 Bytes

Wäre wahrscheinlich kleiner geworden, wenn ich die Tiefensuche verwendet hätte oder so. Diese Monstrosität benutzt Dijkstra und ist ziemlich schnell, aber sehr lang.

Der Code definiert eine Funktion S, die eine mehrzeilige Zeichenfolge mit dem Labyrinth verwendet und das Ergebnis zurückgibt.

def F(M,L,c):y=M[:M.index(c)].count("\n");return L[y].index(c),y
def S(M):
 L=M.split("\n");Q=[("",)+F(M,L,"S")+(0,)];D={};R=range;H=len;U=R(2**30)
 while Q:
  C,*Q=sorted(Q,key=H);w,x,y,d=C
  for e in R(H(L)>y>-1<x<H(L[y])>0<H(D.get(C[1:],U))>H(w)and(L[y][x]in"+SE")*6):D[C[1:]]=w;E=(d+e)%6;Q+=[(w+",R,RR,RRR,LL,L".split(",")[e]+"F",x+[-1,1,2,1,-1,-2][E],y+[-1,-1,0,1,1,0][E],E)]
 J=min([D.get(F(M,L,"E")+(d,),U)for d in R(6)],key=H);return[J,"Invalid maze!"][J==U]

Hier ist ein Test des Codes.

Ungolfed

def find_char(maze, lines, char):
    y = maze[:maze.index(char)].count("\n")
    return lines[y].index(char), y
def solve(maze):
    lines = maze.split("\n")
    x, y = find_char(maze, lines, "S")
    queue = [("", x, y, 0)]
    solutions = {}
    very_long = range(2**30)
    x_for_direction = [-1,1,2,1,-1,-2]
    y_for_direction = [-1,-1,0,1,1,0]
    rotations = ["","R","RR","RRR","LL","L"]
    while len(queue) > 0:
        queue = sorted(queue, key=len)
        current, *queue = queue
        route, x, y, direction = current
        if 0 <= y < len(lines) and 0 <= x < len(lines[y]) and lines[y][x] in "+SE" and len(solutions.get(current[1:], very_long)) > len(route):
            solutions[current[1:]] = route
            for change in range(6):
                changed = (direction + change) % 6
                queue += [(route + rotations[change] + "F", x + x_for_direction[changed], y + y_for_direction[changed], changed)]
    end_x, end_y = find_char(maze, lines, "E")
    solution = min([solutions.get((end_x, end_y, direction), very_long) for direction in range(6)], key=len)
    return "Invalid maze!" if solution == very_long else solution
PurkkaKoodari
quelle
Wow, sehr nett. Wie lange hast du dafür gebraucht?
J Atkin
1
@JAtkin Nun, die Datei wurde vor 1,5 Stunden erstellt, obwohl ich nicht sicher bin, wie viel Zeit ich tatsächlich mit der Arbeit am Code verbracht habe. Außerdem ist es hier 3 Uhr morgens, sodass meine Produktivität offensichtlich maximal ist.
PurkkaKoodari
Nett, ich verbrachte 2+ Stunden und die meisten von mir waren bereits für ein Standardlabyrinth geschrieben.
J Atkin
Hast du eine ungolfed version?
J Atkin
1
@JAtkin Es wird benötigt, da Sie sich zu Beginn möglicherweise umdrehen müssen. Ohne die Startposition würde es funktionieren L,,R.
PurkkaKoodari
3

Groovy, 624 Bytes. Vordergrund!

Zeit Zeit, um den Ball ins Rollen zu bringen. Nimmt mehrzeilige Zeichenkette als Argument anQ

Q={a->d=[0]*4
a.eachWithIndex{x,y->f=x.indexOf('S');e=x.indexOf('E');
if(f!=-1){d[0]=f;d[1]=y}
if(e!=-1){d[2]=e;d[3]=y}}
g=[]
s={x,y,h,i,j->if(h.contains([x, y])|y>=a.size()||x>=a[y].size()|x<0|y<0)return;k = a[y][x]
def l=h+[[x, y]]
def m=j
def n=1
if(h){
o=h[-1]
p=[x,y]
q=[p[0]-o[0],p[1]-o[1]]
n=[[-2,0]:0,[-1,-1]:1,[1,-1]:2,[2,0]:3,[1,1]:4,[-1,1]:5][q]
r=n-i
m=j+((r==-5|r==5)?' LR'[(int)r/5]:['','R','RR','LL','L'][r])+'F'}
if(k=='E')g+=m
if(k=='+'|k=='S'){s(x-2,y,l,n,m)
s(x+2,y,l,n,m)
s(x+1,y+1,l,n,m)
s(x+1,y-1,l,n,m)
s(x-1,y+1,l,n,m)
s(x-1,y-1,l,n,m)}}
s(d[0],d[1],[],1,'')
print(g.min{it.size()}?:"Invalid maze!")}

Ungolfed-Version:

def map =
        """
  + 0 0 0 0 0 0
 0 0 0 0 0 + + 0
0 0 E 0 + 0 0 + 0
 0 0 0 0 0 0 0 +
  0 + 0 0 + + +
   0 0 + + 0 0
    S + 0 0 0""".split('\n').findAll()
//map =
//        """
// 0 + +
//E + 0 S 0
// 0 0 0 +
//  + + +""".split('\n').findAll()

//map = [""]// TODO remove this, this is type checking only
//map.remove(0)
//reader = System.in.newReader()
//line = reader.readLine()
//while (line != '') {
//    map << line
//    line = reader.readLine()
//}

startAndEnd = [0, 0, 0, 0]
map.eachWithIndex { it, idx ->
    s = it.indexOf('S'); e = it.indexOf('E');
    if (s != -1) {
        startAndEnd[0] = s; startAndEnd[1] = idx
    }
    if (e != -1) {
        startAndEnd[2] = e; startAndEnd[3] = idx
    }
}

def validPaths = []
testMove = { x, y, visited ->// visited is an array of x y pairs that we have already visited in this tree
    if (visited.contains([x, y]) || y >= map.size() || x >= map[y].size() || x < 0 || y < 0)
        return;


    def valueAtPos = map[y][x]
    def newPath = visited + [[x, y]]

    if (valueAtPos == 'E') validPaths += [newPath]
    if (valueAtPos == '+' || valueAtPos == 'S') {
        println "$x, $y passed $valueAtPos"
        testMove(x - 2, y, newPath)
        testMove(x + 2, y, newPath)

        testMove(x + 1, y + 1, newPath)
        testMove(x + 1, y - 1, newPath)

        testMove(x - 1, y + 1, newPath)
        testMove(x - 1, y - 1, newPath)
    }
}

//if (!validPath) invalid()
testMove(startAndEnd[0], startAndEnd[1], [])
println validPaths.join('\n')

//println validPath

def smallest = validPaths.collect {
    def path = ''
    def orintation = 1
    it.inject { old, goal ->
        def chr = map[goal[1]][goal[0]]
        def sub = [goal[0] - old[0], goal[1] - old[1]]
        def newOrin = [[-2, 0]: 0, [-1, -1]: 1, [1, -1]: 2, [2, 0]: 3, [1, 1]:4, [-1, 1]:5][sub]
        def diff = newOrin - orintation// 5L -5R
        def addedPath= ((diff==-5||diff==5)?' LR'[(int)diff/5]:['', 'R', 'RR', 'LL', 'L'][diff]) + 'F'//(diff == 0) ? '' : (diff > 0 ? 'R'*diff : 'L'*(-diff)) + 'F'
//        println "old:$old, goal:$goal chr $chr, orintation $orintation, sub:$sub newOrin $newOrin newPath $addedPath diff $diff"
        path += addedPath
        orintation = newOrin
        goal
    }
    path
}.min{it.size()}
//println "paths:\n${smallest.join('\n')}"
if (smallest)
    println "path $smallest"
else
    println "Invalid maze!"
J Atkin
quelle
3

C #, 600 574 Bytes

Vollständiges Programm, akzeptiert Eingaben von STDIN und gibt sie an STDOUT aus.

Bearbeiten: Es gab einen Fehler in der Wrap-Behandlung (bei keinem der angegebenen Testfälle ist ein Fehler aufgetreten), der 1 Byte hinzugefügt hätte, sodass ich etwas mehr Golf gespielt habe, um dies zu kompensieren.

using Q=System.Console;struct P{int p,d;static void Main(){string D="",L;int w=0,W=0,o,n=1;for(;(L=Q.ReadLine())!=null;D+=L)w=(o=(L+="X").Length+1)>w?o:w;for(;W<D.Length;)D=D.Insert(W+1,"".PadLeft(D[W++]>87?w-W%w:0));P[]K=new P[W*6];var T=new string[W*6];P c=K[o=0]=new P{p=D.IndexOf('S')};for(System.Action A=()=>{if(c.p>=0&c.p<W&System.Array.IndexOf(K,c)<0&&D[c.p]%8>0){T[n]=T[o]+L;K[n]=c;n=D[c.p]==69?-n:n+1;}};o<n;o++){c=K[o];L="R";c.d=++c.d%6;A();L="L";c.d=(c.d+4)%6;A();L="F";c=K[o];c.p+=new[]{~w,1-w,2,1+w,w-1,-2}[c.d%6];A();}Q.WriteLine(n>0?"Invalid maze!":T[-n]);}}

Zunächst wird die Karte eingelesen und (an jede Zeile angehängt , damit sie weiß, wo sie endet. Anschließend können Sie eine Menge Leerzeichen hinzufügen, um die Karte rechteckig zu machen Wir führen Wickelprüfungen durch (siehe unten). Es berechnet die Breite des Rechtecks ​​an einem bestimmten Punkt und ermittelt die Gesamtlänge der Karte.

Als nächstes wird alles für eine Breitensuche initialisiert. Es werden zwei große Arrays erstellt, eines zum Speichern aller Zustände, die wir bei unserer Suche erforschen müssen, das andere zum Aufzeichnen der Route, die wir genommen haben, um zu jedem Zustand zu gelangen. Der Anfangszustand wird zum fälligen Array hinzugefügt, wobei der Kopf- und der Endzeiger oben voreingestellt sind. Alles ist 1-indiziert.

Wir iterieren dann, bis der Schwanz gegen den Kopf stößt, oder zumindest scheint er gegen den Kopf gestoßen zu sein. Für jeden Status, den wir besucht haben, versuchen wir, einen neuen Status an derselben Position hinzuzufügen, an der wir nach links oder rechts gedreht wurden, und dann einen, an der wir vorwärts gegangen sind. Die Richtungen sind indiziert, wobei die anfängliche Richtung (standardmäßig auf 0) "oben links" entspricht.

Wenn wir versuchen, einen Zustand in die Warteschlange zu stellen, wird er gebunden, aber nicht umbrochen, da auf der rechten Seite Spalten mit Leerzeichen angezeigt werden, auf denen die Meldung "Dürfen wir hier sein?" check (du darfst nicht auf Leerzeichen sein). Wenn sich der Status in der Warteschlange befindet, prüfen wir, ob er sich in der EZelle befindet. Wenn dies der Fall ist, setzen wir den Kopf der Warteschlange auf minus, wodurch die Hauptschleife beendet und die letzte Zeile des Programms zum Drucken angewiesen wird Geben Sie die entsprechende Route und nicht die Fehlermeldung aus (die anzeigt, ob die zu erweiternden Zustände abgelaufen sind (der Schwanz stürzt gegen den Kopf).

using Q=System.Console;

// mod 8 table (the block of zeros is what we are after - it's everywhere we /can't/ go)
//   0 (space)
// O 0
// X 0
// S 3
// + 3
// E 5

struct P
{
    int p,d;
    static void Main()
    {
        // it's probably a bad thing that I have my own standards for naming this stupid read sequence by now
        string D="", // map
        L; // line/path char

        int w=0, // width
        W=0, // full length
        o, // next state to expand
        n=1; // next state to fill

        for(;(L=Q.ReadLine())!=null;D+=L) // read in map
            w=(o=(L+="X").Length+1)>w?o:w; // assertain max length (and mark end, and remove any need for wrap checking)

        // now we need to add those trailing spaces...
        for(;W<D.Length;)
            D=D.Insert(W+1,"".PadLeft(D[W++]>87?w-W%w:0)); // inject a load of spaces if we hit an X

        P[]K=new P[W*6]; // create space for due states (can't be more states than 6*number of cells)
        var T=new string[W*6]; // create space for routes (never done it this way before, kind of exciting :D)
        P c=K[o=0]=new P{p=D.IndexOf('S')}; // set first state (assignment to c is just to make the lambda shut up about unassigned variables)

        // run bfs
        for(

            System.Action A=()=> // this adds c to the list of states to be expanded, if a whole load of checks pass
            {
                if(//n>0& // we havn't already finished - we don't need this, because we can't win on the first turn, so can't win unless we go forward, which we check last
                   c.p>=0&c.p<W& // c is within bounds
                   System.Array.IndexOf(K,c)<0&& // we havn't seen c yet (the && is to prevent the following lookup IOBing)
                   D[c.p]%8>0) // and we can move here (see table at top of code)
                {
                    T[n]=T[o]+L; // store route
                    K[n]=c; // store state
                    n=D[c.p]==69?-n:n+1; // check if we are at the end, if so, set n to be negative of itself so we know, and can look up the route (otherwise, increment n)
                }
            }

            ;o<n;o++) // o<n also catches n<0
        {
            c=K[o]; // take current
            L="R"; // say we are going right
            c.d=++c.d%6; // turn right
            A(); // go!

            L="L"; // say we are going left
            c.d=(c.d+4)%6; // turn left
            A(); // go!

            L="F"; // say we - you get the picture
            c=K[o];
            c.p+=new[]{~w,1-w,2,1+w,w-1,-2}[c.d%6]; // look up direction of travel (~w = -w-1)
            A();
        }

        // check if we visited the end
        Q.WriteLine(n>0?"Invalid maze!":T[-n]); // if n<0, then we found the end, so spit out the corresponding route, otherwise, the maze is invlida
    }
}

Wie die meisten meiner Graph-Suchen auf dieser Site verwende ich C # -Strukturen, die standardmäßig anhand von Literalwerten verglichen werden.

VisualMelon
quelle
2

Python 2, 703 Bytes

Nicht so gut wie die beiden anderen Versionen, aber zumindest funktioniert es haha. Stellen Sie sich Mauf das Labyrinth.

Da ich keine Erfahrung mit dem Lösen von Labyrinthen habe, wird nur ein Brute-Force-Ansatz angewendet, bei dem alle möglichen Lösungen gefunden werden, bei denen es nicht darum geht, sich selbst zu überkreuzen. Es berechnet die Umdrehungen aus den kürzesten und wählt dann das kürzeste Ergebnis daraus.

z=zip;d=z((-1,1,-2,2,-1,1),(-1,-1,0,0,1,1));E=enumerate;D={};t=tuple;o=list;b=o.index
for y,i in E(M.split('\n')):
 for x,j in E(o(i)):
  c=(x,y);D[c]=j
  if j=='S':s=c
  if j=='E':e=c
def P(s,e,D,p):
 p=o(p);p.append(s);D=D.copy();D[s]=''
 for i in d:
  c=t(x+y for x,y in z(s,i))
  if c not in p and c in D:
   if D[c]=='E':L.append(p+[c])
   if D[c]=='+':P(c,e,D,p)
def R(p):
 a=[0,1,3,5,4,2];h=d[0];x=p[0];s=''
 for c in p[1:]:
  r=t(x-y for x,y in z(c,x));n=0
  while h!=r:n+=1;h=d[a[(b(a,b(d,h))+1)%6]]
  s+=['L'*(6-n),'R'*n][n<3]+'F';x=t(x+y for x,y in z(x,h))
 return s
L=[];P(s,e,D,[])
try:l=len(min(L))
except ValueError:print"Invalid maze!"
else:print min([R(i)for i in L if len(i)==l],key=len)

Messy ungolfed version:

maze = """
     0 0 0 0
    0 + 0 + 0
   0 0 0 + + 0
  0 + 0 + 0 + 0
 0 0 + + 0 0 + 0
0 0 + 0 + 0 0 + 0
 E 0 + 0 0 + + 0 
  + + 0 + 0 + 0
   0 0 0 0 0 +
    + 0 + + +
     0 S 0 0
     """
directions = [(-1, -1), (1, -1),
              (-2, 0), (2, 0),
              (-1, 1), (1, 1)]


maze_dict = {}
maze_lines = maze.split('\n')
for y, row in enumerate(maze_lines):
    if row:
        for x, item in enumerate(list(row)):
            coordinates = (x, y)
            maze_dict[coordinates] = item
            if item == 'S':
                start = coordinates
            elif item == 'E':
                end = coordinates

list_of_paths = []


def find_path(start, end, maze_dict, current_path=None):
    if current_path is None:
        current_path = []
    current_path = list(current_path)
    current_path.append(start)
    current_dict = maze_dict.copy()
    current_dict[start] = '0'

    for direction in directions:
        new_coordinate = (start[0] + direction[0], start[1] + direction[1])

        if new_coordinate in current_path:
            pass

        elif new_coordinate in current_dict:
            if current_dict[new_coordinate] == 'E':
                list_of_paths.append(current_path + [new_coordinate])
                break
            elif current_dict[new_coordinate] == '+':
                find_path(new_coordinate, end, current_dict, current_path)


find_path(start, end, maze_dict)


def find_route(path):

    heading_R = [0, 1, 3, 5, 4, 2]
    heading = (-1, -1)
    current_pos = path[0]
    current_heading = directions.index(heading)
    output_string = []
    for coordinate in path[1:]:
        required_heading = (coordinate[0] - current_pos[0], coordinate[1] - current_pos[1])

        count_R = 0
        while heading != required_heading:
            count_R += 1
            heading_index = directions.index(heading)
            heading_order = (heading_R.index(heading_index) + 1) % len(heading_R)
            heading = directions[heading_R[heading_order]]

        if count_R:
            if count_R > 3:
                output_string += ['L'] * (6 - count_R)
            else:
                output_string += ['R'] * count_R

        output_string.append('F')
        current_pos = (current_pos[0] + heading[0], current_pos[1] + heading[1])
    return ''.join(output_string)


routes = []
try:
    min_len = len(min(list_of_paths))
except ValueError:
    print "Invalid maze!"
else:
    for i in list_of_paths:
        if len(i) == min_len:
            routes.append(find_route(i))

    print 'Shortest route to end: {}'.format(min(routes, key=len))
Peter
quelle
Sie können if heading != required_heading: while heading != required_heading: mit nurwhile heading != required_heading:
J Atkin
Yeah, danke, haha, ich hatte einige Dinge bemerkt, einschließlich der Tatsache, dass ich beim Spielen der Golf-Version den Originalcode nicht aktualisiert habe. Ich werde das jetzt tun, da ich es gerade geschafft habe, ein paar weitere Charaktere zu entfernen
Peter
Nett! (Füllen Sie die 15 Zeichen min)
J Atkin
<Dies ist ein nicht erkanntes HTML-Tag, also keine Ahnung.>
CalculatorFeline