Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Challenges

Knight safe squares

+4
−0

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)

        Knight's moves shown as dots
        (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.

History
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

1 comment thread

Input (3 comments)

3 answers

+1
−0

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);(i|a<<6|b<<15|c<<17|d<<10|d>>6|c>>15|b>>17|a>>10).count_zeros()}

All test cases on Rust Playground

Takes input as a 64 bit unsigned integer where each 1-bit represents a knight and each 0-bit 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 0-bits at these problematic positions. There is a different mask for each direction, each with 0-bits 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 1-bits 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 1-bit 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 0-bits 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);(i|a<<6|b<<15|c<<17|d<<10|d>>6|c>>15|b>>17|a>>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 0-bits instead of 1-bits, 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 0-bits 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.

History
Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+1
−0

APL(Dyalog Unicode), 64 bytes SBCS

{64-≢∪x,u/⍨∧/¨(>∘0∧<∘9)u←⊃,/(a/⍨2|+/¨|a←,∘.,⍨1 2,-1 2)∘+∘⊂¨x←⍸⍵}

Try it on APLgolf!

A dfn which takes a boolean grid.

History
Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+0
−0

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 64-n.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.

History
Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment thread

Good news and bad news (5 comments)

Sign up to answer this question »