Advent of Code 2021 day 25

    After the rigmarole of day 24, day 25 was a breath of fresh air. As I wanted to generate the number of states in the simulation, I decided to write a step function to generate the next step of the simulation, and unfold that into a list of states.

    Data structures

    I've used arrays before, as in day 15, to represent grids. But this time I decided to store the grid as a Map, treating it as a sparse array. I also created a Grid data type to hold both the cucumber locations and the bounds of the grid.

    type Coord = V2 Int -- r, c
    data Grid = Grid (Coord, Coord) (M.Map Coord Cucumber)
      deriving (Eq, Show)
    
    data Cucumber = Eastwards | Southwards
      deriving (Eq)
    
    instance Show Cucumber where
      show Eastwards = ">"  
      show Southwards = "v"

    Reading and displaying a grid was done with list comprehensions.

    mkGrid :: String -> Grid
    mkGrid text = Grid (V2 0 0, V2 maxR maxC) 
        ( M.fromList 
          [ (V2 r c, mkCucubmer r c) 
          | r <- [0..maxR], c <- [0..maxC]
          , isCucumber r c
          ]
        )
      where rows = lines text
            maxR = length rows - 1
            maxC = (length $ head rows) - 1
            isCucumber r c = ((rows !! r) !! c) `elem` (">v" :: String)
            mkCucubmer r c = if (rows !! r) !! c == '>' then Eastwards else Southwards
    
    showGrid :: Grid -> String
    showGrid (Grid (V2 minR minC, V2 maxR maxC) cucumbers) = 
      unlines $ [ concat [showCucumber (V2 r c) | c <- [minC..maxC] ] | r <- [minR..maxR] ]
      where showCucumber here = maybe "." show $ cucumbers !? here

    Building features

    Given those data structures, I wrote the rest of the code by building functions that gave me the features I needed to do the simulation.

    I find space ahead of a cucumber by adding a delta to the cucumber's position (depending on its type) and wrapping the result to lie in the bounds.

    delta :: Cucumber -> Coord
    delta Eastwards = V2 0 1
    delta Southwards = V2 1 0
    
    wrap :: (Coord, Coord) -> Coord -> Coord
    wrap bounds@(V2 r0 c0, V2 r1 c1) (V2 r c)
      | r > r1 = wrap bounds $ V2 r0 c
      | r < r0 = wrap bounds $ V2 r1 c
      | c > c1 = wrap bounds $ V2 r c0
      | c < c0 = wrap bounds $ V2 r c1
      | otherwise = V2 r c
    
    ahead :: Grid -> Coord -> Coord
    ahead (Grid bounds cucumbers) here = wrap bounds (here ^+^ (delta c))
      where c = cucumbers ! here

    A cucumber canMove if the space ahead is vacant. A grid is blocked if no cucumbers can move (this is the condition to stop simulation),

    vacant :: Grid -> Coord -> Bool
    vacant (Grid _ cucumbers) here = M.notMember here cucumbers
    
    canMove :: Grid -> Grid
    canMove grid@(Grid bounds cucumbers) = Grid bounds $ M.filterWithKey openAhead cucumbers
      where openAhead here _ = vacant grid $ ahead grid here
    
    blocked :: Grid -> Bool
    blocked grid = M.null cucumbers 
      where Grid _ cucumbers = canMove grid

    I need to advance the east-facing and south-facing cucumbers separately, so there are functions to separately identify those cucumbers and advance them.

    eastFacing, southFacing :: Grid -> Grid
    eastFacing (Grid bounds cucumbers) = Grid bounds $ M.filter (== Eastwards) cucumbers
    southFacing (Grid bounds cucumbers) = Grid bounds $ M.filter (== Southwards) cucumbers
    
    advanceEastwards, advanceSouthwards :: Grid -> Grid
    advanceEastwards = advance eastFacing
    advanceSouthwards = advance southFacing

    I can advance some cucumbers by finding the once that can move, and are facing the desired direction. Each of those cucumbers moves ahead and the moved cucumbers are joined (with union) with the cucumbers that didn't move. That gives the new grid.

    advance :: (Grid -> Grid) -> Grid -> Grid
    advance facing grid@(Grid bounds cucumbers) = Grid bounds $ M.union cannotMove advanced
      where Grid _ advancing = facing $ canMove grid
            cannotMove = cucumbers \\ advancing
            advanced = M.fromList $ map advanceOne $ M.toAscList advancing
            advanceOne (here, c) = (ahead grid here, c)

    A step of the simulation the the composition of a southwards advance applied to the result of an eastwards advance. The step is maybe taken, depending on whether the grid is blocked. Finally, I simulate the cucumbers by unfolding the initial grid into all its subsequent states.

    step :: Grid -> Grid
    step = advanceSouthwards . advanceEastwards 
    
    maybeStep :: Grid -> Maybe (Grid, Grid)
    maybeStep grid
      | blocked grid = Nothing
      | otherwise = Just (grid', grid')
      where grid' = step grid
    
    simulate :: Grid -> [Grid]
    simulate grid = unfoldr maybeStep grid

    Part 2

    There's no part 2 (as usual), so part 1 is enough to for me to have 350 stars.

    Code

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

    Neil Smith

    Read more posts by this author.