Advent of Code 2020 - Day 1
If you haven’t heard of Advent of Code , it is an Advent calendar of small programming puzzles that run every year from December 1st through the 25th. This year, I was happy to have solved the majority of the puzzles on my own, with very little help from the subreddit.
Most of these puzzles can be solved in Python using only the standard library, and for some, it really boils down to parsing the input into a form that’s more suited for processing. Suffice to say, there are a ton of spoilers in this series, so if you want to avoid spoilers, look away now.
In this post, I’ll cover Day 1 of AoC 2020 - Report Repair. The task is to find
two numbers that sum to 2020. The naive approach is to check every pair of
numbers. This is a $ O(n^2) $ algorithm, but given that the input is fairly
small, it will suffice.
First step is to load the numbers into our program.
with open("input") as datafile:
data = list(map(int, datafile.read().splitlines()))Because the terms of the problem state that there is only 1 pair that will sum to 2020, the way I solved it was to generate two sets, one with the input data, and another with each element subtracted from 2020, and found the set intersection. This would give us exactly 2 elements.
part1 = set(data) & set(2020 - x for x in data)Finally, we need to generate the product of these elements. While there’s a
built-in sum function, we need the equivalent of $ \prod_{i=1}^n x_i $.
This is where we rely on the reduce method from the functools module as
shown below:
print(functools.reduce(lambda x, y: x*y, part1))For part 2, we need to find 3 elements that sum to 2020. At this point I
realized that the itertools.combinations method should have been my first
pick for part 1. Doesn’t matter, I got the right answer anyway. Here’s the code
for part 2.
for combo in itertools.combinations(data, 3):
if sum(combo) == 2020:
print(functools.reduce(lambda x, y: x*y, combo))
break # Because there's only supposed to be 1 set, we can quit early