{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Day 16\n",
"\n",
"- https://adventofcode.com/2019/day/16\n",
"\n",
"While I suspect this can actually be executed as a [Fast Fourier transform](https://en.wikipedia.org/wiki/Fast_Fourier_transform), I found using numpy matrix multiplications plenty fast enough for the first part.\n",
"\n",
"I create a $N x N$ matrix for the input signal, and a matching matrix of multiplication patterns (with judicious applications of [`np.tile()`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.tile.html) and [`np.repeat()`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.repeat.html)). 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.\n",
"\n",
"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\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"\n",
"def readsignal(line: str) -> np.array:\n",
" return np.array([int(d) for d in line])\n",
"\n",
"\n",
"_pattern = np.array([0, 1, 0, -1])\n",
"\n",
"\n",
"def transform(signal: np.array, pattern: np.array = _pattern) -> np.array:\n",
" n = signal.size\n",
" matrix = np.tile(signal, (n, 1)) # N x N matrix\n",
" patterns = np.zeros(matrix.shape, matrix.dtype)\n",
" for i in range(1, n + 1):\n",
" tilecount = int(np.ceil(n / ((i * pattern.size) - 1)))\n",
" patterns[i - 1, :] = np.tile(np.repeat(pattern, i), tilecount)[1 : 1 + n]\n",
" return np.abs((matrix * patterns).sum(axis=1)) % 10\n",
"\n",
"\n",
"def fft(signal: np.array, repeats: int) -> np.array:\n",
" for _ in range(repeats):\n",
" signal = transform(signal)\n",
" return signal\n",
"\n",
"\n",
"def str8top(signal: np.array) -> str:\n",
" return \"\".join(map(str, signal[:8]))\n",
"\n",
"\n",
"assert str8top(fft(readsignal(\"12345678\"), 4)) == \"01029498\"\n",
"part1_tests = {\n",
" \"80871224585914546619083218645595\": \"24176176\",\n",
" \"19617804207202209144916044189917\": \"73745418\",\n",
" \"69317163492948606335995924319873\": \"52432133\",\n",
"}\n",
"for testnum, expected in part1_tests.items():\n",
" assert str8top(fft(readsignal(testnum), 100)) == expected"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import aocd\n",
"\n",
"data = aocd.get_data(day=16, year=2019)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Part 1: 58100105\n"
]
}
],
"source": [
"print(\"Part 1:\", str8top(fft(readsignal(data), 100)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Part 2\n",
"\n",
"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.\n",
"\n",
"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!\n",
"\n",
"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_**.\n",
"\n",
"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!\n",
"\n",
"1000 repeated cumulative sums of the digits from `offset` onwards is easy-peasy..\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"REPEAT = 10_000\n",
"\n",
"\n",
"def offsetfft(signal: np.array, repeat: int = 100) -> np.array:\n",
" # digits to number\n",
" offset = (10 ** np.arange(6, -1, -1) * signal[:7]).sum()\n",
" offsetsignal = np.tile(signal, REPEAT)[offset:]\n",
" for _ in range(repeat):\n",
" offsetsignal = np.cumsum(offsetsignal[::-1])[::-1] % 10\n",
" return offsetsignal\n",
"\n",
"\n",
"part2_tests = {\n",
" \"03036732577212944063491565474664\": \"84462026\",\n",
" \"02935109699940807407585447034323\": \"78725270\",\n",
" \"03081770884921959731165446850517\": \"53553731\",\n",
"}\n",
"for testnum, expected in part2_tests.items():\n",
" assert str8top(offsetfft(readsignal(testnum))) == expected"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Part 2: 41781287\n"
]
}
],
"source": [
"print(\"Part 2:\", str8top(offsetfft(readsignal(data), 100)))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.0"
}
},
"nbformat": 4,
"nbformat_minor": 2
}