POINTS = {
'P' => 1,
'B' => 3,
'N' => 3,
'R' => 5,
'Q' => 9
}
Result = Struct.new :points, :lines
def solve(lines, crt_pos=p)
crt_row, *next_rows = lines.map &:dup
pos = crt_pos||crt_row.index(?L)
next_row = next_rows[0]
points = POINTS[crt_row[pos]]||0
crt_row[pos] = ?X if crt_pos
unless next_row
return Result.new points, crt_row
end
next_moves = []
next_moves << solve(next_rows, pos) if next_row[pos] == ?-
next_moves << solve(next_rows, pos-1) if pos > 0 && next_row[pos-1] > ?-
next_moves << solve(next_rows, pos+1) if pos < 8 && next_row[pos+1] > ?-
# pp next_moves
best_move = next_moves.compact.max_by{ |m| m.points }
if best_move
return Result.new(best_move.points + points, crt_row + best_move.lines)
end
end
F=
->board{
solve(board.lines).lines
}
require 'minitest/autorun'
describe F do
def test_case_1
input = <<-EOS
----L---
-----P--
------P-
--R--P-Q
----P-P-
---P-P-P
--P-N---
-P------
EOS
F[input].must_equal <<-EOS
----L---
-----X--
------X-
--R--P-X
----P-X-
---P-X-P
--P-X---
-P--X---
EOS
end
def test_case_2
input = <<-EOS
--L-----
-P------
P-------
-P------
P--Q----
-P------
P-------
-P------
EOS
F[input].must_equal <<-EOS
--L-----
-PX-----
P-X-----
-PX-----
P--X----
-P-X----
P--X----
-P-X----
EOS
end
end
UE9JTlRTID0gewogICdQJyA9PiAxLCAKICAnQicgPT4gMywKICAnTicgPT4gMywKICAnUicgPT4gNSwKICAnUScgPT4gOQp9CgpSZXN1bHQgPSBTdHJ1Y3QubmV3IDpwb2ludHMsIDpsaW5lcwoKZGVmIHNvbHZlKGxpbmVzLCBjcnRfcG9zPXApCiAgY3J0X3JvdywgKm5leHRfcm93cyA9IGxpbmVzLm1hcCAmOmR1cAogIHBvcyA9IGNydF9wb3N8fGNydF9yb3cuaW5kZXgoP0wpCgogIG5leHRfcm93ID0gbmV4dF9yb3dzWzBdCgogIHBvaW50cyA9IFBPSU5UU1tjcnRfcm93W3Bvc11dfHwwCiAgY3J0X3Jvd1twb3NdID0gP1ggaWYgY3J0X3BvcwoKICB1bmxlc3MgbmV4dF9yb3cKICAgIHJldHVybiBSZXN1bHQubmV3IHBvaW50cywgY3J0X3JvdwogIGVuZAoKICBuZXh0X21vdmVzID0gW10KICBuZXh0X21vdmVzIDw8IHNvbHZlKG5leHRfcm93cywgcG9zKSBpZiBuZXh0X3Jvd1twb3NdID09ID8tCiAgbmV4dF9tb3ZlcyA8PCBzb2x2ZShuZXh0X3Jvd3MsIHBvcy0xKSBpZiBwb3MgPiAwICYmIG5leHRfcm93W3Bvcy0xXSA+ID8tCiAgbmV4dF9tb3ZlcyA8PCBzb2x2ZShuZXh0X3Jvd3MsIHBvcysxKSBpZiBwb3MgPCA4ICYmIG5leHRfcm93W3BvcysxXSA+ID8tCgogICMgcHAgbmV4dF9tb3ZlcwoKICBiZXN0X21vdmUgPSBuZXh0X21vdmVzLmNvbXBhY3QubWF4X2J5eyB8bXwgbS5wb2ludHMgfQoKICBpZiBiZXN0X21vdmUKICAgIHJldHVybiBSZXN1bHQubmV3KGJlc3RfbW92ZS5wb2ludHMgKyBwb2ludHMsIGNydF9yb3cgKyBiZXN0X21vdmUubGluZXMpCiAgZW5kCmVuZAoKRj0KLT5ib2FyZHsKICBzb2x2ZShib2FyZC5saW5lcykubGluZXMKfQoKcmVxdWlyZSAnbWluaXRlc3QvYXV0b3J1bicKCmRlc2NyaWJlIEYgZG8KICBkZWYgdGVzdF9jYXNlXzEKICAgIGlucHV0ID0gPDwtRU9TCi0tLS1MLS0tCi0tLS0tUC0tCi0tLS0tLVAtCi0tUi0tUC1RCi0tLS1QLVAtCi0tLVAtUC1QCi0tUC1OLS0tCi1QLS0tLS0tCkVPUwoKICAgIEZbaW5wdXRdLm11c3RfZXF1YWwgPDwtRU9TCi0tLS1MLS0tCi0tLS0tWC0tCi0tLS0tLVgtCi0tUi0tUC1YCi0tLS1QLVgtCi0tLVAtWC1QCi0tUC1YLS0tCi1QLS1YLS0tCkVPUwogIGVuZAoKICBkZWYgdGVzdF9jYXNlXzIKICAgIGlucHV0ID0gPDwtRU9TCi0tTC0tLS0tCi1QLS0tLS0tClAtLS0tLS0tCi1QLS0tLS0tClAtLVEtLS0tCi1QLS0tLS0tClAtLS0tLS0tCi1QLS0tLS0tCkVPUwoKICAgIEZbaW5wdXRdLm11c3RfZXF1YWwgPDwtRU9TCi0tTC0tLS0tCi1QWC0tLS0tClAtWC0tLS0tCi1QWC0tLS0tClAtLVgtLS0tCi1QLVgtLS0tClAtLVgtLS0tCi1QLVgtLS0tCkVPUwogIGVuZAoKZW5kCgo=