El problema del peón perdido

Después de que terminó el juego de ajedrez, un peón sobreviviente quedó detrás de las líneas enemigas. ayudémoslo a encontrar el camino más corto de regreso a casa.

El problema original describe un tablero de "ajedrez" nXn y una función f: {1,..,n-1}X{1,..,n}X{-1,0,1} => R+de pesos. el objetivo es encontrar el mejor camino desde un cuadrado en la línea inferior hasta otro cuadrado en la línea superior, donde los posibles movimientos son: izquierda, arriba, derecha, y no puedes salir del tablero.

El problema es relativamente fácil de resolver en O (n ^ 2) usando programación dinámica, pero esto es codegolf, y no nos importan las cosas inútiles como la complejidad del tiempo de ejecución ...

El problema

input: una matriz tridimensional (o alguna otra colección de su elección, recibida a través de stdin, o como argumento de función), correspondiente a un tablero de ajedrez regular, exactamente en tamaño: 7X8X3 (#linePasses X #rowSize X #movesPerPass) que contiene enteros no negativos. Los movimientos cuestan desde alguna posición (i,j)donde iestá el índice de la fila, y jes el índice de la columna, son:

• a[i][j][0]por el costo para viajar hasta-izquierda a la plaza (i+1,j-1), o gráficamente: \.
• a[i][j][1]por el costo de viajar hasta la cuadratura (i+1,j), o gráficamente: |.
• a[i][j][2]por el costo de viajar arriba-derecha a la plaza (i+1,j+1), o gráficamente: /.

puede suponer que no contendrá una ruta que sea mayor que MAX_INT.

salida: una salida ASCII 8X8 que muestra la mejor ruta (la más corta, es decir, la suma mínima de pesos) (si hay más de 1 resultado óptimo, puede mostrar una ruta arbitraria de su elección). el camino se dibuja de abajo hacia arriba, donde en cada línea, el personaje correspondiente a la posición del peón en el camino, es el que está a punto de hacer. por ejemplo, si el peón está a punto de moverse hacia la izquierda desde la columna 3 (a la columna 2), debe dibujar:

#?######
##\#####

donde ?debe ser reemplazado con el siguiente movimiento. la posición final necesita ser dibujada como X.

Ejemplos

entrada:

[
  [[1,1,1],[1,1,1],[0,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,0],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,0],[1,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
  [[1,1,1],[1,1,1],[1,1,1],[0,1,1],[1,1,1],[1,1,1],[1,1,1],[1,1,1]]
]

salida:

##X#####
###\####
###|####
###|####
##/#####
#/######
#|######
##\#####

entrada:

[
  [[41,27,38],[12,83,32],[50,53,35],[46,32,26],[55,89,82],[75,30,87],[2,11,64],[8,55,22]],
  [[56,21,0],[83,25,38],[43,75,63],[56,60,77],[68,55,89],[99,48,67],[94,30,9],[62,62,58]],
  [[23,18,40],[24,47,61],[96,45,72],[71,6,48],[75,63,98],[93,56,51],[23,31,30],[49,34,99]],
  [[20,47,42],[62,79,72],[32,28,44],[68,61,55],[62,39,57],[4,17,49],[97,85,6],[91,18,12]],
  [[51,50,11],[32,39,56],[12,82,23],[33,88,87],[60,55,22],[29,78,14],[70,11,42],[63,94,67]],
  [[75,64,60],[27,79,86],[70,72,56],[55,45,32],[95,67,12],[87,93,98],[81,36,53],[38,22,93]],
  [[31,80,50],[77,71,22],[59,46,86],[64,71,53],[41,19,95],[62,71,22],[92,80,41],[26,74,29]]
]

salida:

######X#
#####/##
####/###
#####\##
#####|##
######\#
######|#
#######\

Este es el código de golf , por lo que gana el código más corto.

juega limpio. sin lagunas ...

EDITAR:

Iv'e escribió una solución directa sin golf en scala que puedes ver. También hay un sitio que puede jugar con el código scala en línea: scalakata (solo copie y pegue la esencia en scalakata, y presione el botón de reproducción)

Q: 199 bytes

f:{m::x;n::{@/[+/-1 0 1_\:/:(x;m[y;;|!3]);0 2;(0W,),{x,0W}]};i:*<*|r:{&/n[x;y]}\[8#0;!7];  s:{-1+{*<x}'+n[y;z]}\[();(,8#0),-1_r;!7];j:i,{x+y x}\[i;|s];-1(@[8#"#";;:;]'[j;"X","/|\\"1+s'[|!7;-1_j]]);}

Notas

• Q interpreter (kx.com) gratis para uso no comercial (versiones para Windows, Linux, Mac)
• Esta solución utiliza el núcleo interno de Q (denominado internamente k4), por lo que necesitamos un archivo de secuencias de comandos con extensión k, o un intérprete interactivo en modo k (comando \ en el primer aviso). Por el contrario, la versión 'verbosa' (legible) del lenguaje requiere un script con extensión q, y es el modo predeterminado en el intérprete interactivo.

PRUEBA

f ((1 1 1; 1 1 1; 0 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 0; 1 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 1 0 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1)
   (1 1 1; 1 1 1; 1 1 1; 0 1 1; 1 1 1; 1 1 1; 1 1 1; 1 1 1))

##X#####
###\####
###|####
###|####
##/#####
#/######
#|######
##\#####

f ((41 27 38; 12 83 32; 50 53 35; 46 32 26; 55 89 82; 75 30 87;  2 11 64;  8 55 22)
   (56 21  0; 83 25 38; 43 75 63; 56 60 77; 68 55 89; 99 48 67; 94 30  9; 62 62 58)
   (23 18 40; 24 47 61; 96 45 72; 71  6 48; 75 63 98; 93 56 51; 23 31 30; 49 34 99)
   (20 47 42; 62 79 72; 32 28 44; 68 61 55; 62 39 57;  4 17 49; 97 85  6; 91 18 12)
   (51 50 11; 32 39 56; 12 82 23; 33 88 87; 60 55 22; 29 78 14; 70 11 42; 63 94 67)
   (75 64 60; 27 79 86; 70 72 56; 55 45 32; 95 67 12; 87 93 98; 81 36 53; 38 22 93)
   (31 80 50; 77 71 22; 59 46 86; 64 71 53; 41 19 95; 62 71 22; 92 80 41; 26 74 29))

######X#
#####/##
####/###
#####\##
######\#
######|#
######|#
#######\

EXPLICACIÓN

Para fines de ilustración, asumimos la segunda prueba (matriz ((41 27 38; 12 83 32; ....)

Transformamos la matriz original (m a nivel de código): en lugar de la matriz original con un triplete para cada coordenada, definimos la matriz para los desplazamientos hacia la izquierda, arriba y derecha. La matriz izquierda contiene valores 7x7 (soltamos la primera columna), la matriz Arriba 7x8 y la matriz derecha 7x7 (volcamos la última columna).

left                           up                         right
12 50 46 55 75 2  8       27 83 53 32 89 30 11 55     38 32 35 26 82 87 64
83 43 56 68 99 94 62      21 25 75 60 55 48 30 62     0  38 63 77 89 67 9 
24 96 71 75 93 23 49      18 47 45 6  63 56 31 34     40 61 72 48 98 51 30
62 32 68 62 4  97 91      47 79 28 61 39 17 85 18     42 72 44 55 57 49 6 
32 12 33 60 29 70 63      50 39 82 88 55 78 11 94     11 56 23 87 22 14 42
27 70 55 95 87 81 38      64 79 72 45 67 93 36 22     60 86 56 32 12 98 53
77 59 64 41 62 92 26      80 71 46 71 19 71 80 74     50 22 86 53 95 22 41

Para calcular la posición final, necesitamos evaluar la ruta de costo mínimo. Asumimos el costo inicial 0 0 0 0 0 0 0 0 (costo para llegar a cada columna de la primera fila) e iteramos con cada fila siguiente. En cada columna i, calculamos tres valores:

• costo del valor anterior de i + 1 más izquierda [i + 1]. Dejamos caer el primer componente del costo (desplaza y alinea las columnas para agregar) y sumamos componente a componente

• costo del valor anterior i más arriba [i]. Sumamos componente a componente

• costo del valor i-1 anterior más derecho [i-1]. Dejamos caer el último componente del costo (desplaza y alinea las columnas para agregar) y sumamos componente a componente

Para calcular el mínimo, completamos el costo izquierdo precediendo el infinito y el derecho agregando el infinito: con 3 vectores de ocho componentes, calcule el componente mínimo a componente. El valor resultante es el costo base para una nueva iteración

Para la primera iteración obtenemos valores (0W es infinito en Q)

0W 12 50 46 55 75 2  8
27 83 53 32 89 30 11 55
38 32 35 26 82 87 64 0W

y calcula el mínimo de cada columna

27 12 35 26 55 30 2 8

Después de todas las iteraciones, tenemos el costo mínimo para llegar a cada cuadrado (asumiendo la fila 0 en la parte superior, 7 en la parte inferior). Solo nos interesa la última columna, pero dibujo todos los resultados intermedios con fines ilustrativos

0   0   0   0   0   0   0   0
27  12  35  26  55  30  2   8
27  37  78  82  110 78  11  70
45  61  123 88  173 129 34  104
87  123 151 143 212 133 40  122
98  155 163 176 234 147 51  185
158 182 219 208 246 234 87  207
208 204 265 261 265 256 128 233

Ahora encontramos el valor mínimo en la última fila (128, en la columna 6). Ese es el final del camino (carácter X en salida).

Repetimos el cálculo de costos nuevamente, pero ahora anotamos la dirección desde la que obtenemos cada mínimo (de los 3 valores utilizados para calcular el mínimo es el valor seleccionado).

\|/|\///
\\\\\/|/
\\\|//|/
\\|\//|/
\\|//|\/
\\//|\|/
\|/|/|\/

Revertimos las filas, colocamos 'X' en la posición 6 y conservamos solo la ruta que termina en la columna 6 (las otras se sustituyen por #)

######X#
#####/##
####/###
#####\##
######\#
######|#
######|#
#######\