In checkers, the red pieces move down the board and the black pieces move up it, attacking foes diagonally along the way. I realize that "up" and "down" are completely relative, but work with me here.
In a local situation like the following one, where R is a red piece and B is a black piece, either player is at risk of being attacked, since red and black have met one another diagonally.
R _
_ B
The next situation, however, is a peaceful one. The two pieces have already passed one another and cannot turn backwards to attack.
B _
_ R
What would it take to write a function that scans the entire board and determines whether or not all its pieces are safe?
The board can be thought of as a non-toroidal matrix of any dimensions, but I'm using a square one here.
An enum is a decent way to differentiate between empty spaces (0), red pieces (3), and black ones (1). For any 2x2 subsection of the board
A B
C D
the program should check the values of
A - D
B - C
If either of these subtractions yields a value of 2, it means that a red piece was detected above a black piece, and that a valid attack can be formed. The board is in danger. Any other value suggests a safe arrangement.
I wrote this solution in Q rather than J. I've been reading Q for Mortals during my lunch breaks and wanted to test my knowledge. I suspect that the code here is still not quite idiomatic.
I started out with four 4x4 test boards: two unsafe ones in opposite directions, and two safe ones—the last of which is quite crowded.
unsafe1:4 4#0 3 0 0 0 0 1 0
unsafe2:4 4#0 3 0 0 1 0 0 0
safe1:4 4#0 1 0 0 0 0 3 0 0 0 0 3 0 0 0 1
safe2:4 4#0 1 0 0 3 0 3 0 0 0 1 0 1 3 1 1
unsafe1
0 3 0 0
0 0 1 0
0 3 0 0
0 0 1 0
unsafe2
0 3 0 0
1 0 0 0
0 3 0 0
1 0 0 0
safe1
0 1 0 0
0 0 3 0
0 0 0 3
0 0 0 1
safe2
0 1 0 0
3 0 3 0
0 0 1 0
1 3 1 1
The easiest way to compare two pieces is to have them right next to one another. If all diagonal stretches were isolated into rows, then it'd be easy to perform the aforementioned subtractions across them in a simple fold operation. My first instinct was to rotate each row n of the matrix n times to coerce the diagonals into columns, but this had the effect of wrapping attacks around the board, like a game of Asteroids. The solution wound up being a bit more complex.
The cartesian product of a matrix's top-level shape contains the indices of each one of its values.
{c:n cross n:til count x}[unsafe2]
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
Summing these addresses reveals which diagonal row they are in. A 4x4 matrix has 7 diagonals.
{(sum')c:n cross n:til count x}[unsafe2]
0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6
These indices can be grouped together, then released as a two-dimensional list.
{value group(sum')c:n cross n:til count x}[unsafe2]
,0
1 4
2 5 8
3 6 9 12
7 10 13
11 14
,15
Mapping the cartesian product back across this list gives the 2D indices needed to address each diagonal stretch in the original matrix.
diagonal:{c value group(sum')c:n cross n:til count x}
diagonal[unsafe2]
,0 0
(0 1;1 0)
(0 2;1 1;2 0)
(0 3;1 2;2 1;3 0)
(1 3;2 2;3 1)
(2 3;3 2)
,3 3
Applying the matrix to this diagonal map requires a nested each right operation.
unsafe2 ./:/:diagonal[unsafe2]
,0
3 1
0 0 0
0 0 3 1
0 0 0
0 0
,0
For sequential positions x and y, just check for 2=x-y. If x itself is 2, that means a dangerous situation has already been encountered and should be propagated.
danger:{$[2=x;x;$[2=x-y;2;y]]}
In action
(danger/) 0 0 1 3 0 1 3
3
(danger/) 0 0 3 1 0 1 3
2
Checking the whole board means
danger over every diagonal row.This is expressed in the following function.
safe:{not any 2=(danger/')((reverse each x)./:/:d),x ./:/:d:diagonal x}
Notice how unsafe1 appears safe if only its primary diagonals are isolated.
{x ./:/:diagonal x}[unsafe1]
,0
3 0
0 0 0
0 1 3 0
0 0 0
0 1
,0
But danger rears its head when the rows are reversed.
{((reverse each x)./:/:d),x ./:/:d:diagonal x}[unsafe1]
,0
0 0
3 1 0
0 0 0 0
0 3 1
0 0
,0
,0
3 0
0 0 0
0 1 3 0
0 0 0
0 1
,0
Folding danger over each row gives an array of threatened diagonals.
{(danger/')((reverse each x)./:/:d),x ./:/:d:diagonal x}[unsafe1]
0 0 2 0 2 0 0 0 0 0 0 0 1 0
And the board is unsafe, of course, because a 2 exists in this array.
{not any 2=(danger/')((reverse each x)./:/:d),x ./:/:d:diagonal x}[unsafe1]
0b
We can see that the other boards return their expected results.
safe unsafe2
0b
safe safe1
1b
safe safe2
1b
Writing this solution in Q was fun. Since I couldn't use any of J's funky combinators I might actually be able to read this a week from now.