¡Tu coche solo gira a la derecha!

49

Introducción

Tienes la desgracia de estar atrapado en un automóvil fuera de control en una carrera de obstáculos. Todas las características del automóvil no responden, salvo el sistema de dirección, que está dañado. Puede conducir en línea recta o girar a la derecha. ¿Se puede guiar el automóvil hacia la seguridad?

Mecánica

Su automóvil comienza en la esquina superior izquierda de un mapa de 8x8, y está tratando de ponerse a salvo en la esquina inferior derecha. El automóvil tiene una orientación (inicialmente a la derecha), medida en incrementos de 90 grados. El automóvil puede realizar una de dos acciones:

  1. Conduzca un cuadrado hacia adelante, o
  2. Gire 90 grados en el sentido de las agujas del reloj, luego conduzca un cuadrado hacia adelante

Tenga en cuenta que el automóvil no puede girar lo suficientemente fuerte como para realizar un giro de 180 grados en una sola casilla.

Algunas de las plazas son obstáculos. Si el automóvil entra en una casilla de obstáculo, se estrella. Se supone que todo lo que está fuera del curso 8x8 es un obstáculo, por lo que salir del curso equivale a estrellarse.

El cuadrado inferior derecho es el cuadrado seguro, que permite al automóvil escapar de la carrera de obstáculos. Se supone que la casilla inicial y la casilla segura no son obstáculos.

Tarea

Debe escribir un programa o función que tome como entrada una matriz de 8x8 (matriz, lista de listas, etc.), que representa la carrera de obstáculos. El programa devuelve o imprime un booleano, o algo similarmente verdadero. Si es posible que el automóvil llegue a la plaza segura sin chocar (es decir, si el mapa tiene solución), la salida es True, de lo contrario, es False.

Puntuación

Reglas de golf de código estándar: el ganador es el código con la menor cantidad de bytes.

Bonificaciones:

  • Si, para un mapa solucionable, su código genera una serie válida de entradas del conductor que guían el automóvil hacia el cuadrado seguro, deduzca 10 puntos porcentuales de su puntaje. Un formato de salida de ejemplo podría ser SRSSR(que indica Derecho, Derecho, Derecho, Derecho, Derecho). Esta salida reemplazaría la Truesalida estándar .

  • Si, para un mapa sin solución, la salida de su código distingue entre situaciones en las que un choque es inevitable y situaciones en las que es posible conducir por la carrera de obstáculos para siempre, deduzca 10 puntos porcentuales de su puntaje. Un resultado de ejemplo podría ser Crashsi un choque es inevitable, o Stucksi el automóvil está atascado en la carrera de obstáculos para siempre. Estas salidas reemplazarían la Falsesalida estándar para un mapa insoluble.

Ejemplo

Si el programa recibe una matriz de 8x8 como esta:

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

Se interpretaría como un mapa como este, con cuadrados negros que indican obstáculos:

ingrese la descripción de la imagen aquí

Y una posible solución podría ser:

ingrese la descripción de la imagen aquí

Como existe una solución, el programa debe devolver / imprimir Truepara este mapa. La secuencia de movimientos que se muestra aquí es SSSSRSRRRSRSSRRRSSRSSS.

fosgeno
fuente
2
Escribí algunos casos de prueba increíblemente simples para Crashy Stuck. Están aquí por lo largos que son. Fila 2 llena, todo lo demás vacío -> Crash. Fila 7 llena, todo lo demás vacío ->Stuck
undergroundmonorail
3
Estoy confundido acerca de los puntos porcentuales (a diferencia de los porcentajes). Obtener cualquiera de los bonos multiplica su puntaje por 0.9. ¿Obtener ambos lo multiplica por 0.8 o 0.9 ^ 2?
undergroundmonorail
3
Claro, S y C están bien. Mis resultados fueron solo sugerencias.
fosgeno
13
"Dos errores no hacen un acierto, pero tres izquierdas sí". - Papá.
hoosierEE
2
"¡Tu coche puede hacer solo cero o tres izquierdas!"
feersum

Respuestas:

17

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

Muchas gracias a Optimizer y DocMax por sus útiles sugerencias sobre cómo mejorar este código:

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

Devuelve true(verdadero) para solucionable y false(falso) para insoluble.

Funciona solo en Firefox a partir de hoy debido a las características de JavaScript 1.7.

Tablero de prueba

mi gato y yo
fuente
1
Este es de 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).
Optimizador
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={})- Probado.
Optimizador
1
@Optimizer Todavía estoy cumpliendo para el segundo caso de prueba [[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]]. Eso debería dar falso.
Yo y mi gato
2
Esto se debe a que, xcomo yambos son globales, no puede ejecutar dos casos de prueba antes de volver a cargar la página ...
Optimizer
1
Puede guardar un total de 9 más reemplazando x+=d?d^2?0:-1:1con x+=d&1?0:1-dy y+=d^1?d^3?0:-1:1con y+=d&1&&2-d.
DocMax
10

