Advent of Code 2020, Day 9 -- Encoding Error

Dec 9th, 2020

3 min read

Advent Of Code

Python solutions to Advent of Code 2020, day 9.

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 9 can be found on Github.

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

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

Solution, part 1

Now we're hacking the airplane, which just seems... wrong? 😆

Today's puzzle wasn't quite as difficult as yesterday's, and I ended up with some decently clean code. This is still brute-forced, but runs relatively quickly.

For the first part of today's puzzle, I took a cue from my Day 1 refactor of part 1. I decided to make a dictionary of {target_number - iterated_number: iterated_number}, where the target number is the number at the index directly after the preamble. That way, I can do a quick check to see if the current iterated number has already been found as a number that sums to the target number.

If there are two numbers found that sum to the target number, we want to loop through again, this time with the first number removed from the data list. So, I call encryption_error again with the slice data[1:].

Eventually, we'll find a situation where we get to the end of the preamble without finding a number that sums to the target number. I've added a check to see if we've reached the end of the preamble list (i == preamble[-1]) and if so, it returns the target number, which is the answer to the puzzle.

puzzle_input = open("input.txt", "r")
lines = [int(x) for x in puzzle_input.read().strip().split("\n")]

# Subtracts each number in the preamble by the following number
# at index p. This number is stored in the "sums" dictionary.
# If the number is already in the dictionary, that means that
# data[p] is a valid number. Call encryption_error recursively
# with the first number sliced off of the data list.
#
# If number i in the preamble is the same as the slice preamble[-1],
# that means we've reached the end of the preamble without finding
# a matching number, so the current number is invalid, return it.
def encryption_error(data, p):
    preamble = data[:p]
    target_num = data[p]
    sums = {}
    for i in preamble:
        if i in sums:
            # print(num, (i, sums[i]))
            data = data[1:]
            return encryption_error(data, p)
        elif i == preamble[-1]:
            return target_num
        else:
            sums[target_num - i] = i


print(encryption_error(lines, 25))

Solution, part 2

For part 2, I can use my function for part 1 without any alterations!

I'm going to use the number returned from encryption_error. First, I'm going to limit the data list to numbers that are less than the target number since we're looking for numbers that sum to the target number.

Then, I'm going to iterate over the data list. d is going to be the first number in the range to try adding together to reach the target number. The next loop creates a range over the rest of the data list, that incrementally sums the range and adds it to d.

This might make more sense with an example using test data:

35 + [20] = 55
35 + [20, 15] = 70
35 + [20, 15, 25] = 95
35 + [20, 15, 25, 47] = 142
20 + [15] = 35
20 + [15, 25] = 60
20 + [15, 25, 47] = 107
20 + [15, 25, 47, 40] = 147
15 + [25] = 40
15 + [25, 47] = 87
15 + [25, 47, 40] = 127

This loop would go to the end of the list, but I'm exiting out of the inner loop once the total gets higher than our target number. This minor optimization works because the data list is roughly in order. It's not totally sorted, but we can reasonably assume that numbers towards the end of the list will be higher than ones at the beginning.

Once we find an instance of total being equal to the target number, we return the minimum value of the entire total range added to the maximum value of the entire total range.

# Use encryption_error to find the invalid number.
# First, filtering data to only use numbers smaller than the
# target number. Then, getting the sum of number d, end number
# data[i], and all numbers in-between.
#
# If total == num, return the sum of the smallest and largest numbers
# in the list.
def invalid_number_sum(data, num):
    data = [x for x in data if x < num]
    length = len(data)
    for (s, d) in enumerate(data):
        start = s + 1  # Start point for addition range.
        for i in range(start, length):
            end = i + 1
            total = d + sum(data[start:end])
            if total > num:
                break
            if total == num:
                return min(data[s:end]) + max(data[s:end])


print(invalid_number_sum(lines, encryption_error(lines, 25)))

Overall, I had a lot of fun with today's puzzle! Also, I gave up after Day 8 last year, so this is the farthest I've ever gotten in Advent of Code!

mary.codes