⚠️ 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.
- 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.
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.
35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576
In part 1 we have to find the first number that is NOT valid.
# Parse directly into ints. numbers = [ int(line.strip()) for line in open('09.input', 'r').readlines() ]
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)
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)
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)
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.
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)
I hope these solutions were insightful for you.
Complete code can be found at: github.com/cNille/AdventOfCode/blob/master/2020/09.py