Solve day 14 part 2

1 files changed, 41 insertions, 29 deletions

diff --git a/2021/day14.c b/2021/day14.c
index 7525bd8..a13142e 100644
--- a/2021/day14.c
+++ b/2021/day14.c
@@ -3,46 +3,58 @@
 #include <stdlib.h>
 #include <string.h>
 static struct {
-	char a, b, c;
-} pairs[128];
+	int a, b, c;
+} rules[128];
 static size_t len;
-static char *step(const char *prev) {
-	char *next = malloc(1 + strlen(prev)*2);
-	char *ptr = next;
-	size_t i;
-	for (i = 0; prev[i+1]; ++i) {
-		*ptr++ = prev[i];
-		for (size_t j = 0; j < len; ++j) {
-			if (prev[i] != pairs[j].a || prev[i+1] != pairs[j].b) continue;
-			*ptr++ = pairs[j].c;
-			break;
-		}
+static size_t freq[26];
+static struct Pairs {
+	size_t _[26][26];
+} pairs;
+static void step(void) {
+	struct Pairs next = pairs;
+	for (size_t i = 0; i < len; ++i) {
+		size_t n = pairs._[rules[i].a][rules[i].b];
+		next._[rules[i].a][rules[i].c] += n;
+		next._[rules[i].c][rules[i].b] += n;
+		next._[rules[i].a][rules[i].b] -= n;
+		freq[rules[i].c] += n;
 	}
-	*ptr++ = prev[i];
-	*ptr = '\0';
-	return next;
+	pairs = next;
 }
 int main(void) {
 	size_t cap = 0;
-	char *polymer = NULL;
-	ssize_t n = getline(&polymer, &cap, stdin);
-	if (polymer[n-1] == '\n') polymer[n-1] = '\0';
-	while (EOF != scanf(" %c%c -> %c\n", &pairs[len].a, &pairs[len].b, &pairs[len].c)) {
+	char *buf = NULL;
+	ssize_t n = getline(&buf, &cap, stdin);
+	if (buf[n-1] == '\n') buf[n-1] = '\0';
+	freq[buf[0]-'A']++;
+	for (size_t i = 0; buf[i+1]; ++i) {
+		freq[buf[i+1]-'A']++;
+		pairs._[buf[i]-'A'][buf[i+1]-'A']++;
+	}
+	char a, b, c;
+	while (EOF != scanf(" %c%c -> %c\n", &a, &b, &c)) {
+		rules[len].a = a - 'A';
+		rules[len].b = b - 'A';
+		rules[len].c = c - 'A';
 		len++;
 	}
 	for (int i = 0; i < 10; ++i) {
-		char *next = step(polymer);
-		free(polymer);
-		polymer = next;
+		step();
+	}
+	size_t min = SIZE_MAX, max = 0;
+	for (int i = 0; i < 26; ++i) {
+		if (freq[i] && freq[i] < min) min = freq[i];
+		if (freq[i] > max) max = freq[i];
 	}
-	int freq[128] = {0};
-	for (size_t i = 0; polymer[i]; ++i) {
-		freq[polymer[i]]++;
+	printf("%zu\n", max - min);
+	for (int i = 0; i < 30; ++i) {
+		step();
 	}
-	int min = INT_MAX, max = INT_MIN;
-	for (int i = 'A'; i <= 'Z'; ++i) {
+	min = SIZE_MAX;
+	max = 0;
+	for (int i = 0; i < 26; ++i) {
 		if (freq[i] && freq[i] < min) min = freq[i];
 		if (freq[i] > max) max = freq[i];
 	}
-	printf("%d\n", max - min);
+	printf("%zu\n", max - min);
 }