Module aoc::year2021::day25

Sea Cucumber

To speed things up we compute an entire row at a time for each direction, storing across and down sea cucumbers as bits in a 256 bit wide variable.

For example ...>>>>>... is represented as 00011111000. To compute the movement the steps are:

• Rotate right by one 00001111100
• Invert existing cucumbers 11100000111
• Bitwise AND together to find cucumbers that can move 00000000100
• Rotate 00000001000 left by one, invert 11111110111 then bitwise AND with original cucumbers to remove moving cucumbers from static 00011110000
• Finally bitwise OR static and moving cucumbers together for the final result 00011110000 | 00000000100 = 00011110100

In the actual implementation across and down are stored separately so that we know which cucumbers turn it is to move. We bitwise OR both together to calculate any blockers.

Structs

• State
• U256
  Duct tape two u128 together to make a 256 bit wide integer.

Functions

• parse
  Parse the sea cucumbers as individual bits into separate across and down arrays.
• part1
• part2