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 🔒