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 wrap
ping 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.