Skip to content
advent of code 2020

day 09

encoding error

approach

the numbers are read into a list, and a Counter holds the previous cap numbers (the preamble size is passed in). for each new number, find_pair checks whether two different numbers in the window add up to it, a two-sum lookup against the counter. if none do, that number is the part 1 answer; otherwise the oldest number leaves the counter and the new one enters.

part 2 looks for a contiguous run that sums to the part 1 number. it grows a window to the right and shrinks it from the left while the sum is too big, then returns the smallest plus the largest number of the run. a comment admits it "stinks of sliding window" but the correctness wasn't proven; it relies on the numbers being positive.

the trick

with positive numbers, a contiguous run with a target sum falls out of a two-pointer window that only ever moves forward.

python
    for end in range(len(l)):
        s += l[end]
        while s > n:
            s -= l[start]
            start += 1
        if s == n:
            sub = l[start:end + 1]
            return max(sub) + min(sub)