Advent of Code 2020 - Day 9

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.

Part 1

This exercise asks us to find the first number in a sequence that cannot be expressed as the sum of two numbers in the 25 before it (obviously starting from the 26th number on). This sounds familiar; we will import our find_pair function. It's a good thing that we made the effort to make it separate from the rest of the logic and to make it efficient, as we will use it repeatedly.

In fact, that's all we need to do: get the number, the ones before it, and apply find_pair. The first time it fails, that's our answer. Instead of hardcoding the length of 25 number for the previous block, we will use a variable preamble, if only to check the example which uses a different length.

Part 2

Now a slightly different question: finding a contiguous subsequence of numbers in the sequence that add up to the target (which happens to be the answer from part 1).

As in other cases, trying out all possible combinations is not practical. We can take a look at the input and realize that all numbers are positive, which will make our work easier. We can make our chink a kind of rolling window over the sequence. If the sum of the numbers within the window is less than the target, we increase the size of the window by moving its end one position up (we add the next number); if we overshoot, we remove the first number in the chunk by moving up its start position. If the sum matches the target, we have our chunk.

This only works because we want a contiguous block (otherwise we need completely different approach) and all numbers are positive; if there were negative numbers, extending the chunk after overshooting could still give the right answer.

From the implementation point of view, there are a couple of things to keep in mind. first, we can keep track of the sum of the numbers in the window by adding/subtracting the added/removed number instead of recalculating the whole thing with each step. And second, we must enforce the condition of at least two numbers in the window, or we would return with the target itself if we reach it before the chunk.

Finally adding the minimum and maximum to get the final answer is trivial.