commit ef73ac2bc8dbde3b9fbf91821c925670b0cfea75
parent d670b95b371a9ee99df7b2f0e4c373fd57e48220
Author: Louis Burda <quent.burda@gmail.com>
Date: Sat, 25 Mar 2023 01:40:38 +0100
Add day 16
Diffstat:
| A | 16/info.mk | | | 3 | +++ |
| A | 16/input | | | 2 | ++ |
| A | 16/main.c | | | 177 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 16/part1 | | | 95 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 16/part2 | | | 32 | ++++++++++++++++++++++++++++++++ |
| A | 16/test1 | | | 1 | + |
| A | 16/test2 | | | 1 | + |
7 files changed, 311 insertions(+), 0 deletions(-)
diff --git a/16/info.mk b/16/info.mk
@@ -0,0 +1,3 @@
+16_SRC = 16/main.c common/main.c common/aoc.c common/util.c
+16_SRC += lib/libdvec/build/libdvec.a lib/liballoc/build/liballoc.a
+16_HDR = common/aoc.h common/util.h
diff --git a/16/input b/16/input
@@ -0,0 +1,2 @@
+59769638638635227792873839600619296161830243411826562620803755357641409702942441381982799297881659288888243793321154293102743325904757198668820213885307612900972273311499185929901117664387559657706110034992786489002400852438961738219627639830515185618184324995881914532256988843436511730932141380017180796681870256240757580454505096230610520430997536145341074585637105456401238209187118397046373589766408080120984817035699228422366952628344235542849850709181363703172334788744537357607446322903743644673800140770982283290068502972397970799328249132774293609700245065522290562319955768092155530250003587007804302344866598232236645453817273744027537630
+
diff --git a/16/main.c b/16/main.c
@@ -0,0 +1,177 @@
+#include "allocator.h"
+#include "util.h"
+#include "aoc.h"
+#include "dvec.h"
+
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+
+static const int freq[] = { 0, 1, 0, -1 };
+
+void
+parse_input(struct dvec *phases)
+{
+ const char *c, *sep;
+ int *val;
+
+ sep = strchr(aoc.input, '\n');
+ assert(sep != NULL);
+
+ for (c = aoc.input; c < sep; c++) {
+ val = dvec_add_slot(phases, NULL);
+ *val = *c - '0';
+ }
+}
+
+void
+fft(struct dvec *phases, size_t rounds)
+{
+ struct dvec copy;
+ size_t r, i, k, l;
+ ssize_t sum;
+ int digit;
+ int *val;
+
+ dvec_init(©, sizeof(int), 0, &stdlib_strict_heap_allocator);
+
+ for (r = 0; r < rounds; r++) {
+ dvec_copy(©, phases);
+
+ for (i = 0; i < copy.len; i++) {
+ sum = 0;
+ for (k = 0; k < copy.len; k++) {
+ l = (k + 1) / (i + 1);
+ digit = *(int *)dvec_at(©, k);
+ sum += freq[l % 4] * digit;
+ }
+ sum = ABS(sum) % 10;
+ val = dvec_at(phases, i);
+ *val = (int) sum;
+ }
+ }
+
+ dvec_deinit(©);
+}
+
+void
+fft_dup(struct dvec *phases, size_t offset, size_t rounds, size_t dup)
+{
+ size_t r, i, len, lutlen;
+ int *lut, *lutc, *lutp;
+ int digit, *slot;
+
+ /* | a b c
+ * --+------------------------
+ * 1 | a+b+c b+c c
+ * 2 | a+2b+3c b+2c c
+ * n |a+nb+n(n+1)/2c b+nc c
+ *
+ * a+sum(1)b+sum(sum(1))c .. not nice
+ *
+ * sum(1): n
+ * sum(sum(1)): n(n+1)/2
+ * sum(sum(sum(1))): (K2+K1)/2 = (n^2+n)/2 + (n^3-n)/6
+ *
+ * .. calculation possible but not practically feasible since we
+ * would have to do 10000..th sum() .. will have to use a lookup table
+ */
+
+ len = phases->len * dup;
+ assert(offset >= len / 2 && offset < len);
+
+ lutlen = len - offset;
+ lut = malloc(lutlen * sizeof(int) * (rounds + 1));
+ assert(lut != NULL);
+
+ /* top row */
+ for (i = 0; i < lutlen; i++) {
+ digit = *(int *)dvec_at(phases, (i + offset) % phases->len);
+ lut[i] = digit;
+ }
+
+ /* right column */
+ digit = *(int *)dvec_at(phases, (len - 1) % phases->len);
+ for (r = 0; r < rounds; r++) {
+ lut[(r + 1) * lutlen + lutlen - 1] = digit;
+ }
+
+ for (r = 0; r < rounds; r++) {
+ lutp = &lut[r * lutlen + lutlen - 2];
+ lutc = &lut[(r + 1) * lutlen + lutlen - 2];
+ for (i = 1; i < lutlen; i++, lutp--, lutc--)
+ lutc[0] = (lutp[0] + lutc[1]) % 10;
+ }
+
+ dvec_clear(phases);
+ for (i = 0; i < 8; i++) {
+ slot = dvec_add_slot(phases, NULL);
+ *slot = lut[rounds * lutlen + i];
+ }
+
+ free(lut);
+}
+
+void
+part1(void)
+{
+ struct dvec phases;
+ char *answer;
+ size_t i;
+ int digit;
+
+ dvec_init(&phases, sizeof(int), 64, &stdlib_strict_heap_allocator);
+
+ parse_input(&phases);
+
+ fft(&phases, 100);
+
+ answer = malloc(9);
+ for (i = 0; i < 8; i++) {
+ digit = *(int *)dvec_at(&phases, i);
+ answer[i] = '0' + (char) digit;
+ }
+ answer[i] = 0;
+
+ aoc.answer = answer;
+ aoc.solution = "29956495";
+
+ dvec_deinit(&phases);
+}
+
+void
+part2(void)
+{
+ struct dvec phases;
+ char *answer;
+ int digit;
+ size_t offset;
+ size_t base;
+ size_t i;
+
+ dvec_init(&phases, sizeof(int), 64, &stdlib_strict_heap_allocator);
+
+ parse_input(&phases);
+
+ base = 1;
+ offset = 0;
+ for (i = 0; i < 7; i++) {
+ digit = *(int *)dvec_at(&phases, 6 - i);
+ offset += base * (size_t) digit;
+ base *= 10;
+ }
+
+ fft_dup(&phases, offset, 100, 10000);
+
+ answer = malloc(9);
+ for (i = 0; i < 8; i++) {
+ digit = *(int *)dvec_at(&phases, i);
+ answer[i] = '0' + (char) digit;
+ }
+ answer[i] = 0;
+
+ aoc.answer = answer;
+ aoc.solution = "";
+
+ dvec_deinit(&phases);
+}
diff --git a/16/part1 b/16/part1
@@ -0,0 +1,95 @@
+--- Day 16: Flawed Frequency Transmission ---
+
+You're 3/4ths of the way through the gas giants. Not only do roundtrip signals to Earth take five
+hours, but the signal quality is quite bad as well. You can clean up the signal with the Flawed
+Frequency Transmission algorithm, or FFT.
+
+As input, FFT takes a list of numbers. In the signal you received (your puzzle input), each number
+is a single digit: data like 15243 represents the sequence 1, 5, 2, 4, 3.
+
+FFT operates in repeated phases. In each phase, a new list is constructed with the same length as
+the input list. This new list is also used as the input for the next phase.
+
+Each element in the new list is built by multiplying every value in the input list by a value in a
+repeating pattern and then adding up the results. So, if the input list were 9, 8, 7, 6, 5 and the
+pattern for a given element were 1, 2, 3, the result would be 9*1 + 8*2 + 7*3 + 6*1 + 5*2 (with each
+input element on the left and each value in the repeating pattern on the right of each
+multiplication). Then, only the ones digit is kept: 38 becomes 8, -17 becomes 7, and so on.
+
+While each element in the output array uses all of the same input array elements, the actual
+repeating pattern to use depends on which output element is being calculated. The base pattern is 0,
+1, 0, -1. Then, repeat each value in the pattern a number of times equal to the position in the
+output list being considered. Repeat once for the first element, twice for the second element, three
+times for the third element, and so on. So, if the third element of the output list is being
+calculated, repeating the values would produce: 0, 0, 0, 1, 1, 1, 0, 0, 0, -1, -1, -1.
+
+When applying the pattern, skip the very first value exactly once. (In other words, offset the whole
+pattern left by one.) So, for the second element of the output list, the actual pattern used would
+be: 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0, -1, -1, ....
+
+After using this process to calculate each element of the output list, the phase is complete, and
+the output list of this phase is used as the new input list for the next phase, if any.
+
+Given the input signal 12345678, below are four phases of FFT. Within each phase, each output digit
+is calculated on a single line with the result at the far right; each multiplication operation shows
+the input digit on the left and the pattern value on the right:
+
+Input signal: 12345678
+
+1*1 + 2*0 + 3*-1 + 4*0 + 5*1 + 6*0 + 7*-1 + 8*0 = 4
+1*0 + 2*1 + 3*1 + 4*0 + 5*0 + 6*-1 + 7*-1 + 8*0 = 8
+1*0 + 2*0 + 3*1 + 4*1 + 5*1 + 6*0 + 7*0 + 8*0 = 2
+1*0 + 2*0 + 3*0 + 4*1 + 5*1 + 6*1 + 7*1 + 8*0 = 2
+1*0 + 2*0 + 3*0 + 4*0 + 5*1 + 6*1 + 7*1 + 8*1 = 6
+1*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*1 + 7*1 + 8*1 = 1
+1*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*0 + 7*1 + 8*1 = 5
+1*0 + 2*0 + 3*0 + 4*0 + 5*0 + 6*0 + 7*0 + 8*1 = 8
+
+After 1 phase: 48226158
+
+4*1 + 8*0 + 2*-1 + 2*0 + 6*1 + 1*0 + 5*-1 + 8*0 = 3
+4*0 + 8*1 + 2*1 + 2*0 + 6*0 + 1*-1 + 5*-1 + 8*0 = 4
+4*0 + 8*0 + 2*1 + 2*1 + 6*1 + 1*0 + 5*0 + 8*0 = 0
+4*0 + 8*0 + 2*0 + 2*1 + 6*1 + 1*1 + 5*1 + 8*0 = 4
+4*0 + 8*0 + 2*0 + 2*0 + 6*1 + 1*1 + 5*1 + 8*1 = 0
+4*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*1 + 5*1 + 8*1 = 4
+4*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*0 + 5*1 + 8*1 = 3
+4*0 + 8*0 + 2*0 + 2*0 + 6*0 + 1*0 + 5*0 + 8*1 = 8
+
+After 2 phases: 34040438
+
+3*1 + 4*0 + 0*-1 + 4*0 + 0*1 + 4*0 + 3*-1 + 8*0 = 0
+3*0 + 4*1 + 0*1 + 4*0 + 0*0 + 4*-1 + 3*-1 + 8*0 = 3
+3*0 + 4*0 + 0*1 + 4*1 + 0*1 + 4*0 + 3*0 + 8*0 = 4
+3*0 + 4*0 + 0*0 + 4*1 + 0*1 + 4*1 + 3*1 + 8*0 = 1
+3*0 + 4*0 + 0*0 + 4*0 + 0*1 + 4*1 + 3*1 + 8*1 = 5
+3*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*1 + 3*1 + 8*1 = 5
+3*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*0 + 3*1 + 8*1 = 1
+3*0 + 4*0 + 0*0 + 4*0 + 0*0 + 4*0 + 3*0 + 8*1 = 8
+
+After 3 phases: 03415518
+
+0*1 + 3*0 + 4*-1 + 1*0 + 5*1 + 5*0 + 1*-1 + 8*0 = 0
+0*0 + 3*1 + 4*1 + 1*0 + 5*0 + 5*-1 + 1*-1 + 8*0 = 1
+0*0 + 3*0 + 4*1 + 1*1 + 5*1 + 5*0 + 1*0 + 8*0 = 0
+0*0 + 3*0 + 4*0 + 1*1 + 5*1 + 5*1 + 1*1 + 8*0 = 2
+0*0 + 3*0 + 4*0 + 1*0 + 5*1 + 5*1 + 1*1 + 8*1 = 9
+0*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*1 + 1*1 + 8*1 = 4
+0*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*0 + 1*1 + 8*1 = 9
+0*0 + 3*0 + 4*0 + 1*0 + 5*0 + 5*0 + 1*0 + 8*1 = 8
+
+After 4 phases: 01029498
+
+Here are the first eight digits of the final output list after 100 phases for some larger inputs:
+
+
+ - 80871224585914546619083218645595 becomes 24176176.
+
+ - 19617804207202209144916044189917 becomes 73745418.
+
+ - 69317163492948606335995924319873 becomes 52432133.
+
+
+After 100 phases of FFT, what are the first eight digits in the final output list?
+
+
diff --git a/16/part2 b/16/part2
@@ -0,0 +1,32 @@
+--- Part Two ---
+
+Now that your FFT is working, you can decode the real signal.
+
+The real signal is your puzzle input repeated 10000 times. Treat this new signal as a single input
+list. Patterns are still calculated as before, and 100 phases of FFT are still applied.
+
+The first seven digits of your initial input signal also represent the message offset. The message
+offset is the location of the eight-digit message in the final output list. Specifically, the
+message offset indicates the number of digits to skip before reading the eight-digit message. For
+example, if the first seven digits of your initial input signal were 1234567, the eight-digit
+message would be the eight digits after skipping 1,234,567 digits of the final output list. Or, if
+the message offset were 7 and your final output list were 98765432109876543210, the eight-digit
+message would be 21098765. (Of course, your real message offset will be a seven-digit number, not a
+one-digit number like 7.)
+
+Here is the eight-digit message in the final output list after 100 phases. The message offset given
+in each input has been highlighted. (Note that the inputs given below are repeated 10000 times to
+find the actual starting input lists.)
+
+
+ - 03036732577212944063491565474664 becomes 84462026.
+
+ - 02935109699940807407585447034323 becomes 78725270.
+
+ - 03081770884921959731165446850517 becomes 53553731.
+
+
+After repeating your input signal 10000 times and running 100 phases of FFT, what is the eight-digit
+message embedded in the final output list?
+
+
diff --git a/16/test1 b/16/test1
@@ -0,0 +1 @@
+80871224585914546619083218645595
diff --git a/16/test2 b/16/test2
@@ -0,0 +1 @@
+03036732577212944063491565474664
