While I suspect this can actually be executed as a Fast Fourier transform, I found using numpy matrix multiplications plenty fast enough for the first part.
I create a $N x N$ matrix for the input signal, and a matching matrix of multiplication patterns (with judicious applications of np.tile() and np.repeat()). Then both matrices can be multiplied, after which we sum each row, and take the last digit (after dropping the signs) as the output signal.
Note that this is a $\mathcal{O}(n^2)$ operation, and not an actual Fast Fourier transform; I only named the function fft() because it is the acronym for Flawed Frequency Transmission :-P
import numpy as np
def readsignal(line: str) -> np.array:
return np.array([int(d) for d in line])
_pattern = np.array([0, 1, 0, -1])
def transform(signal: np.array, pattern: np.array = _pattern) -> np.array:
n = signal.size
matrix = np.tile(signal, (n, 1)) # N x N matrix
patterns = np.zeros(matrix.shape, matrix.dtype)
for i in range(1, n + 1):
tilecount = int(np.ceil(n / ((i * pattern.size) - 1)))
patterns[i - 1, :] = np.tile(np.repeat(pattern, i), tilecount)[1 : 1 + n]
return np.abs((matrix * patterns).sum(axis=1)) % 10
def fft(signal: np.array, repeats: int) -> np.array:
for _ in range(repeats):
signal = transform(signal)
return signal
def str8top(signal: np.array) -> str:
return "".join(map(str, signal[:8]))
assert str8top(fft(readsignal("12345678"), 4)) == "01029498"
part1_tests = {
"80871224585914546619083218645595": "24176176",
"19617804207202209144916044189917": "73745418",
"69317163492948606335995924319873": "52432133",
}
for testnum, expected in part1_tests.items():
assert str8top(fft(readsignal(testnum), 100)) == expected
import aocd
data = aocd.get_data(day=16, year=2019)
print("Part 1:", str8top(fft(readsignal(data), 100)))
Part 1: 58100105
While my poor-mans fft() function is fast enough for part 1, part 2 demonstrates why you want to find an actual FFT implementation. FFT is fast because it avoids a $\mathcal{O}(n^2)$ multiplication matrix, giving you the results in $\mathcal{O}(n\log{}n)$ instead.
The input data is 650 digits long, so for part 1 we had to process a 650x650 matrix multiplication, so roughly 422500 operations. For part 2 that turns into a 6.5 million digit monstrosity, and suddenly we are asking numpy to perform a 42250 billion calculations. We clearly need to find a similar shortcut!
That shortcut is in the offset and the way the pattern is repeated. First note that for any digit $d$, the first $d - 1$ digits are ignored because they are multiplied by 0 in the pattern. Next, digit $d$ and the next $d$ digits are all going to be 1. At an offset 7 digits long, that means that the next several million digits are all set to 1, and we only have 6.5 million digits. We also ignored the first offset digits by multiplying them with 0, so all we are doing is summing the digits starting at offset to determine the output digits.
That's the per-digit sum. So, for input[offset], the output digit sum(input[offset:]) % 10. The next digit at offset + 1 is sum(input[offset + 1:]) % 10, and so on. So the digit at position $k + 1$ is the same value as $k$ but with the digit at position $k$ subtracted. So all we have to do is start at digit -1, add and add the digit at -2 to produce the second last digit. Then add digit -3 to create the next digit from the end. It's a cumulative sum of digits starting at the end, up to offset!
1000 repeated cumulative sums of the digits from offset onwards is easy-peasy..
REPEAT = 10_000
def offsetfft(signal: np.array, repeat: int = 100) -> np.array:
# digits to number
offset = (10 ** np.arange(6, -1, -1) * signal[:7]).sum()
offsetsignal = np.tile(signal, REPEAT)[offset:]
for _ in range(repeat):
offsetsignal = np.cumsum(offsetsignal[::-1])[::-1] % 10
return offsetsignal
part2_tests = {
"03036732577212944063491565474664": "84462026",
"02935109699940807407585447034323": "78725270",
"03081770884921959731165446850517": "53553731",
}
for testnum, expected in part2_tests.items():
assert str8top(offsetfft(readsignal(testnum))) == expected
print("Part 2:", str8top(offsetfft(readsignal(data), 100)))
Part 2: 41781287