Day 22: Reactor Reboot
Haskell: Part 1 (00:50:40, rank 3451), Part 2 (03:27:24, rank 2138)
Very cool puzzle that got me thinking hard about spatial relationships between cubes. A nice throwback to Conway Cubes, although not enough overlap with that puzzle that I could lift the code I wrote last year.
To start, I parsed the input a list of tuples (Bool, Region)
where Region
is a range in each axis. Next, I created a big 3D array and just brute force applied all the flips. Not too bad.
It was sort of obvious where this one was going: instead of dealing with a 50x50x50 region of space, deal with unlimited scale. This immediately ruled out the array option, so I had to figure out how to represent a set of possibly intersecting cubes and allow efficient deletes.
What I came up with in the end might not be super elegant but it worked:
- Walk the list of flips.
- For "on" flips, add the region to a list of
(xRange, yRange, zRange)
, where each range is a tuple of(minVal, maxVal)
on that axis.- I think there's a function that does this in Haskell, but I couldn't remember it so just applied min and max separately.
- For "off" flips, it gets very interesting. I sat and looked at a Rubik's cube for a while, then wrote down some equations to remove a region
d
from another regionr
by removingr
from the region list and inserting 6 new regions:- Everything in
r
to the left ofd
. - Everything in
r
to the right ofd
. - Everything in
r
aboved
and within itsx
range. - Everything in
r
belowd
and within itsx
range. - Everything in
r
in front ofd
and within itsx
andy
ranges. - Everything in
r
behindd
and within itsx
andy
ranges.
- Everything in
- Note that the delete operation needs to apply to every region in the original list since there may be multiple overlapping regions. So this could generate thousands of new subregions.
- For "on" flips, add the region to a list of
- When all flips are performed, recurse over the remaining region list and count from 0.
- If there are no more regions, return the count.
- If there's at least a region
r
:- Add its size (product of length in each dimension) to count
- Delete
r
from the region list, treating it like another "off" flip.
This worked well except I got mixed up with the recursion step and had done a fold over the original list instead, which isn't what you want, since the deletion step might completely alter the list (e.g. removing all other elements if they're contained within the deleted region). Also, it turned out I hadn't figured out the subregion generation properly in the deletion step, and was accidentally causing some of the newly generated subregions to be larger than they should.
- Thinking in 3 dimensions can be hard.