From 3f719e53a93064f75711d41ac38d0ae163354cf7 Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Mon, 20 Dec 2021 11:38:14 +0100
Subject: [PATCH] day 18

---
 18a.c    | 165 +++++++++++++++++++++++++++++++++++++++----------
 18b.c    | 185 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 18e.txt  |   2 +
 18e2.txt |   2 +
 18e3.txt |   1 +
 18e4.txt |   1 +
 18e5.txt |   4 ++
 18e6.txt |   1 +
 18e7.txt |   6 ++
 18e8.txt |  10 +++
 Makefile |   4 +-
 11 files changed, 345 insertions(+), 36 deletions(-)
 create mode 100644 18b.c
 create mode 100644 18e.txt
 create mode 100644 18e2.txt
 create mode 100644 18e3.txt
 create mode 100644 18e4.txt
 create mode 100644 18e5.txt
 create mode 100644 18e6.txt
 create mode 100644 18e7.txt
 create mode 100644 18e8.txt

diff --git a/18a.c b/18a.c
index 719c3f0..acec8d3 100644
--- a/18a.c
+++ b/18a.c
@@ -4,52 +4,149 @@
 #include <ctype.h>
 
 struct number {
-	int depth;
 	int number;
+	int depth;
+	struct number *prev;
+	struct number *next;
 };
 
