Advent of Code 2020, Day 1 -- Report Repair

Dec 1st, 2020

4 min read

Advent Of Code

Python solutions to Advent of Code 2020, day 1.

My Advent of Code solutions, done in Python. Refactors and solutions in other languages will be added if/when they're done.

Full code for Day 1 can be found on Github.

You can participate in Advent of Code at adventofcode.com/2020

The Day 1 problem can be found at adventofcode.com/2020/day/1

Original solution, part 1

My first thought was to loop through the provided list of numbers. For each number in the main loop, I'll loop through the numbers from index 0 through the current index, and see if the two numbers equal 2020. If they do, break the loop and print the product of the two numbers.

For example:

The loop starts at list[0]. It goes to the next number, at list[1]. Now the second loop looks at list[0] and adds list[1] + list[0]. If the sum is 2020, break and print the product. If not, the main loop proceeds to list[2]. Now, the second loop adds list[2] + list[0] and evaluates, then list[2] + list[1] and evaluates, and so on until it finds the two numbers that satisfy the condition.

list[a] + list[b] == 2020 where a > b.

# Since the puzzle input is provided as a text file,
# open and parse the file into a list.
input = open("input.txt", 'r')
lines = input.readlines()

# Part 1
# Loops through the provided numbers
# and loops through all numbers before
# until finding the numbers that equal 2020.
for (i, line) in enumerate(lines):
    for j in range(0, i):
        a = int(line)  # Read as strings,
        b = int(lines[j])  # must be converted to integers.
        sums = a + b
        if sums == 2020:
            print(a, b)
            print(a * b)
            break

Original solution, part 2

My solution for part 2 was to build upon part 1, and add a third loop into the mix.

list[a] + list[b] + list[c] == 2020 where a > b > c.

# Part 2
# The same as part 1, but with an additional loop
# that loops through the numbers again.
# Unless all the numbers are at the end of the list,
# this should be fast-ish as it breaks when 2020 is found.
for (i, line) in enumerate(lines):
    for j in range(0, i):
        for k in range(0, j):
            a = int(line)
            b = int(lines[j])
            c = int(lines[k])
            sums = a + b + c
            if sums == 2020:
                print(a, b, c)
                print(a * b * c)
                break

While this works, part 2 is a bit sluggish, so I wanted to try reworking my solution a bit and optimize it further.

Refactor, part 1

I'm a fan of using a Python dictionary to make looking up matching numbers faster. In my first iteration, the dictionary held {n: n}, so if 2020 - list[a] == dict[n], it would simply return the product of list[a] and dict[n]. In my second iteration, which is the code I have below, the dictionary holds {2002 - n: n}, so the check is list[a] == dict[2002 - n] and returns the product of list[a] and dict[list[a]] (which is n).

This is much faster than the original solution, because the lookup is instant, and the loop only needs to go as far as list[a] before it stops.

# This makes part 1 faster by removing the second loop.
# It doesn't even loop through fully once.
# It checks to see if the current number x has been added to dictionary d
# as the difference between n and a previous number.
# If not, it adds n - x: x to d.
def find_two_entries(n):
    d = {}
    for line in lines:
        x = int(line)
        if x in d:
            print(x, d[x])
            return x * d[x]
        d[n - x] = x


print(find_two_entries(2020))

Refactor, part 2

As far as I know, part 2 can't be done with a dictionary object since we're looking for three numbers. I made a few attempts, but decided to use itertools.combinations instead.

This solution first maps the list of number strings into a list of integers, then uses itertools.combinations to create a list of every triplet that can be made with the provided numbers. Then, it iterates over those combinations until it finds one that adds up to 2020 and returns the product of the three numbers.

This is faster than the loop-within-a-loop-within-a-loop original solution, but not as fast as the dictionary lookup.

from itertools import combinations

# Creates every 3-number combination with itertools.combinations,
# then finds the combo that adds up to n.
# https://www.geeksforgeeks.org/python-find-all-triplets-in-a-list-with-given-sum/
def find_three_entries(n):
    nums = list(map(lambda x: int(x), lines))
    combos = list(combinations(nums, 3))
    for c in combos:
        if sum(c) == n:
            print(c)
            return c[0] * c[1] * c[2]


print(find_three_entries(2020))

Refactor that works for both parts

I think the smartest solution, while not necessarily the fastest, is one that can be used for both parts of the problem. It'll even find four numbers that add up to 2020! However, finding four numbers is a much slower calculation due to how many combinations there are.

This is a refactor of the previous solution. It removes the map and replaces it with a list comprehension inside of the itertools.combinations function, which also takes an argument for how many entries we're looking for.

Also, I'm using functools.reduce to return the final product, that way no matter how many entries are returned, they can be easily multiplied together.

from itertools import combinations
from functools import reduce

# Multi-use function that can be used to find any number of combinations
# that add up to n. Returns the product of the combo.
def find_entries(n, num_entries):
    combos = list(combinations([int(x) for x in lines], num_entries))
    for c in combos:
        if sum(c) == n:
            print(c)
            return reduce(lambda a, b: a * b, c)


print(find_entries(2020, 2))
print(find_entries(2020, 3))

At this point, I don't think I can find a better solution for day 1, and it's only going to get harder from here!

mary.codes