Day 13 saw the return of yet another AoC stalwart: number theory. (What is it about the Chinese remainder theorem? Is that a big thing in US discrete maths courses?)

Parsing the input file was another example of using `pure`

to return an explicit value. I represented the bus periods as a list of `Maybe`

s, as I was sure the gaps would be significant in part 2.

```
timeBusP = (,) <$> decimal <* endOfLine <*> busPeriodsP
busPeriodsP = busPeriodP `sepBy` (string ",")
busPeriodP = (Just <$> decimal) <|> ("x" *> pure Nothing)
```

## Part 1

A bit of modular arithmetic. Using the example in the puzzle text, at time 939 and bus 7, the result (939 mod 7 = 1) is how many minutes you missed the bus by (bus 7 left at 938). Similarly, you missed bus 13 by (939 mod 13 = 3) minutes. The next bus 7 will be along in (7 - (393 mod 7)) minutes, and the next bus 13 will be in (13 - (939 mod 13)) minutes. That calculation gets wrapped up in `earliestDeparture`

. `busAndTime`

wraps that calculation with the bus period. I `map`

that function over all the busses, then `sortOn`

the time to wait to find the next bus that turns up.

```
part1 timestamp maybeBusses = eBus * eTime
where busses = catMaybes maybeBusses
busDepartures = map (busAndTime timestamp) busses
(eBus, eTime) = head $ sortOn snd busDepartures
busAndTime timestamp period = (period, earliestDeparture timestamp period)
earliestDeparture timestamp period = period - (timestamp `mod` period)
```

## Part 2

Calculating the Chinese remainder theorem is too much trouble for my little brain. Why reinvent the wheel when it's already in the arithmoi library?

`periodOffsets`

turns the list of busses into a list of (delay, period) pairs. I find the Chinese remainder of all of them by folding the pairs together with the Chinese remainder theorem.

```
earliestGroup :: [(Integer, Integer)] -> (Integer, Integer)
earliestGroup offsetBusses = foldl1 chineseStep offsetBusses
chineseStep (n1, m1) (n2, m2) = (n, m1 * m2)
where n = fromJust $ chinese (n1, m1) (n2, m2)
```

The result is how long, before the repeat, the group occurs. Subtract one from the other to get the result.

```
part2 maybeBusses = b - a
where (a, b) = earliestGroup $ periodOffsets maybeBusses
```

## Code

You can find the code here or on Gitlab.