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

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.