Búsqueda de caminos de Roguelike

21

Búsqueda de caminos de Roguelike

Su tarea será, dada una matriz bidimensional de los elementos descritos a continuación, que representa una mazmorra, para generar o devolver un solo número que representa la cantidad de piezas de oro que el pícaro puede recoger sin despertar a ningún monstruo.

Los elementos de la matriz son los siguientes:

  1. Los espacios vacíos están representados por uno .o un espacio, su llamada;
  2. La posición inicial de Rogue está representada por, por supuesto @,;
  3. Una pieza de oro está representada por $;
  4. Las paredes están representadas por #;
  5. Los monstruos están representados por los personajes de la siguiente expresión regular: [a-zA-Z*&].

La matriz no debe contener ningún personaje que no esté en la lista anterior, por lo que puede suponer que cualquier cosa que no sea una pared, un espacio vacío, el pícaro o una pieza de oro es un monstruo.

Las reglas para encontrar rutas son:

  1. El pícaro solo puede caminar a través de celdas vacías o celdas que contienen oro;
  2. Se necesita un turno para moverse a una celda adyacente o diagonalmente adyacente;
  3. Recoger el oro es instantáneo;
  4. El pícaro no puede permanecer adyacente o diagonalmente adyacente a un monstruo durante más de un turno sin despertarlo, lo cual está prohibido;
  5. El pícaro puede ingresar al área de conciencia de un monstruo varias veces, el monstruo solo se despertará si el pícaro pasa dos turnos consecutivos cerca de él.

Reglas de entrada y salida

Puede obtener la entrada en cualquier formato razonable, incluida una matriz bidimensional, una matriz plana, una cadena o cualquier otra cosa. Si te facilita la vida, también puedes tomar las dimensiones de la matriz.

Está garantizado que el pícaro no estará cerca de un monstruo al principio.

Un programa completo o una función está bien.

Tanteo

Este es el , el puntaje es el recuento de bytes de su envío con menos siendo mejor.

Casos de prueba

Utilizo puntos para espacios vacíos aquí con fines de legibilidad, si así lo desea puede usar espacios (ver arriba). También tenga en cuenta que esta es una pura coincidencia de que el pícaro siempre está en la esquina superior izquierda, su código también debe manejar cualquier otra posición válida.

1)
@..
.$.
...  -> 1

Solo una prueba de cordura.

2)
@....
...g$
.....  -> 0

De nuevo, una prueba de cordura.

3)
@....
...$g
.....  -> 1

El pícaro puede agarrar el oro moviéndose desde la izquierda.

4)
@....g..
.......$
........
.....h..  -> 1

El pícaro puede zigzaguear entre los monstruos, sin quedarse nunca más de un turno cerca de cada uno.

5)
@....z..
.......$
.....b..  -> 0

Las tácticas del caso de prueba anterior no funcionan aquí: las áreas de sensibilidad del monstruo se superponen.

6)
@$#.
###$
....  -> 1

Test de sanidad.

7)
@..#..
$.$g.$
...#..  -> 2

Ídem.

8)
@#.d#$
$...##
e.....
..$...
##..$b
.#..g$  -> 3

De todo el oro aquí, solo se puede alcanzar tres de manera segura: el oro cerca de la posición inicial se puede obtener moviendo hacia abajo uno y luego nuevamente a la posición inicial. Para escapar de la esquina superior izquierda, el pícaro debe moverse diagonalmente hacia abajo-derecha dos veces. El oro en el medio no plantea ningún desafío. El oro exterior está protegido gy bpuede obtenerse moviéndose en diagonal desde el lugar a la derecha del oro central y luego hacia atrás. El resto no se puede obtener: el oro superior derecho está bloqueado por paredes, y el oro inferior derecho requiere dos turnos en áreas de sensibilidad de monstruos.

Los siguientes casos de prueba fueron generosamente donados por mbomb007.

9)
  12345678
a @....g.D
b .......$
c ......#.
d .....h..  -> 1

Este es complicado. Un camino es b4-b5-c6-b7-c8-b8(grab).

10)
  12345678
