10
\$\begingroup\$

The goal of this challenge is to determine if a move is a legal English Checkers move.

This challenge will use an 8x8 board. A moved piece should be treated as a man (not a king) that can only move diagonally forward. The board will have 0 or more black pieces and 1 or more white piece. One white piece will be currently moving. The white piece can "jump" over one black piece diagonally in front of it if the square directly behind it is empty. It is possible to take a further jump from that position if there is another black piece in either direction diagonally in front of it. Capture is mandatory, so it is illegal to not take a jump that is available. However, it is not mandatory to take a path that maximizes the number of jumps. Basically, this means that if you make a jump and there is another possible jump from the ending position then that move is illegal. Piece positions use the following numbering scheme:

Checkerboard numbering


Rules

Inputs:

  • A list of numbers that represent black pieces.

  • A list of numbers that represent white pieces.

  • A starting position for the white piece

  • The ending position for the white piece

Output:

  • A truthy value if the move is valid, otherwise a falsey value


You can assume a white piece will always occupy the starting position.

If convenient, you can assume that the first white piece in the white piece list will contain the starting position instead of accepting input 3.

Standard code golf rules. Fewest bytes wins.


Test Cases

To illustrate, O is the starting position, X is the ending position, B are black pieces, and W are white pieces

Black pieces: []
White pieces: [5]
Move: (5, 1)
Output: True

Single move no jump
 X _ _ _
O _ _ _ 

B: [6]
W: [9]
M: (9, 2)
O: True

Single jump
 _ X _ _
_ B _ _ 
 O _ _ _

B: [2, 6]
M: (9, 2)
O: False

Illegal ending position on top of black piece
 _ X _ _
_ B _ _ 
 O _ _ _

B: [7, 14]
W: [17]
M: (17, 3)
O: True

Double jump
 _ _ X _
_ _ B _ 
 _ _ _ _
_ B _ _ 
 O _ _ _

B: [7, 14]
M: (17, 10)
O: False

Illegal jump, must take the next jump as well
 _ _ _ _
_ _ B _ 
 _ X _ _
_ B _ _ 
 O _ _ _

B: [4]
W: [8]
M: (8, 3)
O: False

Illegal jump across the board
 _ _ _ X
B _ _ _ 
 O _ _ _


B: [6, 7]
W: [6]
M: (10, 1)
O: True

Split decision p1
 X _ _ _
_ B B _ 
 _ O _ _

B: [6, 7]
M: (10, 3)
O: True

Split decision p2
 _ _ X _
_ B B _ 
 _ O _ _


B: [2]
W: [1]
M: (1, 3)
O: False

Sideways Jump
 O B X _

B: [6]
W: [1]
M: (1, 10)
O: False

Backwards Jump
 O _ _ _
_ B _ _ 
 _ X _ _

B: [6]
W: [9, 2]
M: (9, 2)
O: False

Illegal ending position on top of white piece
 _ X _ _
_ B _ _ 
 O _ _ _

B: []
W: [9, 6]
M: (9, 2)
O: False

Illegal jump over white piece
 _ X _ _
_ W _ _ 
 O _ _ _

B: [8, 15, 23, 24]
W: [27]
M: (27, 4)
O: True


Split decision long path
 _ _ _ X
_ _ _ B 
 _ _ _ _
_ _ B _ 
 _ _ _ _
_ _ B B 
 _ _ W _

B: [8, 15, 23, 24]
W: [27]
M: (27, 20)
O: True

Split decision short path
 _ _ _ _
_ _ _ B 
 _ _ _ _
_ _ B _ 
 _ _ _ X
_ _ B B 
 _ _ W _
\$\endgroup\$
  • 3
    \$\begingroup\$ I suggest a test-case like B=[8,15,23,24];W=[27] with each of M=[27,4] and M=[27,20] 1. it will give a change of direction. 2 it will answer a question I have: are both valid or must the longer be taken? ("Capture is mandatory, so it is illegal to not take a jump that is available" kind of suggests both are valid, although I don't know why you make it illegal not to capture if possible, so maybe you mean to take as many pieces as possible?) \$\endgroup\$ – Jonathan Allan Apr 26 '18 at 7:28
  • \$\begingroup\$ Sorry I do not know how to play (English) checkers. Would you mind to adding some more details about what is a legal move. \$\endgroup\$ – tsh Apr 26 '18 at 8:29
  • 1
    \$\begingroup\$ Here is a summary of the test cases in STDIN-friendly format. \$\endgroup\$ – Arnauld Apr 26 '18 at 9:55
  • \$\begingroup\$ Capture is mandatory, so it is illegal to not take a jump that is available. what does "take a jump" mean? \$\endgroup\$ – Erik the Outgolfer Apr 26 '18 at 13:02
  • 1
    \$\begingroup\$ @JonathanAllan I think I addressed your question in the explanation and added the test cases. \$\endgroup\$ – aoemica Apr 26 '18 at 14:17
1
\$\begingroup\$

That was challenging :) * fixed bugs (added bytes)

JavaScript (Node.js), 197 193 191 185 181 186 bytes

f=(B,W,S,E,F=1)=>g(S).filter((x,i)=>B[I="includes"](x)&!B[I](t=g(x)[i])&!W[I](t)&&t>0?F+=f(B,W,t,E):0)[0]?F>1:g(S)[I](E)
g=S=>[S--,!(y=~-(e=S-3)/4%2|0)||S%4^3?y?e+1:e:0,S%4||y?y?e:e-1:0]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I think you can use >>2&1 instead of /4%2|0. \$\endgroup\$ – Arnauld Apr 26 '18 at 22:14
  • \$\begingroup\$ Testcase: [10, 3], [14], 14, 7 failed. \$\endgroup\$ – tsh Apr 27 '18 at 6:43
  • \$\begingroup\$ @tsh fixed :), if more test cases failed let me know \$\endgroup\$ – DanielIndie Apr 27 '18 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.