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:

Y una posible solución podría ser:

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

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

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.

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

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.

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

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