From bb23d8fc0c6a1ad853be28143553de689d784877 Mon Sep 17 00:00:00 2001
From: June McEnroe <june@causal.agency>
Date: Mon, 14 Dec 2020 18:38:27 -0500
Subject: Rewrite day 14 to log all writes then sort them

Down from 1.56s to 0.04s.
---
 2020/day14.c | 52 +++++++++++++++++++++-------------------------------
 1 file changed, 21 insertions(+), 31 deletions(-)

diff --git a/2020/day14.c b/2020/day14.c
index 638ca35..07bab22 100644
--- a/2020/day14.c
+++ b/2020/day14.c
@@ -1,36 +1,22 @@
 #include <stdio.h>
 #include <stdlib.h>
 typedef unsigned long ul;
-static struct Write {
+struct Write {
 	ul addr;
 	ul val;
-} writes[1024];
-static int len;
-static void write(ul addr, ul val) {
-	for (int i = 0; i < len; ++i) {
-		if (writes[i].addr == addr) {
-			writes[i].val = val;
-			return;
-		}
-	}
-	writes[len].addr = addr;
-	writes[len++].val = val;
-}
-static struct Write writes2[512 * (1 << 9)];
-static ul len2;
-static void write2(ul addr, ul val) {
-	for (int i = 0; i < len2; ++i) {
-		if (writes2[i].addr == addr) {
-			writes2[i].val = val;
-			return;
-		}
-	}
-	writes2[len2].addr = addr;
-	writes2[len2++].val = val;
+};
+static int compar(const void *_a, const void *_b) {
+	const struct Write *a = _a;
+	const struct Write *b = _b;
+	if (a->addr < b->addr) return -1;
+	if (a->addr > b->addr) return +1;
+	return 0;
 }
 int main(void) {
-	ul mask = 0;
-	ul bits = 0;
+	struct Write writes[512];
+	struct Write writes2[512 * (1 << 9)];
+	int len = 0, len2 = 0;
+	ul mask = 0, bits = 0;
 	for (;;) {
 		char str[37];
 		int n = scanf("mask = %s\n", str);
@@ -49,11 +35,11 @@ int main(void) {
 			ul addr, val;
 			n = scanf("em[%lu] = %lu\n", &addr, &val);
 			if (n < 2) break;
-			write(addr, (val & mask) | bits);
+			writes[len++] = (struct Write) { addr, (val & mask) | bits };
 			addr |= bits;
 			addr &= ~mask;
-			ul writes = 1UL << __builtin_popcountl(mask);
-			for (ul i = 0; i < writes; ++i) {
+			ul count = 1UL << __builtin_popcountl(mask);
+			for (ul i = 0; i < count; ++i) {
 				ul a = addr;
 				ul w = i;
 				for (int j = 0; j < 36; ++j) {
@@ -62,17 +48,21 @@ int main(void) {
 						w >>= 1;
 					}
 				}
-				write2(a, val);
+				writes2[len2++] = (struct Write) { a, val };
 			}
 		}
 	}
+	mergesort(writes, len, sizeof(writes[0]), compar);
 	ul sum = 0;
 	for (int i = 0; i < len; ++i) {
+		if (i + 1 < len && writes[i+1].addr == writes[i].addr) continue;
 		sum += writes[i].val;
 	}
 	printf("%lu\n", sum);
+	mergesort(writes2, len2, sizeof(writes2[0]), compar);
 	sum = 0;
-	for (ul i = 0; i < len2; ++i) {
+	for (int i = 0; i < len2; ++i) {
+		if (i + 1 < len2 && writes2[i+1].addr == writes2[i].addr) continue;
 		sum += writes2[i].val;
 	}
 	printf("%lu\n", sum);
-- 
cgit 1.4.1