# Advent of Code 2020: Day 9

Day 9 is two challenges about looking across lists of ints to find pairs or slices with a given sum.

## Challenge

The puzzle can be found here. Stripping away the story, I’m given a list of integers and asked to find features in them. For part one, I’m given a window of 25. Starting at the 26th number, there should be two numbers in the 25 proceeding numbers that sum to that number. I’m asked to walk the list and find the first number where that is not the case. For part two, I need to find a contiguous group of numbers that sum to the answer to part one.

## Solution

### Part 1

For part one, I’ll read the puzzle input and the window size from `argv`

(because in the examples they use a window of five instead of 25). I’ll loop over `i`

from that window size to the end of the array, and for each `i`

, I’ll check from `nums[i-window:i]`

for pairs of numbers that total `nums[i]`

. I’ll get those pairs using `combinations`

from itertools.

Because I love list comprehensions, I can check all sums for each `i`

in one line:

```
for i in range(window, len(nums)):
if all([x + y != nums[i] for x,y in combinations(nums[i-window:i], 2)]):
break
```

At that point, I’ve got part one.

### Part 2

Next I’m asked to find a subsection of the list that contains numbers adding up to the part one answer. To find the starting index of that subsection, I’ll walk the list again with an `i`

, and for each `i`

, I’ll loop over `j`

from `i`

to the end of the list, checking if `sum(nums[i:j]) == target`

.

```
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if sum(nums[i:j]) == target:
print(f'Part 2: {min(nums[i:j]) + max(nums[i:j])}')
sys.exit()
```

### Final Code

The first part returns instantly, which the second runs for a second:

```
$ time python3 day9.py 09-puzzle.txt 25
Part 1: 393911906
Part 2: 59341885
real 0m0.900s
user 0m0.892s
sys 0m0.008s
```

```
#!/usr/bin/env python3
import sys
from itertools import combinations
with open(sys.argv[1], "r") as f:
nums = list(map(int, f.readlines()))
window = int(sys.argv[2])
for i in range(window, len(nums)):
if all([x + y != nums[i] for x, y in combinations(nums[i - window : i], 2)]):
break
target = nums[i]
print(f"Part 1: {target}")
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if sum(nums[i:j]) == target:
print(f"Part 2: {min(nums[i:j]) + max(nums[i:j])}")
sys.exit()
```