From 92dd974e7abf6a1afa2def91724ab67f54bc5767 Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Tue, 14 Dec 2021 11:04:11 +0100
Subject: [PATCH] optimise day four

---
 14a.c    | 81 ++++++++++++++++++++++++++++++--------------------------
 14b.c    | 36 ++++++++++++-------------
 Makefile |  2 +-
 3 files changed, 61 insertions(+), 58 deletions(-)

diff --git a/14a.c b/14a.c
index 7b52084..10dea23 100644
--- a/14a.c
+++ b/14a.c
@@ -1,58 +1,63 @@
 #include <stdio.h>
 #include <stdbool.h>
 #include <limits.h>
+#include <string.h>
 
-#include <uthash.h>
+struct template { char x1; char x2; char ins; };
 
-struct pair { char x; char y; };
-struct template { struct pair key; char ins; UT_hash_handle hh; };
+#define lookup(i, x1, x2) (i)[((x1)-'A')+((x2)-'A')*26]
 
 int main()
 {
-	char *input = NULL, *buf = NULL, *oldinput = NULL;
-	size_t inputlen = 0, len;
-	struct template *template = NULL;
+	char *buf = NULL;
+	size_t len;
+	int ntemplate = 0;
+	struct template template[100];
+	unsigned long input1[26*26] = {0}, input2[26*26] = {0};
+	unsigned long *input = input1, *newinput = input2;
+
+	int first = getchar();
+	int c, last = first;
+	unsigned long freq[26] = {0};
+	while ( (c = getchar()) != '\n') {
+		lookup(input, last, c) = 1;
+		last = c;
+	}
 
-	if (getline(&input, &inputlen, stdin) == -1)
-		return 1;
 	while (getline(&buf, &len, stdin) != -1) {
-		if (strcmp(buf, "\n") == 0)
+		if (buf[0] == '\n')
 			continue;
-		struct template *t = calloc(1, sizeof(struct template));
-		t->key.x = buf[0];
-		t->key.y = buf[1];
-		t->ins = buf[6];
-		HASH_ADD(hh, template, key, sizeof(struct pair), t);
+		template[ntemplate++] = (struct template)
+			{.x1=buf[0], .x2=buf[1], .ins=buf[6]};
 	}
 
-	for (int i = 0; i<20; i++) {
-		free(oldinput);
-		oldinput = input;
-		input = malloc(inputlen *= 2);
-		inputlen = 0;
-		char *c;
-		for (c = &oldinput[0]; *c != '\0'; c++) {
-			input[inputlen++] = *c;
-			struct pair p = {.x=c[0], .y=c[1]};
-			struct template *t;
-			HASH_FIND(hh, template, &p, sizeof(struct pair), t);
-			if (t)
-				input[inputlen++] = t->ins;
+	for (int step = 0; step < 10; step++) {
+		for (int i = 0; i<ntemplate; i++) {
+			struct template t = template[i];
+			unsigned long freq = lookup(input, t.x1, t.x2);
+			lookup(newinput, t.x1, t.ins) += freq;
+			lookup(newinput, t.ins, t.x2) += freq;
 		}
-		input[inputlen++] = '\0';
+		unsigned long *t = newinput;
+		newinput = input;
+		input = t;
+		memset(&newinput[0], 0, sizeof(input1));
 	}
 
-	int freq[255] = {0};
-	int mcommon = 0, lcommon = INT_MAX;
-	for (char *c = &input[0]; *c != '\0'; *c++) {
-		freq[*c]++;
+	for (char x = 'A'; x<='Z'; x++) {
+		for (char y = 'A'; y<='Z'; y++) {
+			freq[x-'A'] += lookup(input, x, y);
+			freq[y-'A'] += lookup(input, x, y);
+		}
 	}
-	for (int i = 0; i<255; i++) {
-		if (freq[i] > mcommon)
-			mcommon = freq[i];
-		if (freq[i] > 1 && freq[i] < lcommon)
-			lcommon = freq[i];
+	freq[first-'A']++;
+	freq[last-'A']++;
+
+	unsigned long min = ULONG_MAX, max = 0;
+	for (int i = 0; i<26; i++) {
+		max = freq[i] > max ? freq[i] : max;
+		min = freq[i] > 1 && freq[i] < min ? freq[i] : min;
 	}
 
-	printf("%d\n", mcommon-lcommon);
+	printf("%lu\n", max/2-min/2);
 }
diff --git a/14b.c b/14b.c
index 83ebab0..2b505fa 100644
--- a/14b.c
+++ b/14b.c
@@ -3,42 +3,40 @@
 #include <limits.h>
 #include <string.h>
 
+struct template { char x1; char x2; char ins; };
+
 #define lookup(i, x1, x2) (i)[((x1)-'A')+((x2)-'A')*26]
 
 int main()
 {
 	char *buf = NULL;
 	size_t len;
-	char template[26*26] = {0};
-	unsigned long input1[26*26] = {0};
-	unsigned long input2[26*26] = {0};
-	unsigned long *input = input1;
-	unsigned long *newinput = input2;
+	int ntemplate = 0;
+	struct template template[100];
+	unsigned long input1[26*26] = {0}, input2[26*26] = {0};
+	unsigned long *input = input1, *newinput = input2;
 
 	int first = getchar();
-	int c, oldc = first;
+	int c, last = first;
 	unsigned long freq[26] = {0};
 	while ( (c = getchar()) != '\n') {
-		lookup(input, oldc, c) = 1;
-		oldc = c;
+		lookup(input, last, c) = 1;
+		last = c;
 	}
 
 	while (getline(&buf, &len, stdin) != -1) {
 		if (buf[0] == '\n')
 			continue;
-		lookup(template, buf[0], buf[1]) = buf[6];
+		template[ntemplate++] = (struct template)
+			{.x1=buf[0], .x2=buf[1], .ins=buf[6]};
 	}
 
 	for (int step = 0; step < 40; step++) {
-		for (char x = 'A'; x<='Z'; x++) {
-			for (char y = 'A'; y<='Z'; y++) {
-				char ins = lookup(template, x, y);
-				if (ins != '\0') {
-					unsigned long freq = lookup(input, x, y);
-					lookup(newinput, x, ins) += freq;
-					lookup(newinput, ins, y) += freq;
-				}
-			}
+		for (int i = 0; i<ntemplate; i++) {
+			struct template t = template[i];
+			unsigned long freq = lookup(input, t.x1, t.x2);
+			lookup(newinput, t.x1, t.ins) += freq;
+			lookup(newinput, t.ins, t.x2) += freq;
 		}
 		unsigned long *t = newinput;
 		newinput = input;
@@ -53,7 +51,7 @@ int main()
 		}
 	}
 	freq[first-'A']++;
-	freq[oldc-'A']++;
+	freq[last-'A']++;
 
 	unsigned long min = ULONG_MAX, max = 0;
 	for (int i = 0; i<26; i++) {
diff --git a/Makefile b/Makefile
index 50c1a9f..64234e9 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 CFLAGS:=-Wall -Wextra -O3
 LFLAGS:=-f
 
-BINARIES:=$(foreach num,$(shell seq -f '%02.0f' 1 11),$(num)a $(num)b)
+BINARIES:=$(foreach num,$(shell seq -f '%02.0f' 1 14),$(num)a $(num)b)
 
 all: $(BINARIES)
 
-- 
2.20.1