La venganza del peón negro

Objetivo

El peón negro quiere venganza. Trazar su último ataque.

Reglas

El peón negro ( L) comienza en la fila superior y se mueve hacia abajo a la fila inferior. Maximice los puntos tomados, indicando el camino con X. Los peones ( P) son 1, obispos ( B) y caballeros ( N) 3, torres ( R) 5 y reinas ( Q) 9. No habrá reyes en la entrada.

Si hay más de una ruta que tiene la cantidad máxima de puntos, envíe cualquiera de esas rutas. No habrá situaciones en las que el peón no pueda alcanzar la fila inferior.

Ejemplos

Entrada:

----L---
-----P--
------P-
--R--P-Q
----P-P-
---P-P-P
--P-N---
-P------

Salida:

----L---
-----X--
------X-
--R--P-X
----P-X-
---P-X-P
--P-X---
-P--X---

Entrada:

--L-----
-P------
P-------
-P------
P--Q----
-P------
P-------
-P------

Salida:

--L-----
-PX-----
P-X-----
-PX-----
P--X----
-P-X----
P--X----
-P-X----

code-golf graph-theory path-finding chess Ajenjo
fuente

¿Qué debería pasar si el peón no puede llegar a la fila inferior?

Reto Koradi

En realidad, el texto nunca dice que tiene que llegar a la fila inferior. ¿Esa es la intención? Digamos, en el segundo ejemplo, ¿sería válido que el camino se detuviera en la quinta fila, después de que el peón capturara a la reina?

Reto Koradi

@RetoKoradi Huh. En realidad no he pensado en eso. Sí, el peón debería llegar a la fila inferior. Puede suponer que cualquier caso en el que el peón no pueda alcanzar la fila inferior no ocurrirá en la entrada.

ajenjo

Y cuando llega a la fila de bottow, se promociona como una reina y mata a todos los enemigos ...

coredump

¿Qué hay de El Passant?

Respuestas:

Python, 332

def s(m,l,p):
 if not m:return 1
 b=m[0]+'-';z=filter(lambda i:(b[i]=='-')==(i==l),[l,l-1,l+1])
 if not z:return 0
 g=lambda i:s(m[1:],i,0)+[0,1,3,3,5,9]['-PBNRQ'.index(b[i])];i=max(z,key=g)
 if p:print m[0][:i]+'X'+m[0][i+1:];s(m[1:],i,p)
 return g(i)
import sys
t=sys.stdin.read().split('\n')
print t[0]
s(t[1:],t[0].index('L'),1)

caja de cartón
fuente

Rubí 260258255241 236 222

->b{s=->l,w=p{c,*x=l.map &:dup
v=[1,3,3,5,9,0]['PBNRQ'.index(c[y=w||c.index(?L)])||5]
w&&c[y]=?X
(n=x[0])?(m=[]
[y-1,y,y+1].map{|z|(z==y)^(n[z]>?.)&&m<<s[x,z]}
q,r=m.max_by{|m|m ?m[0]:0}
q&&[q+v,c+r]):[v,c]}
s[b.lines][1]}

Este programa define una función ( s), que, dadas algunas filas del tablero, devuelve la mejor ruta como una cadena y el valor en puntos de esa ruta. ses recursivo, por lo que en cada paso evalúa todas las posibilidades y devuelve la mejor.

Aquí hay una versión en línea con pruebas: http://ideone.com/6eMtm4

La versión legible está disponible aquí: http://ideone.com/eoXUtp

Todos los pasos que tomé para reducir el tamaño del código se pueden encontrar aquí .

Cristian Lupascu
fuente