Advent of Code Day 16

This was a lot of fun to do: Solving the first part was simply writing some careful iterators; and trying to be reasonable about not wasting too much memory. I kicked off a run for the second part while trying to actually solve it and looking for patterns in a second notebook; once I figured it out I just jumped back into the first notebook to solve the problem.

I really appreciate the sample input provided that showed the fact that the last digit was constant, and then realizing that the offset was into the second half of the problem made it much more trivial.

Mildly cleaned up solution, deleting the cells that were simply testing that I understand Python APIs correctly.

In [2]:
def readfile(path):
    with open(path) as input_file: 
        return input_file.read().strip()
In [81]:
from itertools import cycle

base = [0, 1, 0, -1]

def compute(inp, p):
    return abs(sum(a * b for a, b in zip(inp, p))) % 10

def pattern(reps=1):
    b = cycle(base)
    start = True
    for cur in b:
        for _ in range(reps):
            if start:
                start = False
                continue
            yield cur

def phase(inp):
    for i, val in enumerate(inp):
        yield compute(inp, pattern(i + 1))

def fft(inp, phases=4):
    for _ in range(phases):
        inp = list(phase(inp))

    return "".join(str(x) for x in inp)
In [82]:
fft(range(1, 9))
Out[82]:
'01029498'
In [83]:
input16 = (readfile("AoC/input16.txt"))
In [84]:
parsed16 = [int(x) for x in input16]
In [119]:
%%time
fft(parsed16, 100)[:8]
CPU times: user 6.49 s, sys: 4 µs, total: 6.49 s
Wall time: 6.5 s
Out[119]:
'94960436'
In [85]:
def limited_cycle(xs, cycles):
    for _ in range(cycles):
        for x in xs:
            yield x
In [86]:
offset = int("".join(input16[:7]))
offset
Out[86]:
5979673
In [112]:
def endphase(inp):
    n = []
    s = 0
    for i in inp[::-1]:
        s += i
        n.append(abs(s) % 10)
    return n[::-1]
        
def endfft(inp, offset, phases):
    inp = inp[offset:]
    for _ in range(phases):
        inp = endphase(inp)
    return inp
In [114]:
endfft(range(1, 9), 4, 4)
Out[114]:
[9, 4, 9, 8]
Out[114]:
[9, 4, 9, 8]
In [117]:
%%time
endfft(list(limited_cycle(parsed16, 10000)), offset, 100)[:8]
CPU times: user 9.06 s, sys: 224 ms, total: 9.28 s
Wall time: 9.34 s
Out[117]:
[5, 7, 7, 6, 2, 7, 5, 6]