-int parse_number(struct number numbers[])
+void print_number(struct number *head)
+{
+	for (struct number *e = head; e != NULL; e = e->next)
+		printf("(%d,%d) ", e->number, e->depth);
+	printf("\n");
+}
+
+struct number *parse_comp(struct number *prev, int *depth)
 {
-	int ns = 0;
-	int depth = 0;
 	int c = getchar();
-	while ((c = getchar()) != '\n') {
-		switch(c) {
-		case '[':
-			depth++;
-			break;
-		case ']':
-			depth--;
-			break;
-		case ',':
-			break;
-		default:
-			if (isdigit(c))
-				numbers[ns++] = (struct number){.depth=depth, .number=c-'0'};
-			else
-				printf("halp\n");
-			break;
-		}
+	if (isdigit(c)) {
+		struct number *r = malloc(sizeof(struct number));
+		r->next = NULL;
+		r->prev = prev;
+		if (prev != NULL)
+			prev->next = r;
+		r->number = c-'0';
+		r->depth = *depth;
+		return r;
+	} else if (c == ',') {
+		return parse_comp(prev, depth);
+	} else if (c == '[') {
+		*depth = *depth+1;
+		return parse_comp(prev, depth);
+	} else if (c == ']') {
+		*depth = *depth-1;
+		return parse_comp(prev, depth);
+	} else if (c != '\n' && c != EOF) {
+		printf("unknown character: '%c': %d\n", c, c);
 	}
-	return ns;
+	return NULL;
 }
 
-void print_number(struct number n[], int ns)
+struct number *parse_number()
 {
-	int olddepth = 0;
-	for (int i = 0; i<ns; i++) {
-		if (n[i].depth > olddepth)
-			printf("[");
-		else if (n[i].depth < olddepth)
-			printf("]");
-		printf("%d ", n[i].number);
-		olddepth = n[i].depth;
+	int depth = 0;
+	struct number *head = parse_comp(NULL, &depth);
+	if (head == NULL)
+		return NULL;
+	struct number *e = head;
+	while ((e = parse_comp(e, &depth)) != NULL)
+		;
+	return head;
+}
+
+void add_number(struct number *sum, struct number *oper)
+{
+	//increase depth of sum
+	struct number *e = sum;
+	for (; e->next != NULL; e = e->next)
+		e->depth++;
+	//append
+	e->next = oper;
+	oper->prev = e;
+	//increase depth of oper
+	for (; e != NULL; e = e->next)
+		e->depth++;
+}
+
+bool explode_number(struct number *e)
+{
+	if (e->depth <= 4)
+		return false;
+	struct number *l = e;
+	struct number *r = e->next;
+	if (l->prev != NULL)
+		l->prev->number += l->number;
+	if (r->next != NULL)
+		r->next->number += r->number;
+	l->number = 0;
+	l->depth--;
+	l->next = r->next;
+	if (l->next != NULL)
+		l->next->prev = l;
+	if (l->prev != NULL)
+		e = l->prev;
+	free(r);
+	return true;
+}
+
+bool split_number(struct number *e)
+{
+	if (e->number < 10)
+		return false;
+	struct number *i = malloc(sizeof(struct number));
+	i->number = e->number/2 + (e->number%2);
+	i->depth = e->depth+1;
+	i->prev = e;
+	i->next = e->next;
+	e->next = i;
+	e->number = e->number/2;
+	e->depth = e->depth+1;
+	return true;
+}
+
+void reduce_number(struct number *n)
+{
+	bool appliedaction;
+	do {
+		appliedaction = false;
+		for (struct number *e = n; e != NULL && !appliedaction; e = e->next)
+			appliedaction |= explode_number(e);
+		for (struct number *e = n; e != NULL && !appliedaction; e = e->next)
+			appliedaction |= split_number(e);
+	} while (appliedaction);
+}
+
+int magnitude_number(struct number *n)
+{
+	int maxdepth = 4;
+	while (n->next != NULL) {
+		for (struct number *e = n; e != NULL; e = e->next) {
+			if (e->depth == maxdepth) {
+				struct number *l = e;
+				struct number *r = e->next;
+				l->depth--;
+				l->number = l->number*3 + r->number*2;
+				l->next = r->next;
+				if (r->next != NULL)
+					r->next->prev = l;
+				free(r);
+			}
+		}
+		maxdepth--;
 	}
+	int r = n->number;
+	free(n);
+	return r;
 }
 
 int main ()
 {
-	struct number n[100];
-	int ns = parse_number(n);
-	print_number(n, ns);
+	struct number *sum = parse_number();
+	struct number *oper;
+	while ((oper = parse_number()) != NULL) {
+		add_number(sum, oper);
+		reduce_number(sum);
+	}
+	printf("%d\n", magnitude_number(sum));
 }
diff --git a/18b.c b/18b.c
new file mode 100644
index 0000000..490b038
--- /dev/null
+++ b/18b.c
@@ -0,0 +1,185 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <ctype.h>
+
+struct number {
+	int number;
+	int depth;
+	struct number *prev;
+	struct number *next;
+};
+
+void print_number(struct number *head)
+{
+	for (struct number *e = head; e != NULL; e = e->next)
+		printf("(%d,%d) ", e->number, e->depth);
+	printf("\n");
+}
+
+struct number *parse_comp(struct number *prev, int *depth)
+{
+	int c = getchar();
+	if (isdigit(c)) {
+		struct number *r = malloc(sizeof(struct number));
+		r->next = NULL;
+		r->prev = prev;
+		if (prev != NULL)
+			prev->next = r;
+		r->number = c-'0';
+		r->depth = *depth;
+		return r;
+	} else if (c == ',') {
+		return parse_comp(prev, depth);
+	} else if (c == '[') {
+		*depth = *depth+1;
+		return parse_comp(prev, depth);
+	} else if (c == ']') {
+		*depth = *depth-1;
+		return parse_comp(prev, depth);
+	} else if (c != '\n' && c != EOF) {
+		printf("unknown character: '%c': %d\n", c, c);
+	}
+	return NULL;
+}
+
+struct number *parse_number()
+{
+	int depth = 0;
+	struct number *head = parse_comp(NULL, &depth);
+	if (head == NULL)
+		return NULL;
+	struct number *e = head;
+	while ((e = parse_comp(e, &depth)) != NULL)
+		;
+	return head;
+}
+
+void add_number(struct number *sum, struct number *oper)
+{
+	//increase depth of sum
+	struct number *e = sum;
+	for (; e->next != NULL; e = e->next)
+		e->depth++;
+	//append
+	e->next = oper;
+	oper->prev = e;
+	//increase depth of oper
+	for (; e != NULL; e = e->next)
+		e->depth++;
+}
+
+bool explode_number(struct number *e)
+{
+	if (e->depth <= 4)
+		return false;
+	struct number *l = e;
+	struct number *r = e->next;
+	if (l->prev != NULL)
+		l->prev->number += l->number;
+	if (r->next != NULL)
+		r->next->number += r->number;
+	l->number = 0;
+	l->depth--;
+	l->next = r->next;
+	if (l->next != NULL)
+		l->next->prev = l;
+	if (l->prev != NULL)
+		e = l->prev;
+	free(r);
+	return true;
+}
+
+bool split_number(struct number *e)
+{
+	if (e->number < 10)
+		return false;
+	struct number *i = malloc(sizeof(struct number));
+	i->number = e->number/2 + (e->number%2);
+	i->depth = e->depth+1;
+	i->prev = e;
+	i->next = e->next;
+	e->next = i;
+	e->number = e->number/2;
+	e->depth = e->depth+1;
+	return true;
+}
+
+void reduce_number(struct number *n)
+{
+	bool appliedaction;
+	do {
+		appliedaction = false;
+		for (struct number *e = n; e != NULL && !appliedaction; e = e->next)
+			appliedaction |= explode_number(e);
+		for (struct number *e = n; e != NULL && !appliedaction; e = e->next)
+			appliedaction |= split_number(e);
+	} while (appliedaction);
+}
+
+int magnitude_number(struct number *n)
+{
+	int maxdepth = 4;
+	while (n->next != NULL) {
+		for (struct number *e = n; e != NULL; e = e->next) {
+			if (e->depth == maxdepth) {
+				struct number *l = e;
+				struct number *r = e->next;
+				l->depth--;
+				l->number = l->number*3 + r->number*2;
+				l->next = r->next;
+				if (r->next != NULL)
+					r->next->prev = l;
+				free(r);
+			}
+		}
+		maxdepth--;
+	}
+	int r = n->number;
+	free(n);
+	return r;
+}
+
+struct number *copy_number(struct number *n)
+{
+	struct number *copy = malloc(sizeof(struct number));
+	copy->number = n->number;
+	copy->depth = n->depth;
+	copy->prev = NULL;
+	copy->next = NULL;
+	struct number *prev = copy;
+	for (struct number *e = n->next; e != NULL; e = e->next) {
+		struct number *c = malloc(sizeof(struct number));
+		c->depth = e->depth;
+		c->number = e->number;
+		c->next = NULL;
+		c->prev = prev;
+		if (prev != NULL)
+			prev->next = c;
+		prev = c;
+	}
+	return copy;
+}
+
+int main ()
+{
+	int nnumber = 0;
+	struct number *numbers[100] = {0};
+	while ((numbers[nnumber] = parse_number()) != NULL)
+		nnumber++;
+
+	int maxmagnitude = 0;
+	for (int i = 0; i<nnumber; i++) {
+		for (int j = 0; j<nnumber; j++) {
+			if (i == j)
+				continue;
+			struct number *e = copy_number(numbers[i]);
+			add_number(e, copy_number(numbers[j]));
+			reduce_number(e);
+			int magnitude = magnitude_number(e);
+			if (magnitude > maxmagnitude)
+				maxmagnitude = magnitude;
+		}
+	}
+	printf("%d\n", maxmagnitude);
+}
diff --git a/18e.txt b/18e.txt
new file mode 100644
index 0000000..61b0df6
--- /dev/null
+++ b/18e.txt
@@ -0,0 +1,2 @@
+[[[[4,3],4],4],[7,[[8,4],9]]]
+[1,1]
diff --git a/18e2.txt b/18e2.txt
new file mode 100644
index 0000000..f430960
--- /dev/null
+++ b/18e2.txt
@@ -0,0 +1,2 @@
+[[[[[9,8],1],2],3],4]
+
diff --git a/18e3.txt b/18e3.txt
new file mode 100644
index 0000000..41c8d15
--- /dev/null
+++ b/18e3.txt
@@ -0,0 +1 @@
+[7,[6,[5,[4,[3,2]]]]]
diff --git a/18e4.txt b/18e4.txt
new file mode 100644
index 0000000..9f59172
--- /dev/null
+++ b/18e4.txt
@@ -0,0 +1 @@
+[[6,[5,[4,[3,2]]]],1]
diff --git a/18e5.txt b/18e5.txt
new file mode 100644
index 0000000..f212f83
--- /dev/null
+++ b/18e5.txt
@@ -0,0 +1,4 @@
+[1,1]
+[2,2]
+[3,3]
+[4,4]
diff --git a/18e6.txt b/18e6.txt
new file mode 100644
index 0000000..d1c17ef
--- /dev/null
+++ b/18e6.txt
@@ -0,0 +1 @@
+[[[[3,0],[5,3]],[4,4]],[5,5]]
diff --git a/18e7.txt b/18e7.txt
new file mode 100644
index 0000000..85acce5
--- /dev/null
+++ b/18e7.txt
@@ -0,0 +1,6 @@
+[1,1]
+[2,2]
+[3,3]
+[4,4]
+[5,5]
+[6,6]
diff --git a/18e8.txt b/18e8.txt
new file mode 100644
index 0000000..70e9071
--- /dev/null
+++ b/18e8.txt
@@ -0,0 +1,10 @@
+[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
+[7,[[[3,7],[4,3]],[[6,3],[8,8]]]]
+[[2,[[0,8],[3,4]]],[[[6,7],1],[7,[1,6]]]]
+[[[[2,4],7],[6,[0,5]]],[[[6,8],[2,8]],[[2,1],[4,5]]]]
+[7,[5,[[3,8],[1,4]]]]
+[[2,[2,2]],[8,[8,1]]]
+[2,9]
+[1,[[[9,3],9],[[9,0],[0,7]]]]
+[[[5,[7,4]],7],1]
+[[[[4,2],2],6],[8,7]]
diff --git a/Makefile b/Makefile
index a350a35..b6f6074 100644
--- a/Makefile
+++ b/Makefile
@@ -1,9 +1,9 @@
 CFLAGS:=-Wall -Wextra -O3
 LFLAGS:=-f
 
-BINARIES:=$(filter-out 18a 18b 19a 19b,$(foreach num,$(shell seq -f '%02.0f' 1 20),$(num)a $(num)b))
+BINARIES:=$(filter-out 19a 19b,$(foreach num,$(shell seq -f '%02.0f' 1 20),$(num)a $(num)b))
 
-all: 
+all: $(BINARIES)
 
 clean:
 	$(RM) *.o a.out $(BINARIES)
-- 
2.20.1