Day 22 was one where a bit of investigation around the subject paid off.
Sweep algorithms
My original thought was to maintain the property that each voxel could be a member of at most one active cuboid. That would mean, at the end, I only had to add up the volumes of all the remaining cuboids. If two cuboids intersected, I would split the existing cuboid into (up to) 27 cuboids and remove the fragments that were entirely contained within the new cuboid. (There was also going to be some faffing around with removing zero-volume cuboids.) That would have worked, but there were a lot of fiddly cases to take care of.
As I was looking into how to find intersections of cuboids, I came across the idea of sweep line algorithms, and realised those would solve all my problems!
In this case, I don't bother keeping track of intersecting cuboids. All I need to keep track of is the order of application of cuboids, and the value of a voxel is the value of the most recent cuboid that contains it.
I loop through all the x values. For each x, I find the cuboids that contain that x value. Then, for each y, I filter the remaining cuboids to retain only those that contain the y value. Then, for each z, I can determine the value of each voxel.
In other words, I sweep some y-z planes across the values of x. For each of those planes, I sweep some z lines for each value of y.
The clever part is how those scans are optimised, to avoid doing repeated work that I know is redundant. That's easier to explain with some diagrams.
The diagrams below show two slices through the space in the first example in the puzzle description. They only include the cuboids that intersect the y-z plane that that x value.
Starting with the x=10 slice, I only need to consider y positions where the collection of cuboids changes. If we consider the y=12 row, the only z positions to worry about are z=10 and z=13. At z=10, the voxel is on, and I know that state will continue until the next interesting position (z=13), so there are 3 on voxels in this region. Similarly, for x=10, y=11, the interesting z positions are 9, 10, 12, and 13. Once I've established that z=10 is off, I don't need to check z=11.
Similarly, for x=11, y=12 (on the right hand diagram), I need to investigate z positions 10, 11, 13, and 14. Once I get to z=11, I know that nothing could happen until the underlying orange cuboid ends.
Most of these examples, the small cuboids mean that I end up examining most of the voxels individually. But when the cuboids get larger, I can skip more voxels as the sets of cuboids remains constant.
Data structure and utility functions
The basic data structures for cuboids are fairly direct translations from the problem. A Cuboid is a record of bounds, parity, and time (the order in which it was applied. Note that I'm using lenses for this, as there are some reasonably verbose chains of accessors to get to parts of this structure.
type Coord = V3 Int
data Parity = On | Off deriving (Eq, Ord, Show)
data Cuboid = Cuboid
{ _bounds :: (Coord, Coord)
, _parity :: Parity
, _time :: Int
}
deriving (Ord, Eq, Show)
makeLenses ''Cuboid
There are a few utility functions to help the sweeping. straddles takes a lens (an axis) and a value, and returns all cuboids that contain that value on that axis. events takes some cuboids and an axis, and returns the positions of interest for the sweep to investigate. Finally, isActive returns whether a voxel is active.
straddles :: (Lens' (V3 Int) Int) -> Int -> Cuboid -> Bool
straddles f here cuboid =
((cuboid ^. bounds . _1 . f) <= here) && ((cuboid ^. bounds . _2 . f) >= here)
events :: (Lens' (V3 Int) Int) -> [Cuboid] -> [Int]
events f cuboids = nub $ sort $ ls ++ hs
where ls = map (^. bounds . _1 . f) cuboids
hs = map ((+1) . (^. bounds . _2 . f)) cuboids
isActive :: [Cuboid] -> Bool
isActive [] = False
isActive cs = ((last scs) ^. parity) == On
where scs = sortOn (^. time) cs
Sweeping
Sweeping in each dimension is the same. (I could probably combine the functions with some higher-order trickery, but I think it's probably clearer to keep them separate.)
I'll start with the z sweep. Assuming we're working with a given x and y, and are given only the cuboids that straddle both those coordinates. I find the events, pair them up into regions, then find out how long each region is. segmentSize does the length calculation, returning 0 if that region was most recently turned off.
-- assume for a given x and y.
sweepZ :: [Cuboid] -> Int
sweepZ cuboids = sum $ map (segmentSize cuboids) $ segment evs
where evs = events _z cuboids
segmentSize :: [Cuboid] -> (Int, Int) -> Int
segmentSize cuboids (here, there)
| isActive $ filter (straddles _z here) cuboids = (there - here)
| otherwise = 0
segment :: [Int] -> [(Int, Int)]
segment [] = []
segment evs@(_ : tevs) = zip evs tevs
The other two axes are the same. Sweeping along the y axis gives areas, from multiplying the y length by the segment length. Sweeping along the z axis gives volumes, from the x length and area.
sweepX :: [Cuboid] -> Int
sweepX cuboids = sum $ map (volumeSize cuboids) $ segment evs
where evs = events _x cuboids
volumeSize :: [Cuboid] -> (Int, Int) -> Int
volumeSize cuboids (here, there) = (sweepY cuboidsHere) * (there - here)
where cuboidsHere = filter (straddles _x here) cuboids
-- assume for a given x
sweepY :: [Cuboid] -> Int
sweepY cuboids = sum $ map (areaSize cuboids) $ segment evs
where evs = events _y cuboids
areaSize :: [Cuboid] -> (Int, Int) -> Int
areaSize cuboids (here, there) = (sweepZ cuboidsHere) * (there - here)
where cuboidsHere = filter (straddles _y here) cuboids
And that's it!
This now makes part 1 harder than part 2, because I have to filter out all the "non local" cuboids in the input.
Code
You can get the code from my locally-hosed Git repo, or from Gitlab.