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
Maybes, 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)
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
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)
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