day9.md

jupyter
jupytext kernelspec formats text_representation ipynb,md extension format_name format_version jupytext_version .md markdown 1.2 1.6.0 display_name language name Python 3 python python3

Day 9

https://adventofcode.com/2020/day/9

---

Part 1

from IPython.core.debugger import set_trace
from itertools import combinations
import random

def massage_input(i):
    i = [int(x) for x in i.splitlines()]
    return i

def find_sum_terms(prev_nbrs, target_sum):
    for combo in combinations(prev_nbrs, 2):
        if combo[0] != combo[1]:
            if combo[0] + combo[1] == target_sum:
                return (combo[0], combo[1])
    return False

def part1(p, length_preamble):
    p = massage_input(p)
    pointer = length_preamble
    while pointer < len(p):
        nbrs_to_search = p[pointer-length_preamble:pointer]
        assert len(nbrs_to_search) == length_preamble
        found_nbrs = find_sum_terms(nbrs_to_search, target_sum=p[pointer])
        if not found_nbrs:
            return p[pointer], pointer, nbrs_to_search
        pointer += 1
    return ...

Understanding the problem:

l = list(range(1,20)) + list(range(21,26))
random.shuffle(l)
l
for x in [20] + l:
    print(x, end = ', ')

i = 1
l = list(range(1,20)) + list(range(21,26))
random.shuffle(l)
for x in [20] + l:
    print(f'{i}: {x}')
    i += 1

i = 1
l = list(range(1,20)) + list(range(21,26))
random.shuffle(l)
for x in [20] + l + [45]:
    print(f'{i}: {x}')
    i += 1

find_sum_terms(l, 45)

find_sum_terms(l + [45], 26)

find_sum_terms(l + [45], 65)

find_sum_terms(l + [45], 66)

find_sum_terms(l + [45], 64)

Possible curveballs for part 2:

• product instead of sum
  • or other change of requirement
• change length of pre-amble
• take all numbers that does not meet requirement
• invalidate also the summed-together numbers

Test

tmp = [str(x) + '\n' for x in [20] + l]
test1 = ''
for x in tmp:
    test1 += x
del tmp
del x
length_preamble_test1 = 25

print(test1)

test2 = '''35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576
'''
length_preamble_test2 = 5
faulty_test2 = [127]

massage_input(test2)

assert find_sum_terms([x for x in range(3)], 0) is False
assert find_sum_terms([x for x in range(3)], 1) == (0, 1)
assert find_sum_terms([x for x in range(3)], 2) == (0, 2)
assert find_sum_terms([x for x in range(3)], 3) == (1, 2)
assert find_sum_terms([x for x in range(3)], 4) is False

# %debug
find_sum_terms([47, 25, 15, 20, 35], 40)

# %debug
part1(test2, length_preamble_test2)

# %debug
find_sum_terms([15, 25, 47, 62, 55], 65)

assert (out := part1(test2, length_preamble_test2))[0] == 127, out

Run

with open('day9-input.txt', 'r') as f:
    given = f.read()

part1(given, 25)

---

Part 2

Test

invalid = part1(given, 25)[0]
invalid

def part2(p, invalid):
    p = massage_input(p)
    idx = p.index(invalid)
    
    for start in range(idx-1):
        for end in range(start+2, idx):
            nbrs = p[start:end]
            tmp = sum(p[start:end])
#             set_trace()
            if tmp > invalid:
                break
            if tmp == invalid:
                return p[start:end]

out = part2(test2, 127)
out, sum([min(out), max(out)])

out = part2(given, invalid)
out, sum([min(out), max(out)])