Advent of Code 2022 day 18

    After the past few days, day 18 was a bit of a relief! I wonder if this was intended to be a day where people could catch up?

    Data structures

    This is again direct. I have a droplet (a three-dimensional point) and some lava (a set of droplets).

    type Droplet = V3 Int
    type Lava = S.Set Droplet

    Counting surfaces

    The neighbours of a droplet are the positions at ±1 in each dimension.

    neigbours :: Droplet -> Lava
    neigbours here = S.fromList [ here & d %~ (+) n | d <- [_x, _y, _z], n <- [- 1, 1]]

    The surface area contribution of a droplet is 6 faces, -1 for each neighbour that has a droplet. The only wrinkle is converting the lava to a list so it doesn't collapse the result to just the distinct areas.

    surfaceArea :: Lava -> Int
    surfaceArea lava = sum $ fmap countFree $ S.elems lava
      where countFree droplet = 6 - (S.size $ S.intersection lava (neigbours droplet))

    Finding the steam

    I started by thinking about how to find if a point was completely enclosed in a polyhedron, but then realised there was a more direct method.

    1. Define a box outside the droplet
    2. Fill it with steam (with the steam not penetrating the droplet)
    3. The enclosed droplet is the box minus the steam

    The box is a bit larger than it needs to be, to ensure that the steam can reach all the surfaces of the droplet.

    "Filling with steam" is a standard flood-fill process, with a boundary and a set of steam-filled locations. As a point in the boundary is processed, its neighbours are added to the bounary so long as they've not already been processed, are inside the box, and aren't a droplet of lava.

    part2 lava = surfaceArea enclosed
      where box = boundingBox lava
            steam = floodFill lava box (S.singleton $ head $ range box) S.empty
            enclosed = (S.fromList (range box)) `S.difference` steam
    boundingBox lava = ((V3 minX minY minZ), (V3 maxX maxY maxZ))
      where minX = (fromJust $ minimumOf (folded . _x) lava) - 1
            minY = (fromJust $ minimumOf (folded . _y) lava) - 1
            minZ = (fromJust $ minimumOf (folded . _z) lava) - 1
            maxX = (fromJust $ maximumOf (folded . _x) lava) + 1
            maxY = (fromJust $ maximumOf (folded . _y) lava) + 1
            maxZ = (fromJust $ maximumOf (folded . _z) lava) + 1
    floodFill lava box boundary found
      | S.null boundary = found
      | otherwise = floodFill lava box (S.union nbrs $ S.delete here boundary) (S.insert here found)
      where here = S.findMin boundary
            nbrs = S.filter (`S.notMember` lava) 
                    $ S.filter (`S.notMember` boundary) 
                    $ S.filter (`S.notMember` found) 
                    $ S.filter (inRange box) 
                    $ neigbours here


    You can get the code from my locally-hosted Git repo, or from Gitlab.

    Neil Smith

    Read more posts by this author.