Advent of Code: 2020 Day 09 solutions

⚠️ SPOILER ALERT ⚠️
This is a post with my solutions and learning 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/2020/day/9.

My programming language of choice is python and all examples below are in python.

TOC

• Key learning
• Puzzle
• Part 1
  • Solution 1: bad
  • Solution 1: good
  • Solution 1: optimized
• Part 2
  • Solution 2

Key learning

• Window sliding

This puzzle teaches us to slide through an list of values using a window. It is possible to solve with nested for-loops and if-statements. But it gets much easier utilizing a window to operate on.

Puzzle

The puzzle is to validate number in a list. A number is valid if it is the sum of any of the 25 immediately previous numbers. All first 25 numbers are counted as valid. The input is a file with one number per line.

Example input:

35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576

Part 1

In part 1 we have to find the first number that is NOT valid.

Parsing input

# Parse directly into ints.
numbers = [
  int(line.strip())
  for line
  in open('09.input', 'r').readlines()
]

Solution (bad)

The first concept is to figure out how to traverse the list and keep track of the 25 previous number. A naive solution is to iterate back to all previous numbers and try out all possible combinations of sums. Here is a example of that naive thinking. I don't even want to think about the time complexity. Though it still solves the puzzle on my computer in an instant.

def part1(numbers):
    # Iterate all numbers
    for i, n in enumerate(numbers):
        # Skip "preamble"
        if i < 25:
            continue

        # Iterate all 25 previous numbers
        is_valid = False
        for j in range(i-25,i):
            # Try out all combinations to sum to n
            for k in range(i-25, i):
                if j != k:
                    if numbers[j] + numbers[k] == n:
                        is_valid = True
                        break
                if is_valid:
                    break
            if is_valid:
                break

        # If is not valid, then we found our answer
        if not is_valid:
            return n
print "Solution part 1: %d" % part1(numbers)

Solution (good)

Using the concept of a sliding window we can create a more performant and clean solution. The sliding window is a list containing the previous 25 elements.

After each iteration we append the current number at the end and pop the first element to keep the size consistent of 25 elements.

We can also improve our validation. One way is to calculate the differences between the values in the window with the current number n. If the lists of differences intersects with the window, then there are two values that sum up to n. Note: this assumes that it DOES NOT exist numbers that are half of n. Works on my input, might not work on yours.

from collections import deque
def part1(numbers):
    window = numbers[:25]

    for n in numbers[25:]:
        differences = set([n - x for x in window])
        is_valid = len(window.intersection(differences))

        if not is_valid:
            return n          # Found answer
        else:
            window.append(n)  # Append n at end of list
            window.pop(0)     # Remove first element of list
print "Solution part1: %d" % part1(numbers)

Solution (optimized)

If we think about performance it cost O(N) to pop the first element in lists. Using a deque it lowers the time-complexity. Deque:

appends and pops from either side of the deque with approximately the same O(1) performance in either direction

Deque also has a maxlen parameter which ensures that the window stays at a certain size.

To optimize the validation we could reuse the code from Day 01. Essentially it just gives us a early return once a valid number is found with worst case O(N) time complexity. The previous example requires iterating the window once and then doing an intersection. Set intersection has worst case of O(N^2) which looks slower. But the window size is set to 25, which makes the worst case O(500) which simplifies to O(1). So both variants have equal time complexity.

Here is the code:

from collections import deque

def valid(arr, n):
    differences = set()
    for x in arr:
        if n - x in differences:
            return True
        differences.add(x)
    return False

def part1(numbers):
    window = deque(numbers[:25], maxlen=25)
    for n in numbers[25:]:
        if not valid(window, n):
            return n
        window.append(n)
print "Solution part1: %d" % part1(numbers)

Part 2

In part 2 we use the invalid number we find in part 1. We have now to find a contigous set of at least two numbers which sum to that invalid number. The answer is the sum of the largest and smallest number in that set.

Using the learning from part 1 we can jump into the clean solution using a sliding window. While iterating the list of numbers we push the current n to the window. Then if the window-sum is too big we pop the first element. And continue doing so as until the window-sum is equal to our invalid number, or smaller. We can keep track of the window-sum in a variable.

Solution

def part2(numbers, needle):
    window = deque()
    window_sum = 0                            # Sum for numbers currently in window

    for n in numbers:
        window.append(n)
        window_sum += n

        while window_sum > needle:            # Pop head until window_sum is within limit
            window_sum -= window.popleft()
        if window_sum == needle:              # Result found
            return max(window) + min(window)  # Sum the smallest and largest

solution_part_1 = part1(numbers)
print "Solution part 2: %d " part2(numbers, solution_part_1)

Thanks for reading!

I hope these solutions were insightful for you.

Complete code can be found at: github.com/cNille/AdventOfCode/blob/master/2020/09.py