Module advent_of_code_2021::day_22 [−][src]
Expand description
This is my solution for Advent of Code - Day 22 - Reactor Reboot
Today was about toggling cubes of cells in a 3d grid. Part one limited this to a cubic volume 101 units³, but the puzzle input and description was very heavily hinting that part two was the same, but using all the data, making it vastly bigger. The program would take a long time to flip all the required bits, and likely run out of memory trying to represent each cell, so I was looking for some form of optimisation. I though about tracking for a cube which sections had been taken out / added in but that got pretty convoluted to track which cube was responsible for tracking each bit.
This meant I needed a solution that guaranteed each cell was covered by exactly one cuboid. So I decided upon when a new cube intersects with existing active (on) cubes, explode the old cubes into up to 6 pieces, (slice of x on both sides, then y on both sides, then z on both sides), so that none of them intersect with the new cube or each other. Then if the new cube is on, also add it to the list of cubes.
This could still get to a very large list of cubes, but in reality most cubes will only cause a small number to explode. The puzzle input in full mode ends up as ~3.5k cubes. The solution then becomes bounded by the relatively small number of instructions, and is independent of the grid-size, which is key to it running small and fast enough.
Cuboid is used to track each cuboid, and Instruction wraps a cuboid and whether it flips
its contents to on or off. Instruction::from parses a line of input, and parse_input
uses this to build the whole instruction list. volume_active is the entry point into the
solution for both parts. It folds each instruction into a list of ‘on’ cubes calling
merge_instruction to build each iteration from the previous iteration and the next
instruction. In turn, this uses Cuboid::diff_and_split for each existing cube, which returns
a list of cubes to add to the next generation.
For part one, the instruction list is first filtered by limit_instructions to only
the instructions with cuboids (or partial cuboids) that fit in initialisation_limit. For
part two, the unaltered instruction set is used. Both Cuboid::diff_and_split and
limit_instructions use Cuboid::intersect which returns the cuboid region where both
overlap, or None if they are disjoint.
Structs
Represents a cuboid as its range of co-ordinates on each axis. Both values are inclusive.
Represents a line of input as the Cuboid region it intersects, and whether it toggles its
contents on or off.
Functions
The initialisation phase (part_one) is limited to a cube 50 units from the origin on all axes.
Filter the list of instructions to just the region that intersects the limit Cuboid. If an
instruction’s cuboid is partially in the area, instead include a modified instruction that just
contains the intersection with the limit.
Merge an instruction into the current list of cuboids. Use Cuboid::diff_and_split to remove
the instruction’s cuboid from other cuboids it overlaps. Then if it is itself on, add the new
cuboid to the list to mark that its entire region is now active.
Parse the puzzle input as a list of instructions
The entry point for running the solutions with the ‘real’ puzzle input.
Fold the list of instructions into a list of cuboids that describe the entire active area, then sum the volumes of those cuboids to get the total active volume.