# The Black Pawn's Revenge

Objective

The black pawn wants revenge. Plot out its last attack.

Rules

The black pawn (L) starts at the top row and moves downwards to the bottom row. Maximise points taken, indicating the path with X. Pawns (P) are 1, bishops (B) and knights (N) 3, rooks (R) 5, and queens (Q) 9. There won't be any kings in the input.

If there is more than one path that has the maximum amount of points, output any of those paths. There will not be any situations where the pawn cannot reach the bottom row.

Examples

Input:

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


Output:

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


Input:

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


Output:

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

• What should happen if the pawn can't reach the bottom row? – Reto Koradi Oct 17 '15 at 0:17
• Actually, the text never says that it has to reach the bottom row. Is that the intention? Say, in the second example, would it be valid for the path to stop in the 5th row, after the pawn captured the queen? – Reto Koradi Oct 17 '15 at 3:36
• @RetoKoradi Huh. I haven't actually thought of that. Yeah, the pawn should reach the bottom row. You can assume that any cases where the pawn can't reach the bottom row won't occur in the input. – absinthe Oct 17 '15 at 4:50
• And when it reaches the bottow row, it is promoted as a queen and kill everyone elese ... – coredump Oct 17 '15 at 9:16
• What about El Passant? – user54200 Jul 29 '16 at 8:59

# 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
print t[0]
s(t[1:],t[0].index('L'),1)


# Ruby 260 258 255 241 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]}


This program defines a function (s), which, given some board rows, returns the best path as a string, and the value in points of that path. s is recursive, so at each step it evaluates all possibilities and returns the best one.

Here's an online version with tests: http://ideone.com/6eMtm4

The readable version is available here: http://ideone.com/eoXUtp

All the steps I took to reduce the size of the code can be found here.