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.