The Black Pawn's Revenge

Question

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----

Answer 1

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)

Answer 2

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.