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