# Advent of Code 2020 Day 9

## 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.