Advent of Code 2021 day 20

The day 20 puzzle was about handling points in a range, and updating states. Therefore, I made heavy use of the Data.Ix library again, and the RWS monad (reader-writer-state), only not using the writer part.

We're asked to operate over an infinite plane, even if we're only given a finite portion of it. That means I need to keep track of three things:

The extent of the known, finite region
The pixels we know in that finite region
The value of every pixel outside the known region.

That led me to this data structure of storing an image

type Pixel = V2 Int -- row, column

data Image = Image 
  { grid :: S.Set Pixel
  , distantPixel :: Bool
  , explicitRegion :: (Pixel, Pixel)
  } deriving (Eq, Show)

Using regions and determining things inside and outside a region is entirely within the domain of the Ix class. Given the parts of an Image I define the function findContents that will determine if a pixel is lit, whether or not it is inside the known region.

findContents :: S.Set Pixel -> Bool -> (Pixel, Pixel) -> Pixel -> Bool
findContents grid distant region here 
  | inRange region here = here `S.member` grid
  | otherwise           = distant

This is essentially a member function for the infinite image. Armed with this, I can put together the rest of the solution.

But before I get to that, the problem involves updating an image in steps, and doing so in the context of a fixed enhancement scheme. That's computing with a state and in an environment, as modelled in Haskell with a State and Reader monad respectively. Normally, you'd want track some output at the same time and throw in a Writer monad, and those are neatly bundled in the RWS monad. I thought it was easier to use the convenient bundle rather than building my own monad stack.

The use of the monad makes the "update the image" functions a bit clearer, with shorter parameter lists than otherwise. findStencil returns a list of Bools representing the surroundings of the current pixel. (In this case, unwrapping the values from the record inside the monad makes the call to findContents much quicker, halving the overall runtime.) newPixel returns whether the current pixel is lit in the new state.

newPixel :: Pixel -> ImageEnhancer (Maybe Pixel)
newPixel here =
  do  stencil <- findStencil here
      let i = intify stencil
      enh <- ask
      return $ if enh!!i then Just here else Nothing

findStencil :: Pixel -> ImageEnhancer [Bool]
findStencil here = 
  do  let nbrs = map (here ^+^) neighbours
      g <- gets grid
      d <- gets distantPixel
      r <- gets explicitRegion
      return $ map (findContents g d r) nbrs

neighbours :: [Pixel]
neighbours = [V2 r c | r <- [-1, 0, 1], c <- [-1, 0, 1]]

The actual image enhancement is done with newImage. It follows the steps as set out in the puzzle description. The trick is that, as the first step, the explicit region is expanded by 1 step in each direction, and the new finite grid is calculated in that new, expanded region. Ix provides the handy range function that finds all the pixels in the new region, then the combination of newPixel and catMaybes generates the new grid. The final thing is to reset the value of the pixel outside the known region.

newImage :: ImageEnhancer ()
newImage =
  do  region <- gets explicitRegion
      let region' = expandRegion region
      let heres = range region'
      newPixels <- mapM newPixel heres
      let grid' = S.fromList $ catMaybes newPixels
      distant <- gets distantPixel
      enhancement <- ask
      let distant' = if distant then (last enhancement) else (head enhancement)
      put $ Image {grid = grid', distantPixel = distant', explicitRegion = region'}

Given all that effort, iterating newImage is handled by primitive recursion and the monad is executed with evalRWS.

part1 enhancement image = fst $ evalRWS (enhanceImage 2) enhancement image

part2 enhancement image = fst $ evalRWS (enhanceImage 50) enhancement image

enhanceImage :: Int -> ImageEnhancer Int
enhanceImage 0 = do image <- get
                    return $ S.size $ grid image
enhanceImage n = do newImage
                    enhanceImage (n - 1)

Code

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

Advent of Code 2021 day 20

Code

Neil Smith