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.