Day 7 was one where a bit of thinking about the data structures used paid great dividends for getting to an easy solution.

Data structures

For the problem, we're given a grid that contains a bunch of beam splitters and a beam that enters from the top of the grid. The beam goes straight down until it hits a splitter. When it does, beam splits into two, one either side of the splitter, and both continue down. The challenge is to count the number of splits that occur.

For problems like this, I like to think about what information I need while I'm part-way through finding a solution, such as the one below. That shows that the beam has split into two and then into three (the two middle beams merge into one), and has been split three times.

.......S.......
.......|.......
......|^|......
......|.|......
.....|^|^|.....
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

That means I need to keep track of the end ("head") of each beam, and the number of times a beam has been split.

From that, to generate the next step in the solution, I take one of the beam heads and move it down one space. If it meets a splitter, I do the splitting logic. If not, I just record the new head of the beam. I repeat that until all the beams are below the bottom splitter.

That tells me a lot about what the data structures should look like. I need to track positions, so I use the standard V2 object for that. I need a collection of beam heads; as multiple heads in the same place should merge, it looks like I need a Set of Positions. I need to keep that set of beam heads with a count of the number of splits. I chose to use a record data type to keep things neat.

Finally, I need to keep track of the positions of the splitters. Again, that's a Set of Position, but I use a newtype to make it a distinct type. That allows me to use the type system to keep myself straight, so I don't try using the set of splitters instead of the set of beam heads, and vice versa.

type Position = V2 Int -- r, c

pattern U, D, L, R :: Position
pattern U = V2 (-1) 0
pattern D = V2 1 0
pattern L = V2 0 (-1)
pattern R = V2 0 1

type Beams = S.Set Position
newtype Splitters = Splitters (S.Set Position) deriving (Show, Eq)

data SplitState = SplitState { beamHeads :: Beams, splitCount :: Int}
  deriving (Show, Eq, Ord)

(Reading the input file is the same as Day 4, so I don't repeat it here.)

The final step is to combine SplitState items. When I propagate a beam head, it'll be convenient if I can put just that propagated beam in its own SplitState and combine it with the existing one to update the overall situation.

Haskell has a general category for "things that can be combined with each other, to produce a thing of the same type": the Monoid. Examples are things like lists (combining is list appending) and sets (combining is set union). That suggests I should make SplitState and instance of that class. I also need the notion of an "empty" item.

Combining two SplitState items is combining the set of beam heads and adding the number of splits.

instance Semigroup SplitState where
  (SplitState b1 c1) <> (SplitState b2 c2) = SplitState (b1 <> b2) (c1 + c2)

instance Monoid SplitState where
  mempty = SplitState S.empty 0

Once something is defined as a monoid, I get other feature for free, such as mconcat that combines a collection of monoids into one.

With all that done, onto the problem solving!

Part 1

I build the solution up from the lowest level.

Propagating a single beam head takes the set of splitters and the location of the beam, and returns a new SplitState. What's in the split state depends on whether the beam hits a splitter or not.

propagateBeam :: Splitters -> Position -> SplitState
propagateBeam (Splitters splitters) here 
  | there `S.member` splitters = SplitState (S.fromList [there ^+^ L, there ^+^ R]) 1
  | otherwise = SplitState (S.singleton there) 0
  where there = here ^+^ D

I can use that to propagate all the heads. I convert the set of existing beam heads to a list, apply propagateBeam to each, then combine the results with mconcat.

propagateAll :: Splitters -> SplitState -> SplitState
propagateAll splitters oldHeads = newHeads {splitCount = oldHeads.splitCount + newHeads.splitCount}
  where newHeads = mconcat $ fmap (propagateBeam splitters) $ S.toList oldHeads.beamHeads

Finally, the full propagation is based on iterate, where I drop all the partial states that have at least one beam above one splitter.

propagate :: Splitters -> SplitState -> SplitState
propagate splitters@(Splitters s) beams = head $ dropWhile inBounds $ iterate (propagateAll splitters) beams
  where inBounds theseBeams = not $ S.null $ S.filter (\(V2 r _) -> r <= maxDepth) theseBeams.beamHeads
        maxDepth = S.findMax $ S.map (\(V2 r _) -> r) s

Part 2

When I started part 2, my sleep-addled brain started off down a rabbit hole of complex type hierarchies before I saw the idea.

For part two, I have to do the same as part 1, but keep track of how many ways there are of getting to each beam head.

That means I need to use a MultiSet of beam heads, where the MultiSet keeps track of the heads themselves and the number of ways of generating them.

The actual change in the code was restricted to tiny changes in propagateBeam and propagateAll. propagateBeam takes a pair of (Position, Int), to handle how many was there were of getting to this beam; this number is copied into the new SplitState record. In propagateAll, rather than converting the set of beam heads to a list, I convert it to a list of (Position, Int) pairs with toOccursList.

propagateAll :: Splitters -> SplitState -> SplitState
propagateAll splitters oldHeads = newHeads {splitCount = oldHeads.splitCount + newHeads.splitCount}
  where newHeads = mconcat $ fmap (propagateBeam splitters) $ S.toOccurList oldHeads.beamHeads

propagateBeam :: Splitters -> (Position, Int) -> SplitState
propagateBeam (Splitters splitters) (here, n)
  | there `S.member` splitters = SplitState (S.fromOccurList [(there ^+^ L, n), (there ^+^ R, n)]) 1
  | otherwise = SplitState (S.fromOccurList [(there, n)]) 0
  where there = here ^+^ D

I find the total number of ways by reading off the size of the final multiset.

Code

You can get the code from Codeberg.