Part 1

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 while loop.

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])

Part 2

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 = [35], 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 window that will represent we are looking for.
• We create a variable index that will help us iterate over the list of numbers.
• If the sum of elements in window is 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[0]
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.