My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import fileinput
2
3
4PATTERN = [0, 1, 0, -1]
5SIGNAL = [int(s) for s in fileinput.input()[0].strip()]
6
7
8def fft(signal):
9 def coeff(idx, digit):
10 r = ((idx + 1) // (digit + 1)) % 4
11 return PATTERN[r]
12
13 for _ in range(100):
14 for i in range(len(signal)):
15 res = 0
16 for j, d in enumerate(signal):
17 res += coeff(j, i) * d
18
19 signal[i] = abs(res) % 10
20
21 return signal
22
23
24def fft_backhalf(signal):
25 # What pattern?
26 for _ in range(100):
27 partial = 0
28 for i in reversed(range(len(signal) // 2, len(signal))):
29 partial += signal[i]
30 signal[i] = partial % 10
31
32 return signal
33
34
35part_1 = ''.join(str(n) for n in fft(SIGNAL[:]))[:8]
36print "First 8 digits of FFT(input):", part_1
37
38offset = int(''.join(str(n) for n in SIGNAL[:7]))
39part_2 = ''.join(str(n) for n in fft_backhalf(SIGNAL * 10000)[offset:offset+8])
40print "Offset digits of FFT(input * 10000):", part_2