Votre voiture ne tourne que bien!

49

introduction

Vous avez le malheur d'être coincé dans une voiture en fuite sur un parcours d'obstacles. Toutes les fonctionnalités de la voiture sont non réactives, à l'exception du système de direction, qui est endommagé. Il peut rouler droit ou tourner à droite. La voiture peut-elle être guidée vers la sécurité?

Mécanique

Votre voiture commence dans le coin supérieur gauche d'une carte 8x8 et tente de se mettre en sécurité dans le coin inférieur droit. La voiture a une orientation (initialement à droite), mesurée par incréments de 90 degrés. La voiture peut effectuer l'une des deux actions suivantes:

  1. Conduire une case en avant, ou
  2. Tourner de 90 degrés dans le sens des aiguilles d'une montre, puis avancer d'un carré

Notez que la voiture est incapable de tourner suffisamment brusquement pour effectuer un virage à 180 degrés sur une seule case.

Certaines des places sont des obstacles. Si la voiture pénètre dans un obstacle, elle se bloque. Tout ce qui se trouve en dehors du parcours 8x8 est supposé être un obstacle. Par conséquent, quitter le parcours équivaut à un accident.

Le carré en bas à droite est le coffre-fort, qui permet à la voiture d'échapper au parcours du combattant. La case de départ et la case de sécurité sont supposées ne pas être des obstacles.

Tâche

Vous devez écrire un programme ou une fonction prenant en entrée un tableau 8x8 (matrice, liste de listes, etc.) représentant le parcours du combattant. Le programme retourne ou imprime un booléen, ou quelque chose de similaire. S'il est possible pour la voiture de se rendre à la case de sécurité sans se planter (c'est-à-dire si la carte est résoluble), la sortie l'est True, sinon False.

Notation

Règles de golf de code standard - le gagnant est le code avec le moins d'octets.

Bonus:

  • Si, pour une carte résoluble, votre code génère une série valide d'entrées de conducteur qui guident la voiture vers le coffre-fort, déduisez 10 points de pourcentage de votre score. Un exemple de format de sortie pourrait être SRSSR(indiquant droite, droite, droite, droite, droite). Cette sortie remplacerait la Truesortie standard .

  • Si, pour une carte insoluble, la sortie de votre code établit une distinction entre les situations dans lesquelles un accident est inévitable et les situations dans lesquelles il est possible de contourner le parcours du combattant pour toujours, déduisez 10 points de pourcentage de votre score. Un exemple de sortie pourrait être Crashsi un accident est inévitable, ou Stucksi la voiture est bloquée dans le parcours du combattant pour toujours. Ces sorties remplaceraient la Falsesortie standard pour une carte insoluble.

Exemple

Si le programme reçoit un tableau 8x8 tel que celui-ci:

[[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]]

Cela serait interprété comme une carte comme celle-ci, avec des carrés noirs indiquant les obstacles:

entrez la description de l'image ici

Et une solution possible pourrait être:

entrez la description de l'image ici

Puisqu'une solution existe, le programme doit retourner / imprimer Truepour cette carte. La séquence de mouvements illustrée ici est SSSSRSRRRSRSSRRRSSRSSS.

phosgène
la source
2
J'ai écrit des cas de test incroyablement simples pour Crashet Stuck. Ils sont ici à cause de combien de temps ils sont. Rangée 2 remplie, tout le reste vide -> Crash. Rangée 7 remplie, tout le reste vide ->Stuck
undergroundmonorail
3
Je suis confus au sujet des points de pourcentage (par opposition aux pourcentages). Obtenir l'un ou l'autre bonus multiplie votre score par 0,9. Obtenir les deux le multiplie-t-il par 0,8 ou 0,9 ^ 2?
undergroundmonorail
3
Bien sûr, S et C vont bien. Mes sorties n'étaient que des suggestions.
Phosgene
13
"Deux torts ne font pas un droit, mais trois gauches font." - Papa.
hoosierEE
2
"Votre voiture ne peut faire que zéro ou trois gauches!"
Feersum

Réponses:

17

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

Merci à Optimizer et DocMax pour leurs suggestions utiles sur la façon d’améliorer ce code:

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))

Retours true(vérité) pour résolvable et false(falsy) pour insoluble.

Fonctionne uniquement dans Firefox à partir d'aujourd'hui en raison des fonctionnalités de JavaScript 1.7.

Test Board

moi et mon chat
la source
1
C'est de 193 octets: 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).
Optimiseur
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={})- Testé.
Optimiseur
1
@Optimizer Je suis encore en train de devenir vrai pour le deuxième cas de test [[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]]. Cela devrait donner de faux.
moi et mon chat
2
En effet, depuis xet ysont globaux, vous ne pouvez pas exécuter deux cas de test avant de recharger la page ...
Optimiseur,
1
Vous pouvez économiser 9 autres en remplaçant x+=d?d^2?0:-1:1par x+=d&1?0:1-det y+=d^1?d^3?0:-1:1avec y+=d&1&&2-d.
DocMax
10

