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:

    1. The extent of the known, finite region
    2. The pixels we know in that finite region
    3. 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)


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

    Neil Smith

    Read more posts by this author.