Advent of code: 2020 Day 01

SPOILER ALERT
This is a post with my solutions and learnings from the puzzle. Don't continue reading if you haven't tried the puzzle on your own yet.

If you want to do the puzzle, visit adventofcode.com.

TOC

• Key learning
• Part 1
  • Solution N^2
  • Solution N
• Part 2
  • Solution N^3
  • Solution N^2
• Other tricks
• Functional style

Key learnings

• For-loops
• If statements

You need to understand loops and if-statements to solve the puzzle. You can make it more advanced by optimizing the solution, then there are some more key learnings. Though the input is small enough that no optimization is needed.

Puzzle part 1

You get a list of numbers and the puzzle is: Find the two entries that sum to 2020; what do you get if you multiply them together?.

Input example

The input is a file with numbers. They are in the format of one number per line.

1721
979
366
299
675
1456

Parse input

Start by preparing how to parse the data. My programming language of choice is python:

# Open the input file
inputfile = open('01.input', 'r')

# Parse lines to array of numbers
lines = inputfile.readlines()
entries = [int(x.strip()) for x in lines]

Solution - O(N^2)

A first assumption is made that 1010 isn't on the entry-list. Therefore it doesn't matter if we happen to compare a entry to itself. Otherwise it would give a false positive.

The naive solution is a double for-loop where we check all possible combinations of two entries. For those entries we check if they sum up to 2020, if so it returns the multiplication of them.

In worst case it requires O(N^2). The input-file is 200 lines long, which means 200 * 200 = 40 000 comparisons. It executes within a few seconds on my computer.

def part1(entries):
  for x in entries:
    for y in entries:
      if x + y == 2020:
        return x * y
result = part1(entries)
print("Result part 1: %d" % result)

Solution advanced - O(N)

If we use a set to store the rests we can optimize the solution to O(N) in time complexity. The rest is the difference between our current entry X and 2020

X + rest = 2020 ==> rest = 2020 - X

For each entry X we check if we have a value in the rests-set which fulfills X + rest == 2020. Otherwise we store X as a rest.

def part1(entries):
    rests = set()

    for x in entries:
        rest = 2020 - x
        if rest in rests:
            return rest * x
        else:
            rests.add(x)

Part 2

The second part of the puzzle is: what is the product of the three entries that sum to 2020?

Solution - O(N^3)

A naive solution is just to add another for loop. This gives us 3 for-loops that in worst case gives time complexity of O(N^3)

def part2(entries):
    for x in entries:
        for y in entries:
            for z in entries:
                if x + y + z == 2020:
                    return x * y * z

Solution - O(N^2)

A more optimized solution is to calculate this in two steps. First using a dictionary to store each possible combination of two entries. This takes O(N^2) time. Then we iterate through the list once again to find the third entry required to meet 2020.

The dictionary has the sum of two entries as key, and multiplication of them as the value.

This solution has time complexity of O(N^2 + N) which is simplified to O(N^2)

def part2(entries):
    rests = {}
    for x in entries:
        for y in entries:
            rests[x + y] = x * y

    for x in entries:
        rest = 2020 - x
        if rest in rests:
            return x * rests[rest]

Please share if you know a faster way of solving this problem!

Other tricks

Another way to increase performance is to never look at a combination twice. Not sure which time complexity it gives. At least better than O(N^2) and O(N^3) for part 1 and part 2 respectively. Please comment below if you know!

def part1(entries):
  size = len(entries)
  for i in range(size):
      for j in range(i + 1, size):
          if entries[i] + entries[j] == 2020:
            return entries[i] * entries[j]

def part2(entries):
  size = len(entries)
  for i in range(size):
    for j in range(i + 1, size):
      for k in range(j + 1, size):
        if entries[i] + entries[j] + entries[k] == 2020:
          return entries[i] * entries[j] * entries[k]

Functional style

Some entertainment for the ones that prefer a more functional style of coding. The solutions generates all pairs that sum up to 2020, and then filters on which pair that is present in the list.

def part1functional(arr):
    return [
        a * b
        for (a,b)
        in filter(
            lambda (a,b): a in arr and b in arr,
            zip(range(0, 1010, 1), range(2020, 1010, -1))
        )
    ][0]