Knight safe squares
Given a chess board with some knights on it, say how many squares are neither attacked by a knight nor containing a knight.
Input
 An 8 by 8 grid where each square is either a knight or empty
 The input can contain any number of knights from 0 to 64
 You may choose to take input with any 2 distinct characters (or numbers or Booleans  there is no restriction to string input) representing a knight and an empty square
 You may take input in the format of your choice provided it does not provide additional information that would help solve the challenge
 For example, if you find it more convenient you could take input as a single 64 bit integer, where each bit is 1 for a knight and 0 for an empty square
Output
 A number from 0 to 64, indicating the number of squares that satisfy both of:
 The square does not contain a knight
 The square is not a knight's move away from a knight.
A knight's move is either of:
2 squares horizontally (left or right) and 1 square vertically (up or down)

1 square horizontally (left or right) and 2 squares vertically (up or down)
(thanks to Wikipedia)

Example
The following example input has knights represented by N
and empty squares represented by *
.
********
********
**N*****
********
********
********
******N*
N*******
Here it is again with attacked empty squares marked as a
. The required output is the number of remaining squares (the number of squares still showing *
).
*a*a****
a***a***
**N*****
a***a***
*a*a*a*a
*a**a***
**a***N*
N***a***
So for this example, the output would be 47
.
Test cases
String input test cases
Test case inputs are given as 8 strings of 8 characters, followed by the output as an integer. Knights are represented by N
and empty squares are represented by *
.
[
[
"********",
"********",
"********",
"********",
"********",
"********",
"********",
"********",
],
64
],
[
[
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
],
0
],
[
[
"N*N*N*N*",
"*N*N*N*N",
"N*N*N*N*",
"*N*N*N*N",
"N*N*N*N*",
"*N*N*N*N",
"N*N*N*N*",
"*N*N*N*N",
],
0
],
[
[
"N***N***",
"*N***N**",
"**N***N*",
"***N***N",
"N***N***",
"*N***N**",
"**N***N*",
"***N***N",
],
16
],
[
[
"N*******",
"********",
"********",
"********",
"********",
"********",
"********",
"********",
],
61
],
[
[
"******N*",
"********",
"********",
"********",
"********",
"********",
"********",
"********",
],
60
],
[
[
"********",
"********",
"********",
"********",
"********",
"********",
"********",
"*****N**",
],
59
],
[
[
"********",
"********",
"********",
"********",
"********",
"********",
"*N******",
"********",
],
59
],
[
[
"********",
"**N*****",
"********",
"********",
"********",
"********",
"********",
"********",
],
57
],
[
[
"********",
"********",
"**N*****",
"********",
"********",
"********",
"********",
"********",
],
55
],
[
[
"********",
"********",
"****N***",
"********",
"***N****",
"********",
"********",
"********",
],
48
],
[
[
"********",
"********",
"***N****",
"*****N**",
"**N*****",
"****N***",
"********",
"********",
],
36
],
[
[
"NNNNNNNN",
"NNN*N*NN",
"NN*NNN*N",
"NNNN*NNN",
"NN*NNN*N",
"NNN*N*NN",
"NNNNNNNN",
"NNNNNNNN",
],
1
],
[
[
"NNNNNNNN",
"NNN*N*NN",
"N***NN*N",
"*NNN*NNN",
"NN*NNN*N",
"*NN***NN",
"N*N*NNNN",
"NNNNNNNN",
],
2
],
[
[
"*NNNNNNN",
"NN*NNNNN",
"N*NNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
],
1
],
[
[
"NNNNNN*N",
"NNNN*NNN",
"NNNNN*N*",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
],
1
],
[
[
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNN*N*N",
"NNN*NNN*",
"NNNNN*NN",
],
1
],
[
[
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"*N*NNNNN",
"NNN*NNNN",
"N*NNNNNN",
"NNN*NNNN",
],
1
],
[
[
"*NNN*NNN",
"NN*NNNNN",
"*NNN*NNN",
"N*N*NNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
],
1
],
[
[
"N*N*NNNN",
"*NNN*NNN",
"NN*NNNNN",
"*NNN*NNN",
"N*N*NNNN",
"NNNNNNNN",
"NNNNNNNN",
"NNNNNNNN",
],
1
],
[
[
"********",
"********",
"**N*****",
"********",
"********",
"********",
"******N*",
"N*******",
],
47
]
Integer input test cases
If you choose to take input as a 64 bit unsigned integer, with each square being represented by a single bit, these are the equivalent of the test cases shown above, but with integer input.
Input which treats 1
bits as knights will be called one_knight_input, and input which treats 0
bits as knights will be called zero_knight_input. Since both of these are valid input types, both are included in the test cases so you can choose which to use.
Each test case is in the format one_knight_input : zero_knight_input : output
.
0 : 18446744073709551615 : 64
18446744073709551615 : 0 : 0
12273903644374837845 : 6172840429334713770 : 0
9819010546270478865 : 8627733527439072750 : 16
9223372036854775808 : 9223372036854775807 : 61
144115188075855872 : 18302628885633695743 : 60
4 : 18446744073709551611 : 59
16384 : 18446744073709535231 : 59
9007199254740992 : 18437736874454810623 : 57
35184372088832 : 18446708889337462783 : 55
8796361457664 : 18446735277348093951 : 48
17609903308800 : 18446726463806242815 : 36
18441077155848519679 : 5666917861031936 : 1
18440988645153550335 : 5755428556001280 : 2
9214294468855857151 : 9232449604853694464 : 1
18300371588261871615 : 146372485447680000 : 1
18446744073708891899 : 659716 : 1
18446744071024132079 : 2685419536 : 1
8637754208117850111 : 9808989865591701504 : 1
12643820184012849151 : 5802923889696702464 : 1
35184372089472 : 18446708889337462143 : 47
Explanations are optional, but I'm more likely to upvote answers that have one.
Rust, 236 184 166 142 bytes …
8mo ago
APL(Dyalog Unicode), 64 bytes …
1y ago
Python, 143 bytes ```python …
6mo ago
3 answers
Rust, 236 184 166 142 bytes
i:u64{let s=0x101010101010101;let(a,b,c,d)=(i&252*s,i&254*s,i&127*s,i&63*s);(ia<<6b<<15c<<17d<<10d>>6c>>15b>>17a>>10).count_zeros()}
All test cases on Rust Playground
Takes input as a 64 bit unsigned integer where each 1bit represents a knight and each 0bit represents an empty square.
Ungolfed version
let knight_safe_squares = input_integer: u64 {
// Moves in direction (2, 1)
let mask = u64::from_str_radix("\
00000000\
11111100\
11111100\
11111100\
11111100\
11111100\
11111100\
11111100\
", 2).unwrap();
let pieces_to_move = input_integer & mask;
let moved1 = pieces_to_move << 6;
// Moves in direction (1, 2)
let mask = u64::from_str_radix("\
00000000\
00000000\
11111110\
11111110\
11111110\
11111110\
11111110\
11111110\
", 2).unwrap();
let pieces_to_move = input_integer & mask;
let moved2 = pieces_to_move << 15;
// Moves in direction (1, 2)
let mask = u64::from_str_radix("\
00000000\
00000000\
01111111\
01111111\
01111111\
01111111\
01111111\
01111111\
", 2).unwrap();
let pieces_to_move = input_integer & mask;
let moved3 = pieces_to_move << 17;
// Moves in direction (2, 1)
let mask = u64::from_str_radix("\
00000000\
00111111\
00111111\
00111111\
00111111\
00111111\
00111111\
00111111\
", 2).unwrap();
let pieces_to_move = input_integer & mask;
let moved4 = pieces_to_move << 10;
// Moves in direction (2, 1)
let mask = u64::from_str_radix("\
00111111\
00111111\
00111111\
00111111\
00111111\
00111111\
00111111\
00000000\
", 2).unwrap();
let pieces_to_move = input_integer & mask;
let moved5 = pieces_to_move >> 6;
// Moves in direction (1, 2)
let mask = u64::from_str_radix("\
01111111\
01111111\
01111111\
01111111\
01111111\
01111111\
00000000\
00000000\
", 2).unwrap();
let pieces_to_move = input_integer & mask;
let moved6 = pieces_to_move >> 15;
// Moves in direction (1, 2)
let mask = u64::from_str_radix("\
11111110\
11111110\
11111110\
11111110\
11111110\
11111110\
00000000\
00000000\
", 2).unwrap();
let pieces_to_move = input_integer & mask;
let moved7 = pieces_to_move >> 17;
// Moves in direction (2, 1)
let mask = u64::from_str_radix("\
11111100\
11111100\
11111100\
11111100\
11111100\
11111100\
11111100\
00000000\
", 2).unwrap();
let pieces_to_move = input_integer & mask;
let moved8 = pieces_to_move >> 10;
(input_integer  moved1  moved2  moved3  moved4  moved5  moved6  moved7  moved8).count_zeros()
};
Explanation
For each of the 8 directions in which a knight can potentially move, the input integer is bit shifted by the appropriate number of places to take each bit to the destination position of a knight moving in that particular direction. This would take some knights wrapping over the edge of the board, and others off the board altogether. These knights are first removed by a bitwise AND with a mask that has 0bits at these problematic positions. There is a different mask for each direction, each with 0bits for the knights that are not permitted to move in that direction.
Now for each of the 8 directions in which a knight can potentially move, the corresponding bit shifted result (moved1
to moved8
in the ungolfed version) has 1bits in each of the destination positions that the knights in the input would end up in the respective direction.
The bitwise OR of the input (the starting positions of the knights) with all 8 of the potential moved positions leaves a 1bit in every position that is either a knight or the result of a legal move for one of those knights.
The output is the number of 0bits in this final bit string, using count_zeros()
.
Golfing steps
In the golfed version, the masks are the equivalent 64 bit unsigned integers, instead of bit strings. Initially it looked like this (236 bytes):
i:u64(i(i&71209857637481724)<<6(i&280371153272574)<<15(i&140185576636287)<<17(i&17802464409370431)<<10(i&4557430888798830336)>>6(i&9187201950435704832)>>15(i&18374403900871409664)>>17(i&18229723555195321344)>>10).count_zeros()
Then the decimal literals were replaced with hexadecimal literals, which turn out a little shorter for each of the 8 directions (226 bytes):
i:u64(i(i&0xfcfcfcfcfcfcfc)<<6(i&0xfefefefefefe)<<15(i&0x7f7f7f7f7f7f)<<17(i&0x3f3f3f3f3f3f3f)<<10(i&0x3f3f3f3f3f3f3f00)>>6(i&0x7f7f7f7f7f7f0000)>>15(i&0xfefefefefefe0000)>>17(i&0xfcfcfcfcfcfcfc00)>>10).count_zeros()
Then seeing all the repetition between the hexadecimal literals led to extracting the common parts (197 bytes):
i:u64{let(a,b,c,d)=(0xfcfcfcfcfcfcfc,0xfefefefefefe,0x7f7f7f7f7f7f,0x3f3f3f3f3f3f3f);(i(i&a)<<6(i&b)<<15(i&c)<<17(i&d)<<10(i&d<<8)>>6(i&c<<16)>>15(i&b<<16)>>17(i&a<<8)>>10).count_zeros()}
Extracting the repetition within the hexadecimal literals required 2 new literals as the repetition is not identical for all (some have a pair of digits repeated 6 times, others 7 times). This was achieved by creating the longer one (s
) and then bit shifting it to give the shorter one (t
) (194 bytes):
i:u64{let s=0x1010101010101;let t=s>>8;let(a,b,c,d)=(0xfc*s,0xfe*t,0x7f*t,0x3f*s);(i(i&a)<<6(i&b)<<15(i&c)<<17(i&d)<<10(i&d<<8)>>6(i&c<<16)>>15(i&b<<16)>>17(i&a<<8)>>10).count_zeros()}
Since t
is only used twice, it turns out to be shorter to just use s>>8
inline (189 bytes):
i:u64{let s=0x1010101010101;let(a,b,c,d)=(0xfc*s,0xfe*s>>8,0x7f*s>>8,0x3f*s);(i(i&a)<<6(i&b)<<15(i&c)<<17(i&d)<<10(i&d<<8)>>6(i&c<<16)>>15(i&b<<16)>>17(i&a<<8)>>10).count_zeros()}
Now that the hexadecimal literals are mostly down to 2 digits each, it becomes shorter to mostly go back to using decimal and avoid the 0x
prefixes (184 bytes):
i:u64{let s=0x1010101010101;let(a,b,c,d)=(252*s,254*s>>8,127*s>>8,63*s);(i(i&a)<<6(i&b)<<15(i&c)<<17(i&d)<<10(i&d<<8)>>6(i&c<<16)>>15(i&b<<16)>>17(i&a<<8)>>10).count_zeros()}
The bitmasks are excluding knights that would otherwise wrap around to the other side of the board, or drop off the board altogether. I don't know why I previously thought dropping off the top or bottom of the board (the end of the bit string) would be a problem. It doesn't leave a knight in a position that is not a valid move, so it doesn't affect the output and there is no need to mask it out. This means all of the bitmasks can have every row identical with no need for zeros at the top or bottom  only the zeros at the left and right are important.
Now instead of needing to have hexadecimal strings with 6 or 7 repetitions of pairs of digits, and having to bitshift to adjust, they can just all have 8 repetitions. This avoids the need to bitshift to adjust the size of the mask, and also avoids the need to bitshift to position the mask vertically for knight moves that involve upwards and downwards components (166 bytes):
i:u64{let s=0x101010101010101;let(a,b,c,d)=(252*s,254*s,127*s,63*s);(i(i&a)<<6(i&b)<<15(i&c)<<17(i&d)<<10(i&d)>>6(i&c)>>15(i&b)>>17(i&a)>>10).count_zeros()}
Now that the bitmasks are in 4 matching pairs that do not need to be adjusted, they can be applied just once each rather than twice, by applying them at the point a, b, c, and d are assigned. This halves the number of &
s needed, and also removes the need for most of the parentheses (142 bytes):
i:u64{let s=0x101010101010101;let(a,b,c,d)=(i&252*s,i&254*s,i&127*s,i&63*s);(ia<<6b<<15c<<17d<<10d>>6c>>15b>>17a>>10).count_zeros()}
I'm still left with the nagging thought that one more byte might be able to be saved by representing knights with 0bits instead of 1bits, allowing the use of count_ones()
instead of count_zeros()
, but I'm fairly sure that would cost more bytes overall due to needing to mask off all the 0bits that get brought onto the board each bitshift (since they would now represent knights). So I'm pretty sure this is as short as I can get.
0 comment threads
APL(Dyalog Unicode), ^{}64 bytes ^{SBCS}
{64≢∪x,u/⍨∧/¨(>∘0∧<∘9)u←⊃,/(a/⍨2+/¨a←,∘.,⍨1 2,1 2)∘+∘⊂¨x←⍸⍵}
A dfn which takes a boolean grid.
0 comment threads
Python, 143 bytes
def r(i):
y,z=65537,1+(1<<32);s=257*y*z;n=(i(i&252*s)*y>>10(i&254*s)*z>>17(i&127*s)*z>>15(i&63*s)*y>>6)&(1<<64)1
return 64n.bit_count()
This is a port of trichoplax's Rust answer, written with relatively little comprehension. Because Python's integers are arbitrary sized, they cannot implicitly cut off bits above the least significant 64 bits (so we must explicitly mask the value afterwards); however, this also means that shifts beyond that point will preserve bits, which allows refactoring some pairs of shifts as a multiplication (which now cannot overflow) and shift. Since it's now required to multiply by some numbers that are factors of the magic constant s
(equal to 0x1010101010101
), it's now computed as a product of those factors. Python's integer type does not provide a method to count clear bits, but it does provide a method to count set bits.
Because of the need to assign and remember multiple values in order, this won't work directly as a lambda
; using the :=
operator is complex and seems unlikely to offer a net improvement.
1 comment thread