Advent of Code 2020 day 10

Day 10 is another example where the explanation is much longer than the code.

The first insight is to realise that the constraint that all adapters must be used, together with the fact that jolts can only increase, means that the adapter list should be sorted. At the same time, I include the source and the device in the list.

main :: IO ()
main = 
    do  numStrs <- readFile "data/advent10.txt"
        let nums = map (read @Int) $ lines numStrs
        let device = 3 + maximum nums
        let sortedNums = sort (0:device:nums)
        print $ part1 sortedNums
        print $ part2 sortedNums

Part 1

The only interesting part is the "trick" for bringing together adjacent pairs in the list: zip the list with the tail of itself. Once you have those pairs, you can filter if they have the desired gap, then count how many are left.

part1 :: [Int] -> Int
part1 nums = jolt1s * jolt3s
    where jolt1s = joltNs 1 nums
          jolt3s = joltNs 3 nums

joltNs d ns = length $ filter diff $ zip ns (tail ns)
    where diff (a, b) = (b - a) == d

Part 2

There are a couple of ways to approach this. One is to generate all the arrangements of adapters that lead from the source to the device, and count how many there are. As there are 100 adapters, that's 2¹⁰⁰ ≈ 10³⁰ possible different arrangements of including and excluding adapters. This approach will only work with memoisation.

The other approach, the one I took, is dynamic programming. The solution is easy if I can just look up the answer. Imagine I have a table that shows, for each adapter, the number of arrangements that leads to that adapter. When I include a new adapter, I can look up the values for the next-smaller adapters, add them together, and that's the result for this adapter.

If I walk up the adapter list in sorted order, adding to the table as I go, I always have the information to efficiently calculate result for the next adapter.

The table is a Map of adapter value to number of ways of using it. I include a new adapter in the table by looking up all the earlier arrangements, adding their values, then inserting that new value into the table.

includeAdapter arrangements adapter = M.insert adapter earlierCount arrangements
    where 
        earlierArrangements = M.filterWithKey (\k _ -> (adapter - k) <= 3) arrangements
        earlierCount = M.foldl (+) 0 earlierArrangements

Building the table over the list of adapters is a fold over the list of adapters, starting with an initial table that says there's one way to use the source. Once done, I extract the value of the maximum key (the device).

part2 :: [Int] -> Int
part2 nums = snd $ M.findMax $ foldl includeAdapter (M.singleton 0 1) $ tail nums

Code

You can find the code here or on Gitlab.