Inspiriert von We do Tower Hopping und verwandt mit 2D Maze Minus 1D
Einführung
Ihre Aufgabe ist es, den kürzesten Weg zu finden, um ein Array-Labyrinth nach festgelegten Regeln zu verlassen.
Herausforderung
Ein 1D-Array a mit n Elementen kann als Labyrinth aus n Punkten betrachtet werden, wobei Punkt mit Index k einseitig mit den Punkten mit k + a [ k ] und k - a [ k ] verbunden ist. Mit anderen Worten, können Sie vorwärts oder rückwärts springen genau ein [ k ] Schritte vom Punkt mit dem Index k . Punkte mit einem Index außerhalb der Grenzen des Arrays werden außerhalb des Labyrinths betrachtet.
Betrachten Sie zur Veranschaulichung das folgende Array:
[0,8,5,9,4,1,1,1,2,1,2]
Wenn wir uns gerade am 5. Element befinden, da das Element 4 ist, können wir 4 Schritte vorwärts zum 9. Element oder 4 Schritte rückwärts zum 1. Element springen. Wenn wir Letzteres tun, erhalten wir das Element 0, was darauf hinweist, dass keine weiteren Bewegungen möglich sind. Wenn wir das erstere machen, da das 9. Element 2 ist, können wir uns dafür entscheiden, zum 11. Element zu springen, das wiederum eine 2 ist, und dann können wir erneut zum "13. Element" springen, das außerhalb der Grenzen des ist Array und betrachtet einen Ausgang zum Labyrinth.
Wenn wir also von dem Element in der Mitte ausgehen, besteht ein Weg, das Labyrinth zu verlassen, darin, 1 Schritt zurück, 4 Schritte vorwärts, 2 Schritte vorwärts und erneut 2 Schritte vorwärts zu hüpfen, was als Array ausgedrückt werden kann [-1,4,2,2]
. Alternativ können Sie es mit dem Array ausdrücken, [4,8,10,12]
das den auf Null basierenden Index aller Zwischen- und Endpunkte aufzeichnet (der auf 1 basierende Index ist ebenfalls in Ordnung), oder nur mit den Zeichen [-1,1,1,1]
.
Es ist auch in Ordnung, das Labyrinth vom Ende mit dem niedrigen Index zu verlassen.
Die erste Notation zu verwenden und vom selben Element aus zu beginnen, [1,1,1,2,2]
ist ebenfalls eine Lösung, aber nicht optimal, da es 5 statt 4 Schritte gibt.
Die Aufgabe besteht darin, den kürzesten Weg zu finden, um aus dem Array-Labyrinth herauszukommen und den Weg auszugeben. Wenn es mehr als einen optimalen Pfad gibt, können Sie einen oder alle Pfade ausgeben. Wenn es keine Lösung gibt, sollten Sie einen von Ihnen gewählten falschen Wert ausgeben, der aus einem gültigen Pfad erkennbar ist (es ist auch in Ordnung, überhaupt keine Ausgabe zu erstellen).
Der Einfachheit halber ist die Anzahl der Elemente im Array immer ungerade und wir beginnen immer mit dem Element in der Mitte.
Testfälle
Die Testfälle veranschaulichen verschiedene Ausgabeformen, auf die Sie jedoch nicht beschränkt sind.
Input
Output
[0,8,5,9,4,1,1,1,2,1,2]
[-1,4,2,2]
[2,3,7,1,2,0,2,8,9]
[2,9] (or [2,-5] or [[2,9],[2,-5]])
[0,1,2,2,3,4,4,4,3,2,2,3,0]
[1,-1,1,1]
[0,1,2,2,4,4,6,6,6,6,6,4,2,1,2,2,0]
[]
Technische Daten
Sie können eine Funktion oder ein vollständiges Programm schreiben.
Das Array enthält nur nichtnegative Ganzzahlen.
Sie können Eingaben und Ausgaben über jedes Standardformular vornehmen . Bitte geben Sie in Ihrer Antwort an, welches Formular Sie verwenden.
Dies ist Code-Golf , die niedrigste Anzahl von Bytes gewinnt.
Wie üblich gelten hier Standardlücken .
quelle
[0,8,5,9,4,1,1,1,2,1,2]
Ausgabe[[-1,4,2,2]]
)[1,1,1,-1]
statt[-1,1,1,1]
?Antworten:
JavaScript (ES6), 117 Byte
Gibt ein Array mit 0-indizierten Zwischen- und Endpunkten oder ein leeres Array zurück, wenn keine Lösung vorhanden ist.
Probieren Sie es online!
Kommentiert
quelle
Schale , 22 Bytes
Gibt eine Liste mit Zeichen oder eine leere Liste zurück, wenn keine Lösung vorhanden ist. Probieren Sie es online!
Erläuterung
Dies ist eine Brute-Force-Lösung, die Listen
-1,0,1
mit zunehmender Länge überprüft und die erste zurückgibt, die zu einem Sprung aus dem Array führt. Da es nur eine minimale Länge hat, enthält es keine Nullen.quelle
Python 3 ,
195188179 BytesProbieren Sie es online!
Bearbeiten:
all(..)and s => all(..)*s
,if u not in x => if{u}-x
Ersteres nutzt
boolean * list == int * list
die Set-Differenz (leeres Set ist auch falsch).Ausgabeformat: Verschachteltes Array aller optimalen Antworten, angegeben als nullbasierte Indizes für Zwischen- und Endpunkte.
Zum Beispiel:
f([0,8,5,9,4,1,1,1,2,1,2]) == [[4, 8, 10, 12]]
.Der Algorithmus ist einfach BFS. Zeichnet
s
alle möglicheni
Pfade mit der Längei
der Iteration auf, mit Ausnahme der bereits besuchten Indizes. Beachten Sie, dass die erweiterte Sternnotation (ab) verwendet wird, da ein wiederholter Array-Zugriff teuer ist. Ich habe festgestellt, dass eine solche Notation bei richtiger Verwendung auch einige Leerzeichen reduzieren kann.Ich habe aus der obigen Lösung auch eine rekursive (aber längere) Version gemacht. Beides
s and
undor s
wird benötigt, sonst klappt es nicht.Python 3 , 210 Bytes
Probieren Sie es online!
quelle
Haskell ,
207202 Bytes5 Bytes gespart dank BMO .
Probieren Sie es online!
Dies ist eine Funktion, die eine Liste von
Int
als Parameter verwendet und eine Liste von Pfaden zurückgibt, wobei jeder Pfad eine Liste von relativen Sprüngen ist, die ausgeführt werden, um aus dem Array herauszukommen.Die ungolfed Version:
quelle
C (gcc) , 269 Bytes
Probieren Sie es online!
Zunächst versuchte man eine rekursive Rückverfolgungssuche, weil die Verwendung
main
für die Rekursion immer Spaß macht. Am Ende konnte eine unkomplizierte nicht-rekursive Breitensuche jedoch verkleinert werden, wie es diese Version ist. Dieses Programm verwendet das Eingabearray als Befehlszeilenargumente ohne geschweifte Klammern, z. B.0 8 5 9 4 1 1 1 2 1 2
für das erste bereitgestellte Beispiel. Das Programm gibt auf stdout eine Liste von 1-indizierten , durch Kommas getrennten Array-Indizes in umgekehrter Reihenfolge aus, beginnend mit dem endgültigen, außerhalb der Grenzen liegenden / "Escape" -Index und durcharbeiten der erreichten Zwischenindizes (es gibt den nicht aus Mitte, Startindex). Das Programm gibt keine geschweiften Klammern um das Array aus und hinterlässt ein Komma, da getrenntprintf
Anweisungen enthalten viele Zeichen. Die Ausgabe, die dem obigen ersten Testbeispiel entspricht, ist13,11,9,5,
beispielsweise.Wenn es keinen Fluchtweg aus dem Array-Labyrinth gibt, gibt das Programm nichts aus.
Entgolfet und erklärt ist es unten (stark entgolfet mit einigen Änderungen für die Lesbarkeit):
Wie für C-Code üblich, enthält die Kompilierungsausgabe natürlich eine freundliche Wand mit Warnungen und Hinweisen.
quelle
Perl 5 , -a: 73 Bytes
(altes Zählen: 75 Bytes,
+1
füra
und+1
zum Ersetzen-//
durch-/$/
und Verwenden$`
für$'
)Geben Sie das Eingabearray als eine Zeile in STDIN ein, z
0 8 5 9 4 1 1 1 2 1 2
druckt die besuchten Positionen in umgekehrter Reihenfolge einschließlich des Startpunkts aus und stürzt dann ab
Druckt nichts, wenn es keine Lösung gibt
Probieren Sie es online!
quelle
Ruby , 102 Bytes
Probieren Sie es online!
Nimmt das Eingabelabyrinth als Array und gibt es aus, indem der Escape-Pfad vom Ausgang zum Startpunkt (einschließlich) umgekehrt gedruckt wird. Druckt nichts, wenn es keinen Fluchtweg gibt.
Bei diesem Ansatz wird die Kartenmethode missbraucht, um ein temporäres Array zu durchlaufen, in dem der Verlauf von Pfaden gespeichert ist. Dieses Array wird ständig erweitert, wenn ein weiterer möglicher Schritt erforderlich ist.
Im Prinzip könnte ich ein weiteres Byte einsparen, indem ich
return x
stattdessen verwendebreak p x
, aber das würde bedeuten, zu behaupten, dass mein falscher Wert gleich dem ganzen monströsen Müll ist, der in gespeichert istb
. Wahrscheinlich wäre das zu viel, selbst wenn man die erlaubte Flexibilität der Ausgabe bedenkt ...Komplettlösung
quelle