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.

posted about 2 years ago

CC BY-SA 4.0

Razetime‭

2870 reputation 42 65 322 83

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.

posted about 2 years ago

CC BY-SA 4.0

1y ago

trichoplax‭

1050 reputation 83 17 132 472

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 over 1 year ago

CC BY-SA 4.0

Karl Knechtel‭

31 reputation 0 3 3 2