Communities

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

Post History

60%
+1 −0
Challenges Knight safe squares

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

posted 1y ago by trichoplax‭  ·  edited 9mo ago by trichoplax‭

Answer
#7: Post edited by user avatar trichoplax‭ · 2023-07-14T11:36:27Z (9 months ago)
Reword awkward sentence
  • ## [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 by user avatar trichoplax‭ · 2022-11-04T02:19:22Z (over 1 year ago)
Conclude switching to 0-bits for knights would be longer
  • ## [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 by user avatar trichoplax‭ · 2022-11-03T20:28:56Z (over 1 year ago)
Forgot to update Rust Playground link
  • ## [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 by user avatar trichoplax‭ · 2022-11-03T20:22:15Z (over 1 year ago)
Combine bitmask pairs into single applications
  • ## [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 by user avatar trichoplax‭ · 2022-11-03T15:55:36Z (over 1 year ago)
No need to stop knights moving off the top of bottom of the board, only the sides
  • ## [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 by user avatar trichoplax‭ · 2022-11-01T02:35:52Z (over 1 year ago)
Further golfing
  • ## [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 by user avatar trichoplax‭ · 2022-10-31T05:42:21Z (over 1 year ago)
## [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.