It’s that time of the year again: the Advent of Code 2020 has started!

For those who don’t know, Advent of Code is an Advent calendar of programming puzzles. Simple at first, not-so-simple after one week or two usually. This year I’ve decided to try to write a small recap every day. Or, well, whenever I solve those puzzles, which may be a few days late, or even way later if things don’t go as planned 😅

Also, this year I won’t try to do anything crazy. I’ll just stick to things I know and use Python. And reuse the small “framework” I wrote last year that makes it easier to focus on solving puzzles, instead of losing time doing mundane things like testing or parsing input. (Maybe I’ll throw in some Cython as well, if needed for performance. Or maybe use that as an opportunity to try Rust? We’ll see!)

All my solutions are available as a Git repository: https://git.sr.ht/~schnouki/advent-of-code.

Part 1

The 1st part is pretty simple: in a list of integers, find a pair of numbers that sums to 2020, and show their product.

To do that, we need to:

• iterate over all pairs of numbers,
• avoiding repetitions (no need to consider (a, a), and
• not caring for order ((a, b) is the same as (b, a)).

So we can use 2 nested for loops… or recognize that this is a combination, and use itertools.combination.

The resulting code looks like this:

import itertools as it

for a, b in it.combinations(data, 2):
    if a + b == 2020:
        return a * b

And that’s it. This took 0.11 ms to run on my laptop for a list of 200 numbers.

Part 2

Same thing, with 3 numbers. We can still use itertools.combination (or 3 nested for loops):

for a, b, c in it.combinations(data, 3):
    if a + b + c == 2020:
        return a * b * c

This is much slower, as it took 64 ms to run. Which makes sense: as we have a 3rd nested loop with 200 entries, iterating over all those combinations becomes 200 times slower.

So let’s go back to 2 nested loops. We can use a simple trick: a + b + c = 2020 means that c = 2020 - a - b. So we can compute c and check if it’s in the input data:

for a, b in it.combinations(data, 2):
    c = 2020 - a - b
    if c in data:
        return a * b * c

That takes 22 ms. Still too long!

Why is it still slow? Because of the c in data check. As data is a list, the Python runtime has to iterate over it to check if c is in here. This is implemented in C so faster than iterating in Python, but still pretty slow.

So, simple solution that works: use a set instead of a list. Now checking if c in data will be O(log n) instead of O(n):

data = set(data)
for a, b in it.combinations(data, 2):
    c = 2020 - a - b
    if c in data:
        return a * b * c

This took 0.48 ms. Applying the same trick to part 1 reduces its runtime to 0.01 ms. Not too bad 😎

And that’s it for today! Kudos to Eric Wastl for running the Advent of Code. Especially as this December 1st was hit by a serious case of 2020!