Python 2-123 125 133 146 148 150 154 160

Trueen el éxito, Falseen el fracaso.

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

Debe proporcionar información como f(b=var_containing_board).

Versión Lambda - 154

Devoluciones 0(falsas) por fracaso, Truepor éxito.

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

Gracias a Will y Brandon por hacer la función más corta que la lambda. También para agregar más desplazamiento horizontal: D

¡Gracias a xnor por su excelente bit-bashing y lógica!

Nota de edición: estoy razonablemente seguro de que b[y][x]nunca se ejecutará cuando esté fuera de rango. Como estamos fuera del tablero, la verificación del historial s in cserá False. Entonces la verificación de límites (x|y)&8será 8. Entonces python ni siquiera verificará el último valor de ==porque los dos primeros ya son diferentes.

FryAmTheEggman
fuente
1
La versión funcional puede combinar los dos ifs que ambos regresan; como solo el retorno devuelve Ninguno, lo cual es falso, tampoco es necesario que devuelva 0.. solo devuelve el favor;)
Será el
Si voltea los cheques, puede combinar ambos ifs también
Will
¿Puedes combinar ambas declaraciones de devolución?
Brandon
1
@ Gracias, sabía que había una mejor manera de hacerlo: D Um, no pude encontrar ningún espacio para eliminar que no me causara un error de sintaxis. Realmente no entiendo por qué x|y>7orfunciona, pero x|y<0orno ...
FryAmTheEggman
1
Puede hacer un literal octal comenzando con 0o.
feersum
9

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

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

Mi nueva versión usa un entero con signo en lugar de sin signo. Anteriormente tenía miedo de firmar el desplazamiento a la derecha, pero me di cuenta de que, dado que el bit de signo es el cuadrado del gol, no importa lo que ocurra después de eso.

La función toma una matriz de bits (los que representan cuadrados bloqueados) en forma de un entero de 64 bits. Los bits están ordenados de menor a mayor importancia de la misma manera que leerías un libro. Devuelve -1 por un accidente, 0 por conducir para siempre o 1 por escapar a la esquina inferior derecha.

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

Programa de prueba

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

Salida

Escape
Stuck
Crash

Python convertidor de matriz a hexadecimal:

