Sean McLemon | Advent of Code

2020-12-09 - Encoding Error

(original .ipynb)

Day 9 is a sequence of integers (mine is here) which represent some data that has been encoded with some kind of cipher. Part 1 involves identifying a weakness in the cipher, by locating the first number in the sequence that isn't the sum of any digits in the previous 25. Part 2 involves finding a run of >1 consecutive numbers which sum to the number identified in Part 1, and adding the smallest and largest values in this sequence.

from itertools import combinations

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

puzzle_input_str = open("puzzle_input/day9.txt", "r").read()

def is_sum_of_two_previous_n_numbers(value, numbers, n):
    combos = combinations(numbers, 2)
    for x,y in combos:
        if x + y == value:
            return True
    return False
    

def part1(preamble, input_str):
    input_numbers = [int(l) for l in input_str.split("\n")]
    numbers = []

    for value in input_numbers:
        if len(numbers) < preamble:
            numbers.append(value)

        else:
            if not is_sum_of_two_previous_n_numbers(value, numbers, preamble):
                return value
            else:
                numbers.append(value)
                numbers.pop(0)
                
    # shouldn't hit this
    return -1

assert 127 == part1(5, test_input_str)
part1(25, puzzle_input_str)

776203571

def part2(target, input_str):
    input_numbers = [int(l) for l in input_str.split("\n")]
    for i, value in enumerate(input_numbers):
        numbers = [value]
        prev_i = i
        
        while sum(numbers) <= target:
            prev_i -= 1
            numbers.append(input_numbers[prev_i])

            if sum(numbers) == target:
                return min(numbers) + max(numbers)
    
    # shouldn't hit this
    return -1

assert 62 == part2(127, test_input_str)
part2(776203571, puzzle_input_str)

104800569