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.
def readfile(path): with open(path) as input_file: return input_file.read().strip()
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)
input16 = (readfile("AoC/input16.txt"))
parsed16 = [int(x) for x in input16]
%%time fft(parsed16, 100)[:8]
CPU times: user 6.49 s, sys: 4 µs, total: 6.49 s Wall time: 6.5 s
def limited_cycle(xs, cycles): for _ in range(cycles): for x in xs: yield x
offset = int("".join(input16[:7])) offset
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
endfft(range(1, 9), 4, 4)
[9, 4, 9, 8]
[9, 4, 9, 8]
%%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
[5, 7, 7, 6, 2, 7, 5, 6]