Comments on Knight safe squares

Parent

Knight safe squares

−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)
    
    (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.

code-golf

posted about 2 years ago

CC BY-SA 4.0

2y ago

trichoplax‭

1020 reputation 83 17 129 470

Raw

Markdown

History

is a duplicate

This question has been asked before and has already been answered. It should be marked as a duplicate.

Please enter the URL of the proposed duplicate in the details field below.

not constructive

This question cannot be answered in a way that is helpful to anyone. It's not possible to learn something from possible answers, except for the solution for the specific problem of the asker.

−0

Rust, 236 184 166 142 bytes …

1y ago

−0

APL(Dyalog Unicode), 64 bytes …

2y ago

−0

Python, 143 bytes ```python …

1y ago

1 comment thread

Input (3 comments)

Post

−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.

posted about 1 year ago

CC BY-SA 4.0

Karl Knechtel‭

31 reputation 0 3 3 2

Copy Link

Raw

Markdown

History

1 comment thread

Good news and bad news (5 comments)

trichoplax‭ wrote about 1 year ago

copy link

Input:                    0 Expected: 64 Actual: 64 
Input: 18446744073709551615 Expected:  0 Actual:  0 
Input: 12273903644374837845 Expected:  0 Actual: 14 MISMATCH
Input:  9819010546270478865 Expected: 16 Actual:  9 MISMATCH
Input:  9223372036854775808 Expected: 61 Actual: 61 
Input:   144115188075855872 Expected: 60 Actual: 60 
Input:                    4 Expected: 59 Actual: 59 
Input:                16384 Expected: 59 Actual: 59 
Input:     9007199254740992 Expected: 57 Actual: 57 
Input:       35184372088832 Expected: 55 Actual: 55 
Input:        8796361457664 Expected: 48 Actual: 48

trichoplax‭ wrote about 1 year ago

copy link

Input:       17609903308800 Expected: 36 Actual: 36 
Input: 18441077155848519679 Expected:  1 Actual:  0 MISMATCH
Input: 18440988645153550335 Expected:  2 Actual:  1 MISMATCH
Input:  9214294468855857151 Expected:  1 Actual:  1 
Input: 18300371588261871615 Expected:  1 Actual:  1 
Input: 18446744073708891899 Expected:  1 Actual:  1 
Input: 18446744071024132079 Expected:  1 Actual:  0 MISMATCH
Input:  8637754208117850111 Expected:  1 Actual:  0 MISMATCH
Input: 12643820184012849151 Expected:  1 Actual:  0 MISMATCH
Input:       35184372089472 Expected: 47 Actual: 47

Communities

Comments on Knight safe squares

Knight safe squares

Input

Output

Example

Test cases

String input test cases

Integer input test cases

1 comment thread

Python, 143 bytes

1 comment thread