Advent of Code 2020 day 13

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)

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.