Advent of Code 2020 - Day 10

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

In today's puzzle, after stripping it of the adaptor theme, we are asked to work with a sorted sequence of numbers, and the difference between one and the next. It has to be sorted because of the monotonicity imposed by the description of the adaptors. The first thing is to get the sequence from the input, sort it, and add the zero and last value (which is just the maximum of the input plus three). With this dealt with in get_adaptors, we can move on.

Part 1

The question in this part is, once translated, how many differences of 1 and how many differences of 3 are there in the full sorted sequence.

We start by finding the differences. we could iterate over the indices and take adaptors[i] - adaptors[i-1], then keep count of the counters for differences of one and three by hand:

count1, count3 = 0, 0
for idx in range(1, len(adaptors)):
    diff = adaptors[idx] - adaptors[idx - 1]
    if diff == 1:
        count1 += 1
    elif diff == 3:
        count3 += 1

Instead we note that adaptors[1:] gives us the sequence displaced by one position, and we can zip it with the original to get consecutive pairs. This makes it easy to build a generator expression for the differences, which we can feed directly to a Counter to do the counting for us.

Part 2

And now to the interesting part of today's puzzle: how many valid arrangements can be made by dropping zero or more items from the sequence, but keeping the maximum difference at most three.

We could recursively generate all possibilities, but I don't think I have that much time. So let's use graphs once again. I'm starting to sense a pattern here...

Let's say each item is a node, and we get and edge from it to every item afterwards that is at most itself plus three, i.e. to compatible items. Now the question is how many paths from the first to the last item can we have in that graph.

That's easy to answer if we only have one item: one path, starting and ending at itself. And we can go on by induction for there. To calculate the paths that reach any item, we take all the items that can reach it directly and add the number of paths reaching each of them. Since each item can only be reached from items before it in the sequence, we can just update them in that order and the values needed will be available.

We build the graph as usual, using a dictionary with each item as keys, and the set of items that can be reached from it as value. We initialize the paths of the first item to 1, and from there we push the number of paths to the successors instead of pulling from the predecessors. This avoids cumbersome reverse lookups in the graph. The result is the same, we just add the number of paths corresponding to an item to all the items that can be reached from it. By the time we reach an item, all items that could contribute have already been processed, so the number is already correct.

To get the final answer, we take the number of paths reaching the last item.