a2b=lambda(A):"0x%X"%sum(A[i/8][i%8]<<i for i in range(64))
Feersum
fuente
1
Reemplace memset(&M,~1,8)(15 caracteres) con M=~(-1ULL/255)(14 caracteres).
R ..
@R .. ¡Buena! -4 bytes de eso.
Feersum
2
Me gusta el formato de entrada, ¡genial!
fosgeno
Estoy obteniendo 'crash' para P(0x00fefefefefefefe);= (Debería ser un disparo directo a la esquina superior derecha, una vuelta, directamente a la esquina. Lo mismo para P(0x00eeeeeeeeeeeeee);(callejón sin salida en la cuarta columna). No creo que deba asignar ainicialmente.
@tolos Has transpuesto el orden de fila / columna principal. Para tener la fila superior y la columna derecha abiertas, debería estarlo 0x7f7f7f7f7f7f7f00. También es necesario inicializar aporque más tarde solo se modifica mediante ORing en bits adicionales, por lo que no puedo permitirme tener un conjunto de bits no deseado inicialmente.
feersum
6

Pitón, 187 213

207 caracteres, 10% de bonificación por ruta de impresión

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

En la entrada de prueba, encuentra una ruta ligeramente diferente: SSSSRSRSRRSSRSSRRSRSSRSSSSS

El enfoque general es convertir primero la entrada en espacios y os. Los espacios tienen un hexadecimal de 20, por lo que los cuatro bits inferiores no están configurados. otiene un hexadecimal de 6F, por lo que los cuatro bits bajos están todos establecidos.

Se ocoloca un borde de s alrededor del tablero para que no tengamos que preocuparnos por los malos índices.

Mientras caminamos por el tablero, usamos los bits en cada mosaico para ver si se nos permite pasar cuando venimos de ese lado. De esta manera, evitamos bucles infinitos. No es suficiente tener un solo booleano por mosaico, ya que la dirección de salida depende de la dirección de entrada, por lo que los mosaicos se pueden visitar dos veces.

Luego hacemos una búsqueda recursiva de un camino seguro.

Será
fuente
3
"Su automóvil comienza en la esquina superior izquierda de un mapa de 8x8" - ¿no puede codificar 9en lugar de w=len(b[0])+1, etc.?
FryAmTheEggman
@FryAmTheEggman gracias, ¿cómo podría haber pasado por alto eso? : D
Will
Puede revertir su declaración ternaria y reemplazar p==79con p-79. Obtuve un error de sintaxis haciendo esto en ambos sentidos sin un espacio antes delelse . Creo que ese truco solo funciona if.
FryAmTheEggman
@FryAmTheEggman Creo que la prueba de profundidad tiene que ser antes de la recurrencia? He estado jugando con una multiplicación por booleano en su lugar.
Will
77
Acabo de encontrar un truco muy bueno. ¡Probablemente sepa que -~x== x+1pero ambos operadores unarios tienen mayor prioridad que la multiplicación, división y módulo! Entonces(d+1)%4 podría ser -~d%4! Esto también funcionaría x-1pero solo se usaría ~-xen su lugar.
FryAmTheEggman
6

Javascript - 270 - 20% = 216262 - 20% = 210 bytes

Dado que debería haber al menos una solución que gane ambas bonificaciones (y no conduzca a una profundidad de pila ridícula;) ...

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

Expandido:

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

ves una tabla hash con claves que son triples de estado (x,y,d)correspondientes a (x, y) coordenadas y dirección de entrada d. Cada tecla tiene un valor asociado que es la cadena de movimientos S(rectos) y R(girar a la derecha) necesarios para alcanzar el estado representado por la tecla.

El código también mantiene una pila de triples (en variable n) que aún no se han procesado. Inicialmente, la pila contiene solo el triple (0,0,0), correspondiente al estado en el que el automóvil se enfrenta a la derecha en la celda (0,0). En el bucle externo for( S = ... ), la rutina verifica si quedan triples sin procesar. Si es así, se ejecuta cada triples sin procesar a través del bucle interno, n.map( ....

El circuito interno hace cinco cosas:

  1. calcula los dos movimientos posibles (conducir en línea recta, girar a la derecha) fuera del estado actual
  2. Si cualquiera de estos movimientos conduce a un estado ya registrado en la tabla hash, se ignora para su posterior procesamiento. KSin embargo, marcamos la salida FALSO como (atascada), ya que hemos encontrado al menos un bucle donde el automóvil puede continuar dando vueltas para siempre sin estrellarse.
  3. si un estado es legal y novedoso, se agrega a la tabla hash ( v) y a la pila de triples sin procesar ( m) para el próximo paso del bucle externo
  4. cuando el nuevo estado está registrado en v , su valor se establece en el valor del estado de origen (la secuencia de movimientos) más Ro en Sfunción del movimiento actual
  5. si xy yson7 , el valor del estado de origen (la secuencia de movimientos tomados para alcanzar el estado de origen) se copia S, ya que esta secuencia de movimiento es una solución al problema

Después de que termina el bucle interno, n (la pila) se reemplaza por m(la nueva pila).

Después de que termina el bucle externo (no se alcanzaron nuevos estados), la función devuelve su salida. Si se alcanzó la celda (7,7), Scontendrá una secuencia de movimientos que conducen a esta celda, y esto se generará. Si no se alcanzó la celda, Sserá la cadena vacía, y la rutina pasa a la salida O, que contendrá K(atascada) si y solo si se encontró un bucle, o C(choca) si el automóvil inevitablemente chocará.

COTO
fuente
1
Obtuve la confirmación de OP, puedes cambiar el nombre de 'Crash' y 'Stuck' a 'C' y 'S'.
FryAmTheEggman
Ah Eso ahorra un poco, entonces. Gracias. ;)
COTO
¿Puedes explicar qué está haciendo tu código? No puedo hacer cara o cruz.
fosgeno
@phosgene: He incluido una explicación detallada en línea.
COTO
Ese es un procedimiento inteligente. Nada se desperdicia.
fosgeno
4

Python 339 - 10% = 305 bytes

Utilicé una búsqueda recursiva de profundidad primero, que termina temprano en el éxito a través de exit. También imprime la ruta del éxito en forma de 00001010101010101010101110100111001000, 0por derecho, 1por derecho. La respuesta será más larga que la óptima, ya que es profunda primero. Estoy seguro de que algunas optimizaciones del algoritmo podrían hacer que la cuenta de bytes disminuya bastante.

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
estocástico
fuente
3
Como se trata de Python 2, puede mezclar pestañas y espacios para sangrías, como en ael forbucle. Tampoco necesita espacios alrededor de los operadores, por ejemplo, (v+1) % 4-> (v+1)%4. También puede unir varias declaraciones en una línea utilizando ;si no hay ifo for, etc. en la línea, por ejemplo c(l+"0");c(l+"1"). Algunos otros campos de golf: x,y,v=0,0,2, x|y>7 or x|y<0, x==y==7. Buena suerte :)
FryAmTheEggman