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 beginnenE: Der Ort, an den Sie gelangen möchten0: 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
RDreht Sie um 60 Grad nach rechts (im Uhrzeigersinn)LDreht Sie nach links (gegen den Uhrzeigersinn) um 60 GradFBewegt 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.)
quelle
Antworten:
Python 2, 291 Bytes
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 findenE.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.
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.
quelle
Hexagony , 2437 Bytes
Das lang erwartete Programm ist hier:
Probieren Sie es online!
"Lesbare" Version:
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
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):
F,RundLbereit für die Hauptverarbeitung. Der Befehlszeiger 0 bewegt sich zu Funktion 0, während die Ausführung zu Funktion 1 bewegt wird.+innerhalb von 2 Zügen, nachdem diese zuerst erreicht wurde. Kehrt zu Funktion 1 zurück.F. Kehrt zu Funktion 1 zurück.F,RoderLangehängt. Kehrt zu Funktion 1 zurück.FFLF) und beendet dann das Programm.Invalid maze!und beendet.Erinnerung
Hinweis: Nochmals vielen Dank an Esoteric IDE für das Diagramm
Der Speicher besteht aus drei Hauptteilen:
0oder einen gültigen Ort, der vorher zugegriffen wurde Züge mehr als die Stelle in einem beliebigen Richtung zu verlassen wäre erforderlich.+noch nicht erreichtes.-1s mit einem einzelnen Zeichen-2links und ermöglicht die schnelle Rückkehr des Speicherzeigers zum Kernverarbeitungsbereich.F,R,Lwie1,2,3jeweils-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:
Ewird hier gespeichert.quelle
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.Hier ist ein Test des Codes.
Ungolfed
quelle
L,,R.Groovy, 624 Bytes. Vordergrund!
Zeit Zeit, um den Ball ins Rollen zu bringen. Nimmt mehrzeilige Zeichenkette als Argument an
QUngolfed-Version:
quelle
C #,
600574 BytesVollstä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.
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).Wie die meisten meiner Graph-Suchen auf dieser Site verwende ich C # -Strukturen, die standardmäßig anhand von Literalwerten verglichen werden.
quelle
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.
Messy ungolfed version:
quelle
if heading != required_heading: while heading != required_heading:mit nurwhile heading != required_heading: