Einführung
Sie haben das Unglück, in einem außer Kontrolle geratenen Auto auf einem Hindernisparcours stecken zu bleiben. Alle Funktionen des Fahrzeugs sprechen nicht an, mit Ausnahme des beschädigten Lenksystems. Es kann geradeaus fahren oder nach rechts abbiegen. Kann das Auto in Sicherheit gebracht werden?
Mechanik
Ihr Auto beginnt in der oberen linken Ecke einer 8x8-Karte und versucht, sich in der unteren rechten Ecke in Sicherheit zu bringen. Das Auto hat eine Ausrichtung (anfangs rechts), die in 90-Grad-Schritten gemessen wird. Das Auto kann eine von zwei Aktionen ausführen:
- Fahren Sie ein Quadrat vorwärts oder
- Drehen Sie um 90 Grad im Uhrzeigersinn und fahren Sie dann ein Feld vorwärts
Beachten Sie, dass das Auto nicht scharf genug drehen kann, um eine 180-Grad-Drehung auf einem einzelnen Quadrat durchzuführen.
Einige der Plätze sind Hindernisse. Wenn das Auto auf ein Hindernisfeld fährt, stürzt es ab. Alles, was sich außerhalb des 8x8-Kurses befindet, wird als Hindernis angesehen, sodass das Abfahren des Kurses einem Absturz gleichkommt.
Das untere rechte Quadrat ist das sichere Quadrat, mit dem das Auto dem Hindernisparcours entkommen kann. Das Startquadrat und das sichere Quadrat gelten als keine Hindernisse.
Aufgabe
Sie müssen ein Programm oder eine Funktion schreiben, die als Eingabe ein 8x8-Array (Matrix, Listenliste usw.) verwendet, das den Hindernislauf darstellt. Das Programm gibt einen Booleschen Wert oder einen ähnlichen Wahrheitswert zurück oder gibt ihn aus. Wenn es für das Auto möglich ist, den sicheren Platz zu erreichen, ohne zusammenzustoßen (dh wenn die Karte lösbar ist), ist die Ausgabe True
, ansonsten ist es False
.
Wertung
Standard Code Golf Regeln - der Gewinner ist der Code mit den wenigsten Bytes.
Boni:
Wenn Ihr Code für eine lösbare Karte eine gültige Reihe von Fahrereingaben ausgibt, die das Auto zum sicheren Feld führen, ziehen Sie 10 Prozentpunkte von Ihrer Punktzahl ab. Ein Beispiel für ein Ausgabeformat ist
SRSSR
(Straight, Right, Straight, Straight, Right). Diese Ausgabe würde die Standardausgabe ersetzenTrue
.Wenn bei einer unlösbaren Karte die Ausgabe Ihres Codes zwischen Situationen unterscheidet, in denen ein Absturz unvermeidbar ist, und Situationen, in denen es möglich ist, den Hindernisparcours für immer zu befahren, ziehen Sie 10 Prozentpunkte von Ihrer Punktzahl ab. Eine Beispielausgabe kann sein,
Crash
wenn ein Crash unvermeidbar ist oderStuck
das Auto für immer im Hindernisparcours steckt. Diese Ausgaben würden die StandardausgabeFalse
für eine unlösbare Karte ersetzen .
Beispiel
Wenn das Programm ein 8x8-Array wie dieses erhält:
[[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 0, 0, 1, 0]]
Es würde als eine Karte wie diese interpretiert, wobei schwarze Quadrate Hindernisse anzeigen:
Und eine mögliche Lösung könnte sein:
Da es eine Lösung gibt, sollte das Programm True
diese Karte zurückgeben / drucken . Die hier gezeigte Abfolge von Zügen ist SSSSRSRRRSRSSRRRSSRSSS
.
Crash
und geschriebenStuck
. Sie sind hier, weil sie so lang sind. Zeile 2 gefüllt, alles andere leer ->Crash
. Zeile 7 gefüllt, alles andere leer ->Stuck
Antworten:
JavaScript (ES6) - 122
124148Bytes162172178187190193208Vielen Dank an Optimizer und DocMax für hilfreiche Vorschläge zur Verbesserung dieses Codes:
Gibt
true
(wahr) für lösbar undfalse
(falsch) für unlösbar zurück.Funktioniert ab heute nur in Firefox, da JavaScript 1.7 unterstützt wird.
Test Board
quelle
D=(x,y,d,t,a)=>!t[i=x+y*8+d*64]&&(t[i]=1,x+=d==0?1:d==2?-1:0,y+=d==1?1:d==3?-1:0,x==7&&y==7||!((x|y)&~7||a[y][x])&&G(x,y,d,t,a));G=(x,y,d,t,a)=>D(x,y,d,t,a)||D(x,y,d+1&3,t,a);F=a=>G(0,0,0,[],a)
.D=d=>!t[i=x+y*8+d/4]&&(t[i]=1,x+=d?d^2?0:-1:1,y+=d^1?d^3?0:-1:1,x==7&&y==7||!((x|y)&~7||b[y][x])&&G(x,y,d));G=(X,Y,d)=>D(d,x=X,y=Y)||D(d+1&3,x=X,y=Y);F=a=>G(0,0,0,b=a,t={})
- Getestet.[[0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1], [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, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
. Das sollte falsch geben.x
undy
sind beide Globals, können Sie nicht zwei Testfälle laufen , bevor Sie die Seite neu zu laden ...x+=d?d^2?0:-1:1
mitx+=d&1?0:1-d
undy+=d^1?d^3?0:-1:1
mity+=d&1&&2-d
.Python 2 - 123
125 133 146 148 150 154 160True
Auf Erfolg,False
auf Misserfolg.Sie müssen Eingabe wie angeben
f(b=var_containing_board)
.Lambda-Version - 154
Gibt
0
(falsy) für Fehler zurück,True
für Erfolg.Vielen Dank an Will und Brandon, dass sie die Funktion kürzer gemacht haben als das Lambda. Auch für mehr horizontales Scrollen: D
Dank an xnor für überlegenes Bit-Bashing und Logik!
Anmerkung bearbeiten: Ich bin mir ziemlich sicher, dass dies
b[y][x]
niemals ausgeführt wird, wenn der Bereich verlassen wird. Da wir uns außerhalb des Boards befinden, wird die Verlaufsprüfungs in c
durchgeführtFalse
. Dann wird die Grenzüberprüfung(x|y)&8
sein8
. Dann überprüft Python nicht einmal den letzten Wert von,==
da die ersten beiden bereits unterschiedlich sind.quelle
x|y>7or
funktioniert,x|y<0or
aber nicht ...0o
.C (GNU-C), 163 Bytes * 0,9 = 146,7
#C (GNU-C), 186 Bytes * 0,9 = 167,4Meine neue Version verwendet eine vorzeichenbehaftete statt einer vorzeichenlosen Ganzzahl. Früher hatte ich Angst vor einer Rechtsverschiebung mit Vorzeichen, aber mir wurde klar, dass das Vorzeichen das Torquadrat ist und es keine Rolle spielt, was danach passiert.
Die Funktion verwendet ein Array von Bits (wobei die Bits blockierte Quadrate darstellen) in Form einer 64-Bit-Ganzzahl. Die Bits sind so angeordnet, wie Sie ein Buch lesen würden. Es gibt -1 für einen Absturz, 0 für ewiges Fahren oder 1 für die Flucht in die rechte untere Ecke zurück.
Testprogramm
Ausgabe
Python-Array-zu-Hex-Konverter:
quelle
memset(&M,~1,8)
(15 Zeichen) durchM=~(-1ULL/255)
(14 Zeichen).P(0x00fefefefefefefe);
= (Sollte nach rechts oben, eine Umdrehung, direkt in die Ecke geschossen werden. Gleiches gilt fürP(0x00eeeeeeeeeeeeee);
(Sackgasse in der 4. Spalte). Ich glaube nicht, dass Sie diesa
anfangs zuweisen müssen .0x7f7f7f7f7f7f7f00
. Außerdem muss initialisiert werden,a
da es später nur durch ODER-Verknüpfung zusätzlicher Bits geändert wird. Daher kann ich es mir nicht leisten, zunächst ein unerwünschtes Bit zu setzen.Python,
187-213207 Zeichen, 10% Bonus für den Druckpfad
Am Testeingang findet es einen etwas anderen Pfad:
SSSSRSRSRRSSRSSRRSRSSRSSSSS
Der allgemeine Ansatz besteht darin, die Eingabe zunächst in ein Leerzeichen und ein
o
s umzuwandeln. Leerzeichen haben ein Sechseck von20
, sodass alle vier unteren Bits nicht gesetzt sind.o
hat ein Hex von6F
, so dass die niedrigen vier Bits alle gesetzt sind.Ein Rand von
o
s wird um das Board gelegt, damit wir uns keine Sorgen über schlechte Indizes machen müssen.Während wir über das Brett gehen, benutzen wir die Bits in jedem Feld, um zu sehen, ob wir von dieser Seite kommen und passieren dürfen. Auf diese Weise vermeiden wir Endlosschleifen. Es ist nicht genug, einen einzigen Booleschen Wert pro Kachel zu haben, da Ihre Austrittsrichtung von Ihrer Eintrittsrichtung abhängt, sodass Kacheln zweimal besucht werden können.
Wir führen dann eine rekursive Suche nach einem sicheren Pfad durch.
quelle
9
anstelle vonw=len(b[0])+1
usw. einen Hardcode erstellen?p==79
mitp-79
. Ich habe einen Syntaxfehler bekommen, wenn ich dies in beide Richtungen ohne Leerzeichen vor dem macheelse
. Ich denke, dieser Trick funktioniert nur mitif
.-~x
==,x+1
aber beide unären Operatoren haben eine höhere Priorität als Multiplikation, Division und Modul! So(d+1)%4
könnte es sein-~d%4
! Dies würde auch funktionieren,x-1
aber nur~-x
stattdessen verwenden.Javascript -
270 - 20% = 216262 - 20% = 210 BytesDa es mindestens eine Lösung geben sollte, die beide Boni einbringt (und nicht zu einer lächerlichen Stapeltiefe führt;) ...
Minimiert:
Erweitert:
v
ist eine Hash-Tabelle mit Schlüsseln, bei denen es sich um Zustands-Tripel handelt(x,y,d)
, die der (x, y) -Koordinate und der Eingaberichtung entsprechend
. Jedem Schlüssel ist ein Wert zugeordnet, der aus der Folge vonS
(geraden) undR
(rechten) Zügen besteht, die erforderlich sind, um den durch den Schlüssel dargestellten Zustand zu erreichen.Der Code verwaltet auch einen Stapel von Tripeln (in Variablen
n
), die noch nicht verarbeitet wurden. Der Stapel enthält anfänglich nur das Dreifache (0,0,0), entsprechend dem Zustand, in dem das Auto direkt in der Zelle (0,0) steht. In der äußeren Schleifefor( S = ... )
prüft die Routine, ob noch unverarbeitete Tripel vorhanden sind. In diesem Fall durchläuft jedes unverarbeitete Triple die innere Schleifen.map( ...
.Die innere Schleife macht fünf Dinge:
K
(steckengeblieben), da wir mindestens eine Schleife gefunden haben, in der das Auto ohne Absturz für immer kreisen kann.v
) und zum Stapel unverarbeiteter Tripel (m
) hinzugefügtv
, wird sein Wert auf den Wert des Ursprungszustandes (die Abfolge von Zügen) plusR
oderS
basierend auf dem aktuellen Zug gesetztx
undy
sind7
, wird der Wert des Ursprungszustands (die Abfolge der Bewegungen, die ausgeführt werden, um den Ursprungszustand zu erreichen) kopiertS
, da diese Bewegungsabfolge eine Lösung des Problems darstelltNachdem die innere Schleife beendet ist, wird
n
(der Stapel) durchm
(den neuen Stapel) ersetzt.Nachdem die äußere Schleife beendet wurde (es wurden keine neuen Zustände erreicht), gibt die Funktion ihre Ausgabe zurück. Wenn die (7,7) -Zelle erreicht wurde,
S
enthält sie eine Folge von Zügen, die zu dieser Zelle führen, und wird ausgegeben. Wenn die Zelle nicht erreicht wurde,S
wird die leere Zeichenfolge angezeigt, und die Routine führt zur AusgabeO
, dieK
genau dann (stecken bleibt), wenn eine Schleife gefunden wurde, oderC
(crash), wenn das Auto unweigerlich abstürzt.quelle
Python 339 - 10% = 305 Bytes
Ich habe eine rekursive Tiefensuche verwendet, die frühzeitig mit Erfolg über beendet wird
exit
. Auch drucken Weg zum Erfolg in Form von00001010101010101010101110100111001000
,0
für gerade,1
für rechts. Die Antwort wird länger als optimal sein, da es die Tiefe zuerst ist. Ich bin mir sicher, dass einige Optimierungen des Algorithmus die Anzahl der Bytes erheblich verringern könnten.quelle
a
derfor
Schleife mischen . Sie brauchen auch keine Leerzeichen um Operatoren, zB(v+1) % 4
->(v+1)%4
. Sie können auch mehrere Anweisungen in einer Zeile zusammenfassen, indem Sie verwenden,;
wenn die Zeile keinif
oderfor
usw. enthält, zc(l+"0");c(l+"1")
. Einige andere Golf spielt:x,y,v=0,0,2
,x|y>7 or x|y<0
,x==y==7
. Viel Glück :)