a @....g.D
b .......$
c .......#
d .....h..  -> 1

Un camino es [bc]4-c5-b6-c7-b8(grab).

11)
  12345678
a @....g.D
b ......#$
c .......#
d .....h..  -> 1

El muro adicional en realidad no cambia nada, [bc]4-c5-b6-c7-b8(grab)sigue siendo una solución.

Michail
fuente
Debe agregar un ejemplo más grande y más complejo. Además, ¿cuáles son las dimensiones mínimas y máximas de la mazmorra? ¿Es la mazmorra 1x1 @una entrada válida?
mbomb007
@ mbomb007 He agregado un nuevo ejemplo. En cuanto al tamaño de la cuadrícula, creo que limitarlo a al menos 3x3 es razonable.
Michail
@ mbomb007 ¿Te importa si edito tus ejemplos en? Ellos, una vez entendidos, muestran la lógica muy bien.
Michail
Sentirse libre. Para eso los hice. También podría notarse que rotar un caso de prueba no debería tener impacto en su resultado.
mbomb007

Respuestas:

5

Las soluciones anteriores (parte de ellas) se pueden encontrar en el contenedor de pie de página en el enlace tio (probablemente sean más legibles)

JavaScript (Node.js) , 883 436 411 360,345 311 bytes

g=>g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A
P=(g,x,y,m={},p={},I=i=9,M={})=>{if(/[.$]/.test(c=(g[y]||0)[x])){for(;i--;)if(/^[^.@$#]$/.test(C=(g[y+~-(i/3)]||0)[x+i%3-1])){if(m[C])return
M[C]=1}for(;I--;)if(!p[(X=x+~-(I/3))+","+(Y=y+I%3-1)]&&P(g,X,Y,M,{...p,[x+","+y]:1}))return 1}return c=="@"}

Pruébalo en línea!

Explantación

en lugar de pasar del jugador al efectivo, pasé del caso a la @. Creo que debería ser más rápido porque sé cuándo dejar de mirar (llegar a la @), y cuando buscas dinero en efectivo, siempre debes seguir moviéndote hasta que cubras todos los puntos (y las formas de llegar a ellos). así que el algo es bastante simple de esa manera: la función principal g.map((r,y)=>[...r].map((c,x)=>A+=c=="$"&&P(g,x,y)),A=0)|A: encontrar efectivo -> si lo encontraste -> comienza a buscar al jugador -> si lo encontraste -> el incremento A ahora vamos al buscador de rutas también conocido como P if(/[.$]/.test(c=(g[y]||[])[x]))solo verifica si la celda actual es "especial" -> si es así, queremos regresar si es un jugador. casos especiales: @ # (monstruo)

for(;i--;) if(/^[a-zA-Z*&]$/.test(C=(g[y+~-(i/3)]||0)[x+i%3-1])) -> if my neighbor is a monster {if(m[C])return false -> and it already was in the previous turn - this path is not value M[C]=1} -> if not just add it to the neighbors monsters for(;I--;) if(!p[(X=x+~-(I / 3))+","+(Y=y+I%3-1)]&&P(g,X,Y,M,{...p,[x+","+y]:1}))return true iterar vecinos de nuevo: si aún no estaba allí (p es el camino tomado), continúe el camino (llamada P)

DanielIndie
fuente
Buen golf! Algunas cosas que noté: (1) su código tiene espacios en blanco finales superfluos en las líneas 2 y 7, y la mayoría de los saltos de línea son innecesarios (solo las líneas 1 y 6 necesitan un descanso), y I / 3tiene espacio innecesario. ¡Elimina ese espacio en blanco y tu puntuación es realmente 324! (2) return true puede ser return 1(un valor de verdad) y return falsepuede ser simplemente return(implícito undefined, un valor de falsey). (3) La expresión regular ^[^.@$#]$para verificar si no hay monstruos es más corta que ^[a-zA-Z*&]$para verificar si hay monstruos. ¡Buen trabajo!
apsillers
sí, sé que puedo hacerlo mucho más corto :)
DanielIndie
@apsillers actualizados a la solución gratuita de espacios :)
DanielIndie