14
0
Challenge:
Given a checkerboard, output the smallest amount of moves it would take (assuming black does not move at all) to king a red piece, if possible.
Rules:
Red's side will always be on the bottom, however their pieces may start in any row (even the king's row they need to get to). Black pieces are stationary, meaning they do not move in between red's movements, but they are removed from the board when captured. Note that pieces can start on any space on the board, including right next to each other. This is not how normal checkers is played, but your program must be able to solve these. (See input 5) However, checker pieces must only move diagonally (see input 3). Backward-capturing is allowed if the first capture is forward in the chain (see input 7).
Input:
An 8x8 checkerboard, with board spaces defined as the following characters(feel free to use alternatives as long as they're consistent):
. - Empty
R - Red piece(s)
B - Black piece(s)
Output:
The smallest number of moves it would take a red piece to be 'kinged' by entering the king's row on the top row of the board (black's side), 0 if no moves are required (a red piece started on king's row), or a negative number if it is impossible to king a red piece (ie black occupies it's entire first row).
Input 1:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .
Output 1:
7
Input 2:
. . . . . . . .
. . . . . . . .
. . . . . B . .
. . . . . . . .
. . . B . . . .
. . . . . . . .
. B . . . . . .
R . . . . . . .
Output 2:
2
Input 3:
. B . B . B . B
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .
Output 3:
-1
Input 4:
. . . . . . . R
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .
Output 4:
0
Input 5:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. B . . B . . .
B . . . . B . .
. B . B . . . .
. . B . . B . .
. . . R R . . .
Output 5:
4
Input 6:
. . . . . . . .
. . . . . . . .
. B . . . . . .
. . B . . . . .
. B . B . . . .
. . . . R . . .
. . . B . . . .
. . . . R . . .
Output 6:
2
Input 7:
. . . . . . . .
. . . . . . . .
. . B . . . . .
. . . . . . . .
. . B . . . . .
. B . B . B . .
. . . . B . . .
. . . . . R . R
Output 7:
4
Scoring:
This is code-golf, so shortest code in bytes wins.
Yodle
Posted 2016-09-26T16:17:05.947
Reputation: 2 378
1Shouldn't the second test case be 2, since you can double/triple jump? – James – 2016-09-26T16:23:05.840
Is a state array of arrays of integers as input OK? – Jonathan Allan – 2016-09-26T16:23:10.747
@DJMcMayhem Oh you're right, I totally forgot about that. I'll update the outputs appropriately. – Yodle – 2016-09-26T16:24:59.763
@JonathanAllan Yes, that is fine. – Yodle – 2016-09-26T16:25:07.170
1I added another testcase that should prove difficult. It involves multiple jumps, multiple pieces and jumping backwards in order to achieve the best possible solution. – orlp – 2016-09-26T16:44:52.620
1@orlp Hm, I was going to say none of the red pieces are allowed to move backwards since none of them are kings (hence the point of the challenge), but it appears some people play with rules where capturing backwards is allowed by non-kinged pieces if the first capture was forward. I'll add that to the rules since I was not aware of this before. – Yodle – 2016-09-26T16:50:53.473
Should Output 7 be 5 and not 4? I see the backwards capture but I don't see that it saves a move. – Greg Martin – 2016-09-26T18:16:44.010
Will there always be a solution? If the board is the initial Checkers board, and black cannot move, then there is no solution. – mbomb007 – 2016-09-26T19:01:37.190
@GregMartin No, the red piece on the right takes 2 moves, one to the left and the second to capture two pieces. The other red piece can then do a triple capture, followed by 1 more move to the last row, which results in 4 total. As a side note, the first piece also has the option to capture one more piece during the capture chain which does not effect the number of moves (but perhaps another test case could be introduced where a capture like that could actually be harmful). – Yodle – 2016-09-26T19:14:28.930
@mbomb007 No, see test case 3. If there is no solution, print out anything other than a valid answer (I assume negative number would be the easiest, but it's up to you). 0 is reserved for a red piece that already sits in the goal row (test case 4). – Yodle – 2016-09-26T19:15:45.063
1ooooooooh, you don't have to choose just one red piece, they can team up! I get it – Greg Martin – 2016-09-26T21:00:36.203