Ihr Auto biegt nur rechts ab!

49

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:

  1. Fahren Sie ein Quadrat vorwärts oder
  2. 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 ersetzen True.

  • 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, Crashwenn ein Crash unvermeidbar ist oder Stuckdas Auto für immer im Hindernisparcours steckt. Diese Ausgaben würden die Standardausgabe Falsefü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:

Bildbeschreibung hier eingeben

Und eine mögliche Lösung könnte sein:

Bildbeschreibung hier eingeben

Da es eine Lösung gibt, sollte das Programm Truediese Karte zurückgeben / drucken . Die hier gezeigte Abfolge von Zügen ist SSSSRSRRRSRSSRRRSSRSSS.

Phosgen
quelle
2
Ich habe einige unglaublich einfache Testfälle für Crashund geschrieben Stuck. Sie sind hier, weil sie so lang sind. Zeile 2 gefüllt, alles andere leer -> Crash. Zeile 7 gefüllt, alles andere leer ->Stuck
U-Bahn
3
Ich bin über Prozentsatz verwirrt Punkte (im Gegensatz zu Prozente gegenüber ). Wenn Sie einen dieser Boni erhalten, multiplizieren Sie Ihre Punktzahl mit 0,9. Multipliziert sich beides mit 0,8 oder 0,9 ^ 2?
Undergroundmonorail
3
Sicher, S und C sind in Ordnung. Meine Ausgaben waren nur Vorschläge.
Phosgen
13
"Zwei Fehler machen kein Recht, aber drei Linke." - Papa.
hoosierEE
2
"Ihr Auto kann nur null oder drei Links machen!"
Feersum

Antworten:

17

JavaScript (ES6) - 122 124 148 162 172 178 187 190 193 208 Bytes

Vielen Dank an Optimizer und DocMax für hilfreiche Vorschläge zur Verbesserung dieses Codes:

F=a=>(D=(x,y,d)=>!D[i=[x,y,d]]&&(D[i]=1,x-=~d%2,y-=~-~d%2,x*y==49||!((x|y)&8||a[y][x])&&(D(x,y,d)||D(x,y,~-d%4))),D(-1,0))

Gibt true(wahr) für lösbar und false(falsch) für unlösbar zurück.

Funktioniert ab heute nur in Firefox, da JavaScript 1.7 unterstützt wird.

Test Board

