Skip to content
advent of code 2021

day 22

reactor reboot

approach

part 1 only cares about the region within ±50, so it toggles individual cubes in a set.

part 2 covers the whole space, so it works with boxes instead. lit space is kept as a set of non-overlapping boxes. when a new step's box overlaps a lit one, the lit box is cut into up to 26 smaller boxes around the overlap (a 3×3×3 split minus the middle), keeping the parts outside the new box. then the new box is added if the step is on. the total volume of the remaining boxes is the answer. coordinates are widened by 0.5 on each side so that inclusive integer ranges become boxes with real volume.

the trick

never store cubes; split boxes around their overlap so lit space stays a set of disjoint boxes.

python
for cc in lit.copy():
    if (r := c.remove(cc)) is not None:
        lit.remove(cc)
        lit.update(rr for rr in r[0])
if op == "on":
    lit.add(c)