Resuelve un laberinto de hielo

Los laberintos de hielo han sido uno de mis productos favoritos de los juegos Pokémon desde su debut en Pokémon Oro y Plata. Su tarea será hacer un programa que resuelva este tipo de problemas.

Los laberintos de hielo consisten principalmente, como su nombre lo indica, en hielo. Una vez que el jugador se mueve en una dirección sobre hielo, continuará moviéndose en esa dirección hasta que choque con algún obstáculo. También hay tierra que se puede mover libremente y evitará que cualquier jugador se mueva sobre ella. El último obstáculo es la piedra. La piedra no puede ocupar el mismo espacio que el jugador y si el jugador intenta moverse hacia ella, dejará de moverse antes de que pueda.

Recibirá un contenedor bidimensional de valores, como una lista de listas o una cadena separada por nuevas líneas, que contiene 3 valores distintos para cada uno de los 3 tipos de pisos (Hielo, Suelo y Piedra). También recibirá dos pares (u otros contenedores de dos valores equivalentes) que indican una coordenada de inicio y meta en el laberinto. Estos pueden ser cero o uno indexado.

Debe generar una lista de movimientos (4 valores distintos con una biyección en N, E, S, W) que causarían que el jugador llegue al final cuando se lleva a cabo.

La entrada siempre tendrá un perímetro cerrado de piedra alrededor del laberinto para que no tenga que preocuparse de que el jugador salga del laberinto.

Este es el código de golf, por lo que gana la menor cantidad de bytes

Casos de prueba

Aquí .representará el hielo, ~representará el suelo y Orepresentará una piedra. Las coordenadas son 1 indexadas. Cada letra en la solución representa la dirección que comienza con esa letra (por ejemplo, NNorte)

Entrada

OOOOO
OO.OO
O...O
OOOOO

Start : 3,3
End   : 3,2

Salida

Entrada

OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO

Start : 15,12
End   : 16,8

Salida

N,W,N,E,N,E,S,W,N,W,S,E,S,E,N,E,N

Entrada

OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO

Start : 2,2
End   : 14,3

Salida

E,S,S,W,N,E,N

Entrada

OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO

Start : 2,2
End   : 11,11

Salida

E,E,E,E,E,S,S,E,N,W,S,E,N,N,N

code-golf grid path-finding maze Asistente de trigo
fuente

¿La entrada siempre tendrá al menos una solución válida?

Pavel

@Pavel Puede suponer que sí.

Wheat Wizard

¿Son los casos de prueba (fila, columna) o (columna, fila)? 1 o 0 indexado? ¿Los bordes del tablero cuentan como paredes?

MildlyMilquetoast

Relacionado

Peter Taylor

@busukxuan Puedes quedar atrapado permanentemente en el laberinto (ver caso de prueba 1)

Wheat Wizard

Respuestas:

Mathematica, 247 bytes

(p=x#[[##&@@x]];m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};e=Flatten[Table[#->c,{c,a@#}]&/@g,1];Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]])&

Con saltos de línea:

(
p=x#[[##&@@x]];
m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];
g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];
a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};
e=Flatten[Table[#->c,{c,a@#}]&/@g,1];
Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]
)&

Mi idea inmediata fue representar las posiciones de hielo y tierra como nodos en un gráfico con bordes dirigidos correspondientes a movimientos legales, luego usar FindPath. Uno podría pensar que determinar los movimientos legales sería la parte fácil y encontrar la solución sería la parte difícil. Para mí fue todo lo contrario. Abierto a sugerencias sobre cómo calcular los bordes.

El primer argumento #es una matriz 2D donde 0representa hielo, 1tierra y 2piedra.

El segundo argumento #2y el tercer argumento #3son los puntos inicial y final, respectivamente, en la forma {row,column}.

es el carácter de uso privado de 3 bytes que U+F4A1representa \[Function].

Explicación

p=x#[[##&@@x]];

Define una función pque toma una lista xde la forma {row,column}y las salidas #[[row,column]]; es decir, el valor de hielo / suelo / piedra en esa coordenada.

m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c]

Define una función mque toma una posición inicial cy un vector de dirección vy determina recursivamente dónde terminaría. Si c+ves hielo, entonces continuamos deslizándonos desde ese punto, por lo que vuelve m[c+v,v]. Si c+ves tierra, entonces nos movemos c+vy nos detenemos. De lo contrario (si c+ves piedra o está fuera de límites), no te mueves. Tenga en cuenta que esto solo debe utilizarse en posiciones de hielo o tierra.

