Advent of Code 2020 Day 9
In Day 9, we are given a list of integers and are told that all numbers starting from the 26th one is the sum of two of the previous 25 numbers. All, except for one that we need to determine.
This problem is quite similar to Day 1’s problem, but we now have a moving
window of length 25. So what we have to do now is to loop through all the
numbers starting from the 26th one, and look for a pair of integers in the
previous 25 ones that would add up to the targeted value. Since we don’t know
when this loop will end (we are looking for the first integer that has no such
pair of integers), we can safely assume that we will use a
What is the condition to continue the loop? That we can find two numbers that add up to the target value. So we need a boolean variable that can tell us whether the target value is valid or not (i.e., we have found a pair of integers that add up to the target value).
Then, inside this while loop, we need to create the window that contains the
previous 25 numbers. And finally, we can loop through this window to find the
pair of integers that meet our requirement. If we have found them, we can switch
the value of the boolean variable to
True and look at the next target value.
if the value of the boolean variable is
False, we have found the first target
value that does not match our requirement, and we can print it to the console.
This give us some idea on how to solve the problem. And here is the solution that I propose:
index = 25 window_size = 25 is_valid = True # We can cast all lines into an integer value numbers = [int(number) for number in lines] while is_valid: is_valid = False target_value = numbers[index] window = [int(n) for n in numbers[index-window_size:index]] for number in window: # We change is_valid only if the target value has a valid pair # of integers in the window that add up to target_value # Otherwise, it remains to False and we exit the while loop if target_value - number in window: is_valid = True if is_valid: index += 1 print(numbers[index])
In the second part of Day 9, we are told that there is actually a list of contiguous numbers of size at least two, that add up to the value we have identified in Part 1. This problem can seem complex at first sight: we don’t know the final size of the window.
There is actually a way to solve this problem pretty nicely. Let’s look at the following example. The value we are looking for is 127.
35 # window = , sum = 35 < 127, we add the next value 20 # window = [35, 20], sum = 55 < 127, we add the next value 15 # window = [35, 20, 15], sum = 70 < 127, we add the next value 25 # window = [35, 20, 15, 25], sum = 95 < 127, we add the next value 47 # window = [35, 20, 15, 25, 47], sum = 142 > 127, we remove the first value # window = [20, 15, 25, 47], sum = 107 < 127, we add the next value 40 # window = [20, 15, 25, 47, 40], sum = 147 > 127, we remove the first value # window = [15, 25, 47, 40], sum = 127, end of program. 62 55 ...
The principle of the algorithm is the following:
- We create a variable
windowthat will represent we are looking for.
- We create a variable
indexthat will help us iterate over the list of numbers.
- If the sum of elements in
windowis strictly smaller than the target value, we append the next number in
window, effectively increasing the size of our window.
- If the sum of elements is strictly greater than the target value, we remove
the first element of
window, effectively decreasing the size of our window and shifting it to the right.
Here is the solution in Python:
# This is the value I have found in Part 1 target_value = 20874512 window = numbers index = 1 while sum(window) != target_value: if sum(window) < target_value: window.append(numbers[index]) index += 1 else: window.pop(0) # The question is actually to sum the min and max of the window: print(min(window) + max(window))
Concepts and difficulties
Day 9’s problems do not require the use of some fancy data structures. It is more about pure algorithmic thinking. Part 2 can be puzzling at first sight. We could be brute forcing the problem by looping through all the possibilities (and breaking loops when we have reached a sum greater than the target value). But it is always a good idea to think a little bit more about the characteristics of the problem so that we can design a “nicer” solution.