Module day22 

Sporifica Virus

Part two is made faster by a factor of two by packing 4 nodes into each byte using 2 bits per node. Then multiple steps are memoized for each of the 256 possible states, for each of the 4 positions and each of the 4 directions, for a total of 4,096 combinations. This allows us to skip forward up to 8 steps at a time. For example:

. = Clean   # = Infected   F = Flagged   W = Weakened

State    Direction    Steps    Infected
[W] #    Down         0        0
 F  W

 #  #    Down         1        1
[F] W

[#] #    Up           2        1
 .  W

 F [#]   Right        3        1
 .  W

 F  F    Down         4        1
 . [W]

 F  F    Down         5        2
 .  #
   [ ]

Starting in the top-left corner facing down, after 5 steps the virus carrier leaves the 2x2 block having infected 2 nodes. This is memoized as:

[0][2][01111001] => (2, 5, 10001111)

Constants

CENTER 🔒

HALF 🔒

SIZE 🔒

Functions

compute_block 🔒

Computes the number of steps taken, infected nodes and next location for 2 x 2 blocks of nodes.

parse

part1

Direct implementation on a fixed-size grid.

part2

Use a compressed grid where each byte stores 4 cells (2x2 block) with 2 bits per cell.

step 🔒

Process a single step in any arbitrary location on the grid.