Caminos y pérdida de tiempo

22

Premisa

Tan recientemente llegué media hora antes de la cita y decidí esperar afuera. También determiné que se vería extraño si me paraba inmóvil frente a la casa. Por lo tanto, decidí hacer una caminata rápida, dentro de un área limitada. También concluí que si comenzaba a caminar en círculos, sería obvio que estaba merodeando. Así que me inspiré para crear mi primer desafío de Code Golf.

Especificación

Se le dará una lista, un mapa del área, que contendrá " "o "#", que representan espacios libres y obstáculos de algún tipo. Los espacios libres solo se pueden cruzar una vez, y se tarda 1 minuto en cruzarlos. Su posición inicial se indicará con una "@"tradición per roguelike, y el objetivo se representará con un "$"porque eso es lo que va a perder allí. También se le dará un número entero que representará la cantidad de minutos que tiene que perder antes de no parecer que estaba entrometiéndose. Cuando aterrizas en el"$", tendrá que haber sido la cantidad exacta de minutos (por lo tanto, si estaba haciendo la cuenta regresiva, tendrá que ser 1 en un mosaico adyacente y 0 en el mosaico). Siempre será posible llegar al destino. Su programa o función tendrá que devolver una lista que muestre la ruta más corta con <,>, ^ y v para representar las cuatro direcciones posibles.

Ejemplos

Entrada:

[[" ", " ", " ", " "],
 ["@", " ", " ", "$"],
 [" ", " ", " ", " "],
 [" ", " ", " ", " "]]

y

5

Ouput:

[[">", ">", ">", "v"],
 ["^", " ", " ", "$"],
 [" ", " ", " ", " "],
 [" ", " ", " ", " "]]

Entrada:

