Post History
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...
Answer
#7: Post edited
- ## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> <s>166</s> 142 bytes
- ```rust
- |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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=0f163f68bdd9148bb7caf1a709675799)
- 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
- ```rust
- 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, these bit shifted results (`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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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.
- ## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> <s>166</s> 142 bytes
- ```rust
- |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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=0f163f68bdd9148bb7caf1a709675799)
- 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
- ```rust
- 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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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.
#6: Post edited
- ## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> <s>166</s> 142 bytes
- ```rust
- |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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=0f163f68bdd9148bb7caf1a709675799)
- 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
- ```rust
- 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, these bit shifted results (`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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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()`.
- ## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> <s>166</s> 142 bytes
- ```rust
- |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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=0f163f68bdd9148bb7caf1a709675799)
- 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
- ```rust
- 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, these bit shifted results (`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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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.
#5: Post edited
- ## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> <s>166</s> 142 bytes
- ```rust
- |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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=dce0338bac4caff703d3f9631082a103)- 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
- ```rust
- 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, these bit shifted results (`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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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()`.
- ## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> <s>166</s> 142 bytes
- ```rust
- |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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=0f163f68bdd9148bb7caf1a709675799)
- 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
- ```rust
- 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, these bit shifted results (`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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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()`.
#4: Post edited
## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> 166 bytes- ```rust
|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()}- ```
- [All test cases on Rust Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=dce0338bac4caff703d3f9631082a103)
- 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
- ```rust
- 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, these bit shifted results (`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.- ### 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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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()}
- ```
- 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()`.
- ## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> <s>166</s> 142 bytes
- ```rust
- |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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=dce0338bac4caff703d3f9631082a103)
- 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
- ```rust
- 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, these bit shifted results (`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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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()`.
#3: Post edited
## [Rust](https://www.rust-lang.org/), <s>236</s> 184 bytes- ```rust
|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()}- ```
- [All test cases on Rust Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=dce0338bac4caff703d3f9631082a103)
- 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
- ```rust
- 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, these bit shifted results (`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.
- ### 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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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()}
- ```
- 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()`.
- ## [Rust](https://www.rust-lang.org/), <s>236</s> <s>184</s> 166 bytes
- ```rust
- |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()}
- ```
- [All test cases on Rust Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=dce0338bac4caff703d3f9631082a103)
- 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
- ```rust
- 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, these bit shifted results (`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.
- ### 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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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()}
- ```
- 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()`.
#2: Post edited
## [Rust](https://www.rust-lang.org/), 236 bytes- ```rust
|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()- ```
[All test cases on Rust Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=d3bbad94c532de2c8209dcd7ce193459)- 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
- ```rust
- 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, these bit shifted results (`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.
In the golfed version, the masks are the equivalent 64 bit unsigned integers, instead of bit strings.
- ## [Rust](https://www.rust-lang.org/), <s>236</s> 184 bytes
- ```rust
- |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()}
- ```
- [All test cases on Rust Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=dce0338bac4caff703d3f9631082a103)
- 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
- ```rust
- 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, these bit shifted results (`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.
- ### 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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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):
- ```rust
- |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()}
- ```
- 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()`.
#1: Initial revision
## [Rust](https://www.rust-lang.org/), 236 bytes ```rust |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() ``` [All test cases on Rust Playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=d3bbad94c532de2c8209dcd7ce193459) 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 ```rust 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, these bit shifted results (`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. In the golfed version, the masks are the equivalent 64 bit unsigned integers, instead of bit strings.