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 2100 ≈ 1030 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
            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


    You can find the code here or on Gitlab.

    Neil Smith

    Read more posts by this author.