Twenty-two days into Advent of Code, it finally happened: I predicted what Part 2 would require! Not that I let the prediction guide me away from an overly simple Part 1 implementation, that I knew I would throw away. But I saw it coming.

Day 22's problem is basically calculating volume of a simplified version of Constructive Solid Geometry. The simplifications are that the only operators are "union" (called "on" in this puzzle) and "difference" (called "off") - no "intersection" - and space is made of integer cubes. Part 1 limits the problem further, to a small 101x101x101-cube space.

This implementation uses a map to track which cubes are on. The key
in the map is the coordinates of the cube. If the key has a value in
the map, the key is on. (I've also used the atom 'on' as the value.)
If the key does not have a value in the map, the cube is off. So,
the number of keys in the map is equivalent to the number of cubes
that are turned on (the answer to the puzzle). It just barely
handles the Part 1 space, requiring a million entries if the entire
space is lit. The reason I wrote it anyway is that I recognized the
opportunity to use list-comprehension permutation. That middle part,
where `{X,Y,Z}` comes from an `X <-` generator, and
a `Y <-` generator, and a `Z <-` generator,
automatically creates every combination of the values of the
three. It has never been what I have wanted any time I've tried to
use it, but this time, where I want the 27 individual coordinates
in `x=10..12,y=10..12,z=10..12`, it sure is neat.

"For now, ignore cubes outside this region," said Part 1. My code
did, but my eyes didn't. The instructions for the cubes outside of
the reduces space weren't just far outside, they were
also *large*. The entire initial space held just over a million
cubes. The *first* example instruction outside that space was
for 18.7 *trillion* cubes. And, as predicted, Part 2's task was
to turn on (and off) those regions as well.

So the one-element-per-coordinate solutions isn't going to work. We need to summarize a region of cubes as being "on". That's just the region from the instruction itself, until we turn part of it off. Then we need to slice out a region. In theory, this should come naturally to me, since slicing cubes into smaller cubes is a big part of what I do when I'm not coding.

Above is the high-level code. You can think of my storage as basically being nothing but "on" instructions, for only the regions that would still be turned on after any "off" instructions are processed. The number of "on" cubes is then the volume of all remaining regions.

I've chosen to handle `on` instructions by simply adding the
region to the accumulated list, and then reducing to
a `unique` set of non-overlapping regions at the end, once
all instructions have been processed. This might be a poor choice,
if the instructions happen to create a lot of small on-regions. That
last subtraction will compare a lot of regions to each other,
possibly for no reason. But, it could also be that some regions are
entirely turned off by some later instruction. In that case, we
didn't need to deduplicate that region anyway.

Space subtraction was a hard thing for me to get right. The woodworker in me wanted to make as few cuts as possible, to keep regions as large as possible. This would be a good idea for efficiency as well - the point of this rewrite was to reduce the number of things we needed to keep track of. Alas, the logic for planning large cuts kept getting too gnarly for me to feel confident in, so I came up with the following.

If the existing region is completely outside of the subtracting region, leave the existing region unmodified. If the existing region is completely within the subtracting region, remove the existing region completely. If the intersection is more complicated than either of those, split the existing region, and then reapply these rules.

How to split the region was the hard part to figure out. After
figuring out how to choose the points on each axis, I realized what
I had was this: any intersection of two rectangular solids
("cuboids" in the puzzle description) can be modeled by breaking one
of the solids into at most 27 pieces: each corner (8), each edge
between the corners (12), each face between the edges (6), and the
center (1). The `split_axis` function, and the functions it
calls, chooses the planes in which to dice a cube this way. It may
choose fewer pieces, but 27 is the simplified model. The recursive
call to `subtract` at the end of `subtract2` finds the
correct splits to dispose of. This function never recusively calls
itself more than once, because the splits are guaranteed to match
either the first or second clause.

Sidenote: I got to use the permutation list comprehension again!

This implementation can track the 590,784 on cubes from the limited region of Part 1 with only 460 elements - less than 1/1000 of the map implementation. It handles the two large regions that we ignored before, with just two more elements. Part 2 included a larger example, with more regions outside the "reboot" zone, and this implementation needs only 1311 elements to track 100x more cubes.

My full-puzzle input produces 12173 distinct regions covering about the same number of cubes turned on. Just under 3sec to do it. I'll bet there's a great implementation of this in any of the common CAD packages. I'll look in OpenSCAD's source code if I need to know it some day. For now, my own source is on github.

Categories: Development AdventOfCode

Post Copyright © 2021 Bryan Fink