[[" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 ["@", "#", " ", "$", " "],
 [" ", " ", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

y

7

Salida:

[[" ", "#", " ", " ", " "],
 [" ", "#", ">", "v", " "],
 ["v", "#", "^", "$", " "],
 [">", ">", "^", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

Entrada:

[[" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 ["@", "#", " ", "$", " "],
 [" ", " ", " ", " ", " "],
 [" ", "#", " ", " ", " "],
 [" ", "#", " ", " ", " "]]

y

17

Salida:

[[" ", "#", " ", "v", "<"],
 [" ", "#", " ", "v", "^"],
 ["v", "#", " ", "$", "^"],
 [">", ">", "v", ">", "^"],
 [" ", "#", "v", "^", "<"],
 [" ", "#", ">", ">", "^"]]

Reglas

  • Se aplican lagunas estándar
  • Cada ficha solo debe moverse una vez
  • La cantidad exacta de tiempo debe gastarse en el tablero
  • Solo se debe mostrar una ruta en el caso de múltiples rutas
  • Esta es una pregunta de código de golf, por lo que la respuesta más corta gana
  • Según la pregunta de user202729 en los comentarios, puede asumir una entrada válida.

Agregue un comentario si se requiere alguna aclaración adicional

LForchini
fuente
1
¿Se garantiza que "siempre será posible llegar al destino en el tiempo especificado "?
user202729
Sí, siempre habrá un camino, incluso si es complicado
LForchini
55
Bienvenido a PPCG! :) Bonito primer desafío.
Giuseppe
¿Qué pasó con el medio minuto en cada extremo? (no es necesario cambiar nada si no es obvio)
Jonathan Allan

Respuestas:

6

JavaScript (ES6), 171 bytes

Toma entrada en la sintaxis de curry (a)(n). Salidas modificando la matriz de entrada.

a=>g=(n,y=a[F='findIndex'](r=>~(i=r[F](v=>v>'?'))),x=i,R=a[y])=>!n--|[-1,0,1,2].every(d=>(R[x]='<^>v'[d+1],(c=(a[Y=y+~-d%2]||0)[X=x+d%2])<1?g(n,Y,X):n|c!='$')&&(R[x]=' '))

Pruébalo en línea!

Comentado

a =>                           // a[] = input matrix
g = (                          // g = recursive function taking:
  n,                           //   n = number of remaining moves
                               //   (x, y) = current coordinates, initialized as follows:
  y = a[F = 'findIndex'](r =>  //     y = index of the row containing the starting point,
    ~(i = r[F](v => v > '?'))  //         found by iterating over all rows r until we
  ),                           //         find some i such that r[i] > '?'
  x = i,                       //     x = index of the column of the starting point
  R = a[y]                     //   R[] = current row
) =>                           //
  !n-- |                       // decrement n; force failure if we're out of moves
  [-1, 0, 1, 2].every(d =>     // for each direction d, where -1 = left, 0 = up,
    (                          // 1 = right and 2 = down:
      R[x] = '<^>v'[d + 1], (  //   update the current cell with the direction symbol
        c = (                  //   c = content of the new cell at (X, Y) with:
          a[Y = y + ~-d % 2]   //     Y = y + dy
          || 0                 //     (use a dummy value if this row does not exist)
        )[X = x + d % 2]       //     X = x + dx
      ) < 1 ?                  //   if c is a space:
        g(n, Y, X)             //     we can go on with a recursive call
      :                        //   else:
        n | c != '$'           //     return false if n = 0 and we've reached the target
    ) &&                       //   unless the above result is falsy,
    (R[x] = ' ')               //   restore the current cell to a space
  )                            // end of every()
Arnauld
fuente
5

Python 2 , 310 256 bytes

Gracias @cairdcoinheringaahing por except:0-3 bytes
Gracias @Mnemonic por -8 bytes
Gracias @JonathanAllan por -3 bytes
Gracias @ovs por -5 bytes

G,L=input()
R=[]
def S(x,y,G,c,R):
 try:
	if x>-1<y<G[y][x]in' @':i=0;exec"T=[r[:]for r in G];T[y][x]='<v^>'[i];S(x+~-i/2,y+~-(i^2)/2,T,c-1,R);i+=1;"*4
	R+=[G]*(0==c<'$'==G[y][x])
 except:0
for i,y in enumerate(G):"@"in y>S(y.index("@"),i,G,L,R)
print R[0]

Pruébalo en línea!

Alguna explicación:

try-exceptse utiliza para asegurar que tanto xy ycoordenadas se encuentran en las fronteras. Se generará una excepción al acceder a G[y][x]. Python es demasiado bueno y los índices negativos son aceptables, por lo que x>-1<yse agrega el cheque .

T=[r[:]for r in G]usado para crear copias de Gpor valores

~-i/2y ~-(i^2)/2se usan para generar pares (-1, 0), (0, 1), (0, -1), (1, 0), que solían moverse en la cuadrícula (¡todavía debería haber un camino más corto!)

R+=[G]*(0==c<'$'==G[y][x])comprobar, que '$'se alcanza en el número requerido de pasos. Rse utiliza para obtener este resultado de llamadas a funciones recursivas.

for i,y in enumerate(G):"@"in y>S(y.index("@"),i,G,L,R)Encontrado xy yde '@'entrada y función de llamada S.

print R[0] R podría contener más de una solución, por lo que la salida solo es primero

Zarigüeya muerta
fuente
-4 bytes
caird coinheringaahing
1
Puede guardar un byte reemplazándolo if G[y][x]=='$':con if'$'==G[y][x]:.
1
En realidad, toda esa condición se puede reemplazar R+=(G[y][x]=='$')*(c==0)*[G]por otro byte.
1
Huh, no estoy seguro de lo que estaba viendo. Puede guardar un par de bytes en la primera condición conif(x>-1<y)*(G[y][x]in' @'):
1
Un camino más corto para ti y+cmp(i%2,i/2)sería y+~-(i^2)/2; bien puede ser más corto aún.
Jonathan Allan
2

Python 2 , 264 261 251 249 bytes

def f(a,n,r=-1,s=0):
 j=len(a[0]);x=1;z=y=0
 if r<0:s,r=divmod(sum(a,[]).index('@'),j)
 for c in'>v<^':
	u=r+x;v=s+y;x,y=-y,x
	if j>u>-1<v<len(a):b=[e[:]for e in a];b[s][r]=c;w=a[v][u];z=n*(w<'!')and f(b,n-1,u,v)or n==1and w=='$'and b
	if z:return z

Pruébalo en línea!

Chas Brown
fuente
1
@Arnauld: ¡Vaya! Se puso un poco demasiado elegante. Fijo.
Chas Brown