Advent of Code 2020 - Day 1

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. 

The first day is just a warm-up exercise, but still there are some subtleties, specifically in the complexity of possible solutions.

Part 1

The first part reduces to finding a pair of numbers in a list that add up to 2020. I checked the list for duplicates, and there are none, which makes the use of sets a viable option. We will see why this is important in a moment.

The naive approach would be to check each possible pair, which would result in quadratic complexity, not bad, but this can be easily achieved in linear time. By using sets, so that membership checks are constant time, otherwise these would be linear time and we would be back to quadratic.

The solution is taking each value n in the set, and checking whether target - n is in the set. If it does, we have our answer. We return it as n * (target - n) as the requested answer is the product of the numbers.

This requires two linear operations: building the set, and running through it once checking each number (the check is constant time, as mentioned above).

Part 2

The next exercise is finding three numbers that add up to 2020. If we hadn't gone for a linear solution in the first part, we would be looking at a cubic time solution for this one. As it is, we can manage to limit it to quadratic time, by checking for each number n whether there are two numbers in the rest of the set that add up to target - n, and this can be done using the approach from Part 1.

Of course, in all the discussion complexities are worst case. The algorithms will end as soon as the right answer is found, which can happen with the first numbers that it evaluates. In the worst case, it will try all potential combinations to determine that there isn't one that meets the requirements. In that case, the return value will be None.