Small introduction

This year, a friend of mine introduced me to the Advent of Code challenge. Apprently, this has been going around for five years already without me noticing it. I have to admit that I like these types of programming challenges, but I have never really invested much time in it. What’s nice with the Advent of Code is that you have a new problem each day, and that each problem actually has an ’easy" and a “hard” part.

This blog post (as long as the following ones) is coming a little late (we are already the 13th of December), but I thought it might be interesting to share some of my solutions and thought-processes as I solve the problems (or at least, attempt to solve them).

I’ll try to solve these problems using Python. This will be a very good opportunity for me to practice it every day. But most importantly, this will also allow me to compare my solutions to my friend’s one, who is using Python regularly in his job. And so, we are discussing our solutions and algorithms on a daily basis and I can already say that I’m writing more pythonic algorithms day after day.

The problem

Part 1

Day 1’s problem is quite straightforward. The kind of problem that you can give to your CS1 students. But still, there are ways already to make your solutions more or less efficient.

In this problem, we are given a list of positive integers list and we need to find x and y in list so that x + y = 2020. Then, your algorithm should return x * y.

A very naive solution would be to two loops summing elements of the list together and verifying whether the sum is equal to 2020. But you don’t really need to do that since you are sure that such a couple of values exist. So instead, you can simply loop through the elements of the list, and check that 2020 - element is also in your list. You’d eventually end up with something like this:

list = [1721, 979, 366, 299, 675, 1456] # The list of integers given as example
index = 0
while 2020 - list[index] not in list:
    index += 1
print(list[index] * (2020 - list[index])) # Should oupt 1721 * 299 = 514579

Part 2

Part 2 is exactly the same problem, except that we are now looking for triplets of values that summed together are equal to 2020 (and not couples anymore).

Here, you can very much brute force your results by writing three loops. Or you can realise that, once again, you don’t necessarily need three loops and that two will do just fine. Here are two different ways of solving this exerxise (one way was simply me trying to practice with list comprehension in Python):

# With list comprehension (you then simply need to multiply each value)
# This will have duplicates (which is not super optimized)
# The same could probably be done with set comprehension
answer = [(x, y, z) for x in list for y in list for z in list if x+y+z == 2020]

# With one less loop:
for i in list[:-1]:
    for j in list[i:]:
        if 2020 - list[i] - list[j] in list:
            print(list[i] * list[j] * (2020-list[i]-list[j]))
            break