Module aoc::year2020::day17

Conway Cubes

Solving this problem reveals an interesting insight that the active cells are very sparse. Of the total possible volume of the cube formed by the maximum extents in part one, only roughly 8% is active and of the hypercube from part two only 3% is active for my input.

To speed things up our high level strategy will flip from a “pull” model where we check the surroundings neighbors of each cell, to a “push” model where we update the neighbors of each active cell instead.

A HashSet is generally a good choice for very sparse infinite grids, however for this problem we’ll pack all dimensions into a single vec to achieve a five times increase in lookup speed.

Modules

• size
  x and y dimensions are in the plane of the input. Each dimension can expand at most two in each axis per round (one positive and one negative). Adding padding at the edges to avoid boundary checks gives a maximum width of 8 + 2 * (6 + 1) = 22 for the x and y dimensions and 1 + 2 * (6 + 1) = 15 for the z and w dimensions.
• stride
  Pack a four dimensional array into a one dimensional vec to avoid the speed penalty of following multiple pointers and increase memory locality for caching.

Functions

• boot_process 🔒
  Re-use logic between both parts.
• parse
  Use our utility Grid method to parse the input.
• part1
  Part one cells form a cube.
• part2
  Part two form a hypercube.