It's finally time to get back to the Advent of Code solutions and optimise the very slow ones (as described in my Overview of Advent of Code 2023).

The first one to look at is day 21, as that's an easy one. The problem with this solution is that it does a lot of repeated work.

The problem is to find the positions in a grid that are reachable after precisely n steps, allowing for the agent to return to a previous position. That means that the starting state is reachable after 0, 2, 4 … steps; its neighbours are reachable after 1, 3, 5, … steps; and so on. The reachable area grows after each step.

My original solution maintains a Grid (a Set) of reachable positions and uses that to find the reachable positions after the next step (along with some fiddling to avoid impassible rocks in the grid.

takeSteps :: Grid -> (Position, Position) -> Grid -> Grid
takeSteps rocks bounds places =
  S.filter (notAtRock rocks bounds) $ S.unions $ S.map adjacents places
  
adjacents :: Position -> Grid
adjacents here = S.map (here ^+^) $ S.fromList [ V2 0 1, V2 1 0, V2 0 (-1), V2 (-1) 0 ]

This is slow because the whole of the reachable area is recalculated every step. The nature of the problem means that the interior of that area is the same after two step; only the edges of the area change.

That in turn suggests the optimisation: keep the boundary and the interior of the reachable region separate. I simulate two steps for the boundary and add it to the interior. The new boundary is the extended boundary minus the old interior. That also means I need to change the type signature, so take2Steps accepts and returns the pair of (boundary, interior).

take2Steps :: Grid -> (Position, Position) -> (Grid, Grid) -> (Grid, Grid)
take2Steps rocks bounds (boundary, old) = (boundary2 S.\\ old, new)
  where boundary1 = takeSteps rocks bounds boundary
        boundary2 = takeSteps rocks bounds boundary1
        new = S.union old boundary2

All that's needed after that is a bit of arithmetic to call take2Steps the correct number of times.

Performance

That small change is enough to reduce the runtime from 15.7 seconds to 0.69 seconds, roughly 23 times faster.

Code

You can get the code from my locally-hosted Git repo, or from Gitlab.