aoc

commit 3c39a9143cad06f3e05d3c7478d8313380003361 (patch)
parent 7e1f3d0f3d281d19fe34d714b4838f9aa8206821
Author: Alex Karle <alex@alexkarle.com>
Date:   Mon,  6 Dec 2021 00:59:24 -0500

day6: Add hyper-optimized C solution

Ok, so the parser was a huge struggle here and I was *reallllly* tempted
to just rewrite the `input` to be split on newlines (using sed)... but I
figured part of the "learning" is learning how to tokenize strings in C
and not relying on existing tools...

Other hiccups:

* b required the use of long longs due to overflow
* it took FOREVER to realize that despite fish aging to the '6th' index,
  I really needed them to age to the 7th which is the 6th on the next
  iteration...

Diffstat:
A
6/a.c
 | 
37
+++++++++++++++++++++++++++++++++++++
A
6/b.c
 | 
39
+++++++++++++++++++++++++++++++++++++++
M
Makefile
 | 
2
+-

3 files changed, 77 insertions(+), 1 deletion(-)
diff --git a/6/a.c b/6/a.c
@@ -0,0 +1,37 @@
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(void) {
+    int counts[9] = {0};
+
+    /* Wow, the parser is more complex than the algorithm :( */
+    char *line = NULL;
+    size_t linesize = 0;
+    getline(&line, &linesize, stdin);
+    char *p;
+    for (p = strtok(line, ","); p; p = strtok(NULL, ",")) {
+        counts[atoi(p)]++;
+    }
+    free(line);
+
+    /* Phew, made it */
+    for (int i = 0; i < 80; i++) {
+        /* Rather than pop & append, just edit in place and rotate
+         * the start index in use; i.e. on day 2, idx 1 is '0'.
+         *
+         * In fact, really all we need to do is add the current
+         * "populating fish" (mod 0) to the 7th index (which will
+         * be the 6th index on the next "lifecycle".
+         * */
+        counts[(i + 7) % 9] += counts[i % 9];
+    }
+    
+    int sum = 0;
+    for (int i = 0; i < 9; i++) {
+        sum += counts[i];
+    }
+    printf("%d\n", sum);
+
+    return 0;
+}
diff --git a/6/b.c b/6/b.c
@@ -0,0 +1,39 @@
+/* NOTE: only diff from a.c is the 256 rotation and use of a long long for
+ * big vals (tm). Duplicated for the sake of the build system :) */
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(void) {
+    unsigned long long counts[9] = {0};
+
+    /* Wow, the parser is more complex than the algorithm :( */
+    char *line = NULL;
+    size_t linesize = 0;
+    getline(&line, &linesize, stdin);
+    char *p;
+    for (p = strtok(line, ","); p; p = strtok(NULL, ",")) {
+        counts[atoi(p)]++;
+    }
+    free(line);
+
+    /* Phew, made it */
+    for (int i = 0; i < 256; i++) {
+        /* Rather than pop & append, just edit in place and rotate
+         * the start index in use; i.e. on day 2, idx 1 is '0'.
+         *
+         * In fact, really all we need to do is add the current
+         * "populating fish" (mod 0) to the 7th index (which will
+         * be the 6th index on the next "lifecycle".
+         * */
+        counts[(i + 7) % 9] += counts[i % 9];
+    }
+    
+    unsigned long long sum = 0;
+    for (int i = 0; i < 9; i++) {
+        sum += counts[i];
+    }
+    printf("%llu\n", sum);
+
+    return 0;
+}
diff --git a/Makefile b/Makefile
@@ -11,7 +11,7 @@
 CFLAGS = -g -O2 -Wall -Wpedantic -Wextra
 DAY = *
 
-TARGETS = 1/a 1/b 2/a 2/b 3/a 5/a 5/b
+TARGETS = 1/a 1/b 2/a 2/b 3/a 5/a 5/b 6/a 6/b
 
 .PHONY: build
 build: $(TARGETS)