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.
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
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
canMove if the space
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
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)
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
There's no part 2 (as usual), so part 1 is enough to for me to have 350 stars.