Python 2 - 123 125 133 146 148 150 154 160

Trueen cas de succès, Falseen cas d'échec.

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))

Vous devez fournir des entrées comme f(b=var_containing_board).

Version Lambda - 154

Renvoie 0(falsy) en cas d'échec, en Truecas de succès.

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]])

Merci à Will et Brandon d’avoir rendu la fonction plus courte que le lambda. Aussi pour ajouter plus de défilement horizontal: D

Merci à xnor pour son traitement et sa logique supérieurs au bit!

Edit note: Je suis raisonnablement confiant que b[y][x]ne sera jamais exécuté lorsque vous sortez de la plage. Puisque nous sommes en dehors du tableau, la vérification de l'historique le s in csera False. Ensuite, la vérification des limites (x|y)&8sera 8. Ensuite, python ne vérifiera même pas la dernière valeur de ==car les deux premières sont déjà différentes.

FryAmTheEggman
la source
1
La version fonctionnelle peut combiner les deux ifs que les deux renvoient; comme le retour seul retourne Aucun ce qui est faux, vous n'avez pas non plus besoin de retourner 0. retournez juste la faveur;)
Will
Si vous retournez les chèques, vous pouvez également combiner les deux ifs
Will
Pouvez-vous combiner les deux déclarations de retour?
Brandon
1
@Will Merci, je savais qu'il y avait une meilleure façon de le faire: D Um, je n'ai trouvé aucun espace à supprimer qui ne me cause pas d'erreur de syntaxe. Je ne comprends pas vraiment pourquoi x|y>7orfonctionne mais x|y<0orne ...
FryAmTheEggman
1
Vous pouvez créer un littéral octal commençant par 0o.
Feersum
9

C (GNU-C), 163 octets * 0.9 = 146.7

#C (GNU-C), 186 octets * 0.9 = 167.4

Ma nouvelle version utilise un entier signé plutôt que non signé. Un peu plus tôt, j'avais peur du décalage vers la droite signé, mais je me suis rendu compte que puisque le poteau de signalisation est le carré du but, peu importe ce qui se passera après.

La fonction prend un tableau de bits (ceux-ci représentent des carrés bloqués) sous la forme d'un entier de 64 bits. Les bits sont classés par ordre de signification, de la même manière que vous lisiez un livre. Il renvoie -1 en cas d’accident, 0 en cas de conduite illimitée ou 1 en cas d’évasion dans le coin inférieur droit.

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);
}

Programme de test

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;
}

Sortie

Escape
Stuck
Crash

Convertisseur tableau à hexadécimal Python:

a2b=lambda(A):"0x%X"%sum(A[i/8][i%8]<<i for i in range(64))
feersum
la source
1
Remplacez memset(&M,~1,8)(15 caractères) par M=~(-1ULL/255)(14 caractères).
R ..
@R .. Nice one! -4 octets de cela.
Feersum
2
J'aime le format d'entrée - très cool!
Phosgene
Je reçois un 'crash' pour P(0x00fefefefefefefe);= (Devrait être un coup droit en haut à droite, un tour, droit au coin. Même chose pour P(0x00eeeeeeeeeeeeee);(impasse au 4ème col). Je ne pense pas que vous deviez assigner ainitialement.
@tolos Vous avez transposé l'ordre des lignes / colonnes-majeur. Pour que la ligne du haut et la colonne de droite soient ouvertes, cela devrait être le cas 0x7f7f7f7f7f7f7f00. De plus, il est nécessaire d’initialiser acar plus tard, il n’est modifié que par ORing en bits supplémentaires, je ne peux donc pas me permettre de définir un bit indésirable au départ.
Feersum
6

Python, 187 213

207 caractères, 10% de bonus pour le chemin d'impression

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,"")

Sur l'entrée de test, il trouve un chemin légèrement différent: SSSSRSRSRRSSRSSRRSRSSRSSSSS

L’approche générale est d’abord de transformer l’entrée en espaces et os. Les espaces ont un hex de 20, les quatre bits inférieurs ne sont donc pas définis. oa un hex de 6F, alors les quatre bits bas sont tous mis.

Une bordure de os est placée autour du tableau afin que nous n'ayons pas à nous soucier des mauvais indices.

Lorsque nous marchons sur le plateau, nous utilisons les bits dans chaque tuile pour voir si nous sommes autorisés à passer lorsque nous venons de ce côté. De cette façon, nous évitons les boucles infinies. Il ne suffit pas d'avoir un seul booléen par tuile, car la direction de votre sortie dépend de la direction de votre entrée. Vous pouvez donc visiter les tuiles deux fois.

Nous effectuons ensuite une recherche récursive pour trouver un chemin sécurisé.

