day 18

[advent21.git] / 18b.c

diff --git a/18b.c b/18b.c
new file mode 100644 (file)
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);
+}