g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];

Define la lista gde posiciones de hielo y suelo ( pvalor menor que 2).

a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};

Define una función aque toma una posición de partida cy devuelve los resultados de moverse en las {1,0}, {-1,0}, {0,1}, y {0,-1}direcciones. Puede haber algo de redundancia. Nuevamente, esto supone que ccorresponde al hielo o al suelo.

e=Flatten[Table[#->c,{c,a@#}]&/@g,1];

Define la lista ede aristas dirigidas que representan movimientos legales. Para cada posición #en g, calcular la tabla de bordes #->cpara cada cen a@#. Luego, como terminaremos con una sublista para cada posición #, aplanaré el primer nivel. Puede haber algunos bucles y múltiples aristas.

Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]

Graph[e]es el gráfico donde los nodos son las posiciones legales (hielo o tierra) y los bordes representan movimientos legales (posiblemente chocando contra una piedra y sin moverse). Luego usamos FindPathpara encontrar una ruta desde #2a #3representada como una lista de nodos. Como FindPathpuede tomar argumentos adicionales para encontrar más de una ruta, el resultado será en realidad una lista que contiene una sola ruta, así que tomo el primer elemento usando [[1]]. Luego tomo las sucesivas Differencescoordenadas y Normalizeellas. Así, arriba es {-1,0}, abajo es {1,0}, derecha es {0,1}e izquierda es {0,-1}.

Casos de prueba

ngenisis
fuente

JavaScript (ES6) 180 183

(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

Usando un BFS , como hice para resolver este desafío relacionado

Entrada
El mapa del laberinto es una cadena multilínea, que usa Oo 0para piedra, 8para tierra y cualquier dígito distinto de cero menor que 8 para hielo (se 7ve bien).
Las posiciones de inicio y fin están basadas en cero.

Salida
Una lista de desplazamiento, donde -1 es W, 1 es E, negativo menor que -1 es Ny un positivo mayor que 1 esS

Menos golf

(m,[x,y],[t,u])=>{
  o=~m.search`\n`
  s=[[x-y*o,[]]]
  k=[]
  for(i=0; [p,l]=s[i++], k[p]=1, t-u*o != p;)
  {
    [-1,o,1,-o].map(d=>(
      M=p=>+m[p+=d] ? m[p]<8 ? M(p) : p : p-d,
      q=M(p),
      k[q]||s.push([q,[...l,d]])
    ))
  }
  return l
}

Prueba

Solve=
(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

function Go(maze) {
  var map = maze.textContent;
  var [sx,sy, dx,dy] = map.match(/\d+/g)
  --sx, --sy // zero based
  --dx, --dy // zero based
  map = map.split('\n').slice(1).join('\n') // remove first line
  var result = Solve(map.replace(/\./g, 7).replace(/~/g, 8), [sx,sy], [dx,dy])
  S.textContent = result
  Animate(maze, map, result, sx, sy)
}

function Display(maze, map, pos) {
  var row0 = maze.textContent.split('\n')[0]
  map = [...map]
  map[pos] = '☻'
  maze.textContent = row0+'\n'+map.join('')
}

function Animate(maze, map, moves, x, y) {
  console.log('A',moves)
  var offset = map.search('\n')+1
  var curPos = x + offset * y
  var curMove = 0
  var step = _ => {
    Display(maze, map, curPos)
    if (curMove < moves.length) 
    {
      curPos += moves[curMove]
      if (map[curPos] == 'O')
      {
        curPos -= moves[curMove]
        ++curMove
      }  
      else 
      {
        if (map[curPos] == '~') {
          ++curMove
        }
      }
      setTimeout(step, 100)
    }
    else
      setTimeout(_=>Display(maze,map,-1),500)
  }
  step()
}

td { 
  border: 1px solid #888;
}

Select maze<pre id=S></pre>
<table cellspacing=5><tr>
<td valign=top><input type=radio name=R onclick='Go(M1)'><br>
<pre id=M1>3,3 to 3,2  
OOOOO
OO.OO
O...O
OOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M2)'><br>
<pre id=M2>15,12 to 16,8
OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M3)'><br>
<pre id=M3>2,2 to 14,3
OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M4)'><br>
<pre id=M4>2,2 to 11,11
OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO</pre></td>
</tr></table>

Expandir fragmento

edc65
fuente