Volonté
la source
3
"Votre voiture commence dans le coin supérieur gauche d'une carte 8x8" - ne pouvez-vous pas coder 9en dur à la place de w=len(b[0])+1, etc.?
FryAmTheEggman
@FryAmTheEggman merci, comment aurais-je pu oublier cela? : D
Will
Vous pouvez inverser votre déclaration ternaire et remplacer p==79par p-79. J'ai eu une erreur de syntaxe en faisant cela dans les deux sens sans espace avant le else. Je pense que cette astuce ne fonctionne qu'avec if.
FryAmTheEggman
@FryAmTheEggman Je pense que le test de profondeur doit être effectué avant la recurse? J'ai plutôt joué avec une multiplication par booléen.
Will
7
Je viens de trouver un truc vraiment bien. Vous savez probablement que -~x== x+1mais les deux opérateurs unaires ont une priorité plus élevée que la multiplication, la division et le module! Alors (d+1)%4pourrait être -~d%4! Cela fonctionnerait aussi avec x-1mais utiliseriez juste à la ~-xplace.
FryAmTheEggman
6

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

Puisqu'il devrait y avoir au moins une solution qui gagne les deux bonus (et ne conduit pas à une profondeur de pile ridicule;) ...

Minified:

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;};

Étendu:

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;
};

vest une table de hachage avec des clés qui sont des triples d'état (x,y,d)correspondant à la coordonnée et à la direction d'entrée (x, y) d. Chaque clé a une valeur associée qui correspond à la chaîne de mouvements S(droits) et R(tourner à droite) requis pour atteindre l'état représenté par la clé.

Le code conserve également une pile de triples (variable n) qui n’ont pas encore été traités. La pile ne contient initialement que le triple (0,0,0), correspondant à l'état auquel la voiture fait face dans la cellule (0,0). Dans la boucle externe for( S = ... ), la routine vérifie s'il reste des triplets non traités. Si oui, il fonctionne chaque triple non traité à travers la boucle intérieure, n.map( ....

La boucle intérieure fait cinq choses:

  1. calcule les deux mouvements possibles (conduite droite, virage à droite) en dehors de l'état actuel
  2. Si l'un de ces déplacements mène à un état déjà enregistré dans la table de hachage, il est ignoré pour un traitement ultérieur. Nous signalons la sortie FALSE comme K(bloqué), car nous avons trouvé au moins une boucle dans laquelle la voiture peut continuer à tourner pour toujours sans se planter.
  3. si un état est légal et nouveau, il est ajouté à la hashtable ( v) et à la pile de triplets non traités ( m) pour le prochain passage de la boucle extérieure
  4. lorsque le nouvel état est enregistré dans v, sa valeur est définie sur la valeur de l'état d'origine (la séquence de déplacements) plus Rou Ssur la base du déplacement actuel
  5. si xet ysont 7, la valeur de l'état d'origine (la séquence de déplacements effectués pour atteindre l'état d'origine) est copiée dans S, car cette séquence de mouvements est une solution au problème

Une fois la boucle interne terminée, nla pile est remplacée par mla nouvelle pile.

Une fois la boucle externe terminée (aucun nouvel état n'a été atteint), la fonction renvoie sa sortie. Si la cellule (7,7) a été atteinte, Scontiendra une séquence de mouvements menant à cette cellule, qui sera sortie. Si la cellule n'a pas été atteinte, Sla chaîne sera vide et la routine tombera en sortie O, ce qui contiendra K(bloqué) si et seulement si une boucle a été trouvée, ou C(crash) si la voiture va inévitablement tomber en panne.

COTO
la source
1
Avec la confirmation de l'OP, vous pouvez renommer 'Crash' et 'Stuck' en 'C' et 'S'.
FryAmTheEggman
Ah Cela sauve un peu, alors. Merci. ;)
COTO
Pouvez-vous expliquer ce que fait votre code? Je ne peux pas en faire la tête ou la queue.
Phosgene
@phosgene: J'ai inclus une explication détaillée en ligne.
COTO
C'est une procédure intelligente. Rien n'est gaspillé.
Phosgene
4

Python 339 - 10% = 305 octets

J'ai utilisé une recherche en profondeur d'abord récursive, qui se termine tôt en cas de succès via exit. Aussi impression chemin sur le succès sous la forme de 00001010101010101010101110100111001000, 0pour droit, 1pour droit. La réponse sera plus longue que la meilleure, car il s'agit d'abord de la profondeur. Je suis sûr que certaines optimisations de l'algorithme pourraient réduire considérablement le compte d'octets.

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
stokastic
la source
3
Comme il s’agit de Python 2, vous pouvez mélanger des tabulations et des espaces pour les retraits, comme pour ala forboucle in . Vous n'avez également pas besoin d'espaces autour des opérateurs, par exemple (v+1) % 4-> (v+1)%4. Vous pouvez également joindre plusieurs déclarations sur une ligne en utilisant ;s'il n'y a pas de ifou for, etc. sur la ligne, par exemple c(l+"0");c(l+"1"). D'autres Golfs: x,y,v=0,0,2, x|y>7 or x|y<0, x==y==7. Bonne chance :)
FryAmTheEggman