aoc

commit 418b3c17748e10aab93cf7ce926aad325ca5cd38 (patch)
parent 5693e1b98bd20d9f7415e647b57419e749ce5c61
Author: Alex Karle <alex@alexkarle.com>
Date:   Fri,  3 Dec 2021 10:26:27 -0500

day3: Add speedy bit-shifting C implementation

This was trickier than expected to write. I originally tried to flip
gamma into epsilon with ~, but that flips all the leading bits too...

Next problem was that I was |= 1<<i, which is *backwards*, since the
most significant bit is first. Since we don't know how many bits wide it
is (we could, I suppose), it's easier to just <<=1 first then |=1.

Diffstat:
A
3/a.c
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
Makefile
 | 
2
+-

2 files changed, 56 insertions(+), 1 deletion(-)
diff --git a/3/a.c b/3/a.c
@@ -0,0 +1,55 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#define MAX_WIDTH 32
+
+int main(void) {
+    /* Key takeaway: if think of the input as a matrix, we can
+     * sum the columns and count the number of entries and know
+     * that if N entries had X sum, there's X 1's and N-X 0's.
+     */
+    int counts[MAX_WIDTH] = { 0 };
+    int c;
+    int col = 0;
+    int n = 0;
+    while ((c = getchar()) != EOF) {
+        switch (c) {
+            case '0':
+                col++;
+                break;
+            case '1':
+                counts[col]++;
+                col++;
+                break;
+            case '\n':
+                /* reset the column */
+                col = 0;
+                n++;
+                break;
+            default:
+                fprintf(stderr, "bad input");
+                exit(1);
+                break;
+        }
+    }
+
+    /* convert counts into a bitmask of 1/0 based on which was max */
+    unsigned int gamma = 0;
+    unsigned int eps = 0;
+    for (int i = 0; i < MAX_WIDTH; i++) {
+        if (counts[i] == 0) {
+            /* assume we see each at least once, so this was the end of width */
+            break;
+        }
+        /* boost the last value to make room for more! */
+        gamma <<= 1;
+        eps <<= 1;
+        if (counts[i] > n / 2) {
+            gamma |= 1;
+        } else {
+            eps |= 1;
+        }
+    }
+    printf("%u\n", eps * gamma);
+    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
+TARGETS = 1/a 1/b 2/a 2/b 3/a
 
 .PHONY: build
 build: $(TARGETS)