Ich und meine Katze
quelle
1
Das ist 193 Bytes: 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).
Optimierer
1
172: 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.
Optimierer
1
@Optimizer Für den zweiten Testfall werde ich immer noch wahr [[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.
Ich und meine Katze
2
Das ist , weil da xund ysind beide Globals, können Sie nicht zwei Testfälle laufen , bevor Sie die Seite neu zu laden ...
Optimizer
1
Sie können durch das Ersetzen insgesamt 9 mehr sparen x+=d?d^2?0:-1:1mit x+=d&1?0:1-dund y+=d^1?d^3?0:-1:1mit y+=d&1&&2-d.
DocMax
10

Python 2 - 123 125 133 146 148 150 154 160

TrueAuf Erfolg, Falseauf Misserfolg.

def f(h=1,v=0,b=0,x=0,y=0,c=[]):s=x,y,h,v;a=b,x+h,y+v,c+[s];return(s in c)==(x|y)&8==b[y][x]<(x&y>6or f(h,v,*a)|f(-v,h,*a))

Sie müssen Eingabe wie angeben f(b=var_containing_board).

Lambda-Version - 154

Gibt 0(falsy) für Fehler zurück, Truefür Erfolg.

F=lambda b,x=0,y=0,h=1,v=0,c=[]:0if[x,y,h,v]in c or x|y>7or x|y<0 or b[y][x]else x&y==7or F(b,x+h,y+v,h,v,c+[[x,y,h,v]])or F(b,x+h,y+v,-v,h,c+[[x,y,h,v]])

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üfung s in cdurchgeführt False. Dann wird die Grenzüberprüfung (x|y)&8sein 8. Dann überprüft Python nicht einmal den letzten Wert von, ==da die ersten beiden bereits unterschiedlich sind.

FryAmTheEggman
quelle
1
Die funktionale Version kann die beiden ifs kombinieren, die beide zurückgeben. als Rückkehr allein kehrt Keine, die falsch ist, müssen Sie auch nicht 0 zurückgeben.. nur die Gunst erwidern;)
Will
Wenn du die Schecks
Will
Können Sie beide return-Anweisungen kombinieren?
Brandon
1
@Will Danke, ich wusste, dass es einen besseren Weg gibt, das zu tun: D Ähm, ich konnte keine Leerzeichen zum Entfernen finden, die keinen Syntaxfehler verursachen. Ich verstehe nicht wirklich, warum x|y>7orfunktioniert, x|y<0oraber nicht ...
FryAmTheEggman
1
Sie können ein Oktal-Literal erstellen, das mit beginnt 0o.
Feersum
9

C (GNU-C), 163 Bytes * 0,9 = 146,7

#C (GNU-C), 186 Bytes * 0,9 = 167,4

Meine 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.

g(long long o) {
    typeof(o) a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;
    for( ;i--;d = D<<8&~o)
        a |= D = d|r,
        r = (r|u)*2&~M&~o,
        u = (u|l)>>8&~o,
        l = ((l|d)&~M)/2&~o;
    return a<0?:-!(d|r|u|l);
}

Testprogramm

f(long long o){typeof(o)a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;for(;i--;d=D<<8&~o)a|=D=d|r,r=(r|u)*2&~M&~o,u=(u|l)>>8&~o,l=((l|d)&~M)/2&~o;return a<0?:-!(d|r|u|l);}
{
    char* s[] = {"Crash", "Stuck", "Escape"};
    #define P(x) puts(s[f(x)+1])
    L ex = 0x4640500C0A034020;
    P(ex);
    L blocked = 0x4040404040404040;
    P(blocked);

    L dead = 0x10002;
    P(dead);

    return 0;
}

Ausgabe

Escape
Stuck
Crash

Python-Array-zu-Hex-Konverter:

a2b=lambda(A):"0x%X"%sum(A[i/8][i%8]<<i for i in range(64))
Feersum
quelle
1
Ersetzen Sie memset(&M,~1,8)(15 Zeichen) durch M=~(-1ULL/255)(14 Zeichen).
R ..
@ R .. Schöne! -4 Bytes davon.
Feersum
2
Ich mag das Eingabeformat - sehr cool!
Phosgen
Ich bekomme 'Absturz' für P(0x00fefefefefefefe);= (Sollte nach rechts oben, eine Umdrehung, direkt in die Ecke geschossen werden. Gleiches gilt für P(0x00eeeeeeeeeeeeee);(Sackgasse in der 4. Spalte). Ich glaube nicht, dass Sie dies aanfangs zuweisen müssen .
@tolos Sie haben die Zeilen- / Spalten-Hauptreihenfolge vertauscht. Damit die obere Reihe und die rechte Spalte geöffnet sind, sollte dies der Fall sein 0x7f7f7f7f7f7f7f00. Außerdem muss initialisiert werden, ada 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.
Feersum
6

Python, 187-213

207 Zeichen, 10% Bonus für den Druckpfad

b=map(ord," "*9+" ".join("".join("o "[i]for i in j)for j in input())+" "*9)
def r(p,d,s):
 p+=(1,9,-1,-9)[d]
 if b[p]&1<<d:b[p]^=1<<d;return(s+"S")*(p==79)or r(p,d,s+"S")or r(p,(d+1)%4,s+"R")
print r(8,0,"")

Am Testeingang findet es einen etwas anderen Pfad: SSSSRSRSRRSSRSSRRSRSSRSSSSS

Der allgemeine Ansatz besteht darin, die Eingabe zunächst in ein Leerzeichen und ein os umzuwandeln. Leerzeichen haben ein Sechseck von 20, sodass alle vier unteren Bits nicht gesetzt sind. ohat ein Hex von 6F, so dass die niedrigen vier Bits alle gesetzt sind.

Ein Rand von os 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.

Wille
quelle
3
"Ihr Auto beginnt in der oberen linken Ecke einer 8x8-Karte" - können Sie nicht 9anstelle von w=len(b[0])+1usw. einen Hardcode erstellen?
FryAmTheEggman
@FryAmTheEggman danke, wie hätte ich das übersehen können? : D
Will
Sie können Ihre ternäre Aussage umkehren und ersetzen p==79mit p-79. Ich habe einen Syntaxfehler bekommen, wenn ich dies in beide Richtungen ohne Leerzeichen vor dem mache else. Ich denke, dieser Trick funktioniert nur mit if.
FryAmTheEggman
@FryAmTheEggman Ich denke, der Tiefentest muss vor dem Rückgriff erfolgen? Ich habe stattdessen mit einer Multiplikation mit dem Booleschen Wert gespielt.
Wird
7
Ich habe gerade einen wirklich tollen Trick gefunden. Sie wissen wahrscheinlich, dass -~x==, x+1aber beide unären Operatoren haben eine höhere Priorität als Multiplikation, Division und Modul! So (d+1)%4könnte es sein -~d%4! Dies würde auch funktionieren, x-1aber nur ~-xstattdessen verwenden.
FryAmTheEggman
6

Javascript - 270 - 20% = 216 262 - 20% = 210 Bytes

Da es mindestens eine Lösung geben sollte, die beide Boni einbringt (und nicht zu einer lächerlichen Stapeltiefe führt;) ...

Minimiert:

V=I=>{n=[N=[0,0,0]];v={};v[N]='';O='C';for(S='';n[0];){m=[];n.map(h=>{[x,y,d]=h;D=i=>[1,0,-1,0][d+i&3];p=v[h];for(j=2;j--;){O=v[c=[X=x+D(j),Y=y+D(3-3*j)),d+j&3]]?'K':O;J=X|Y;J<0||J>7||I[Y][X]||v[c]?O:(m.push(c),v[c]=p+'SR'[j])}S=(x&y)>6?p:S});n=m;}return S||O;};

Erweitert:

V = I => {
    n = [N=[0,0,0]];
    v = {};
    v[N] = '';
    O = 'C';

    for( S = ''; n[0]; ) {
        m = [];
        n.map( h => {
            [x,y,d] = h;
            D = i => [1,0,-1,0][d+i&3];
            p = v[h];
            for( j = 2; j--; ) {
                O = v[c = [X = x+D(j),Y = y+D(3-3*j),d+j&3]] ? 'K' : O;
                J = X|Y;
                J<0 || J>7 || I[Y][X] || v[c] ? O : (
                    m.push( c ),
                    v[c] = p + 'SR'[j]
                );
            }

            S = (x&y) > 6 ? p : S;
        } );
        n = m;
    }
    return S || O;
};

vist 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 entsprechen d. Jedem Schlüssel ist ein Wert zugeordnet, der aus der Folge von S(geraden) und R(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 Schleife for( S = ... )prüft die Routine, ob noch unverarbeitete Tripel vorhanden sind. In diesem Fall durchläuft jedes unverarbeitete Triple die innere Schleife n.map( ....

Die innere Schleife macht fünf Dinge:

  1. berechnet die zwei möglichen Bewegungen (geradeaus fahren, rechts abbiegen) aus dem aktuellen Zustand
  2. Wenn einer dieser Schritte zu einem Zustand führt, der bereits in der Hash-Tabelle registriert ist, wird er für die weitere Verarbeitung ignoriert. Wir kennzeichnen die FALSE-Ausgabe jedoch als K(steckengeblieben), da wir mindestens eine Schleife gefunden haben, in der das Auto ohne Absturz für immer kreisen kann.
  3. Wenn ein Staat legal und neu ist, wird er für den nächsten Durchgang der äußeren Schleife zur Hashtabelle ( v) und zum Stapel unverarbeiteter Tripel ( m) hinzugefügt
  4. Wenn der neue Zustand registriert wird v, wird sein Wert auf den Wert des Ursprungszustandes (die Abfolge von Zügen) plus Roder Sbasierend auf dem aktuellen Zug gesetzt
  5. wenn xund ysind 7, wird der Wert des Ursprungszustands (die Abfolge der Bewegungen, die ausgeführt werden, um den Ursprungszustand zu erreichen) kopiert S, da diese Bewegungsabfolge eine Lösung des Problems darstellt

Nachdem die innere Schleife beendet ist, wird n(der Stapel) durch m(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, Senthält sie eine Folge von Zügen, die zu dieser Zelle führen, und wird ausgegeben. Wenn die Zelle nicht erreicht wurde, Swird die leere Zeichenfolge angezeigt, und die Routine führt zur Ausgabe O, die Kgenau dann (stecken bleibt), wenn eine Schleife gefunden wurde, oder C(crash), wenn das Auto unweigerlich abstürzt.

COTO
quelle
1
Nachdem Sie die Bestätigung von OP erhalten haben, können Sie "Crash" und "Stuck" in "C" und "S" umbenennen.
FryAmTheEggman
Ah. Das spart dann ein bisschen. Vielen Dank. ;)
COTO
Können Sie erklären, was Ihr Code tut? Ich kann keine Köpfe oder Schwänze daraus machen.
Phosgen
@phosgene: Ich habe eine ausführliche Erklärung inline eingefügt.
COTO
Das ist eine clevere Vorgehensweise. Nichts wird verschwendet.
Phosgen
4

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 von 00001010101010101010101110100111001000, 0für gerade, 1fü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.

b=input()
D=[(-1,0),(0,-1),(1,0),(0,1)]
def a(l):
 x,y=0,0
 v=2
 for d in l:
  if d=='1':v=(v+1) % 4
  x+=D[v][0]
  y+=D[v][1]
  if x<0 or x>7 or y<0 or y>7:return 0,x,y
  if b[y][x]:return -1,x,y
 return 1,x,y
def c(l):
 if len(l) < 39:
  t,x,y=a(l)
  if t==1:
   if (x,y)==(7,7):
    print l;exit(0)
   c(l+"0")
   c(l+"1")
c("")
print 0
stokastisch
quelle
3
Da dies Python 2 ist, können Sie Tabulatoren und Leerzeichen für Einzüge wie in ader forSchleife 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 kein ifoder forusw. enthält, z c(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 :)
FryAmTheEggman