18b.c

   1 #include <stdio.h>
   2 #include <stdbool.h>
   3 #include <stdlib.h>
   4 #include <ctype.h>
   5
   6 struct number {
   7         int number;
   8         int depth;
   9         struct number *prev;
  10         struct number *next;
  11 };
  12
  13 void print_number(struct number *head)
  14 {
  15         for (struct number *e = head; e != NULL; e = e->next)
  16                 printf("(%d,%d) ", e->number, e->depth);
  17         printf("\n");
  18 }
  19
  20 struct number *parse_comp(struct number *prev, int *depth)
  21 {
  22         int c = getchar();
  23         if (isdigit(c)) {
  24                 struct number *r = malloc(sizeof(struct number));
  25                 r->next = NULL;
  26                 r->prev = prev;
  27                 if (prev != NULL)
  28                         prev->next = r;
  29                 r->number = c-'0';
  30                 r->depth = *depth;
  31                 return r;
  32         } else if (c == ',') {
  33                 return parse_comp(prev, depth);
  34         } else if (c == '[') {
  35                 *depth = *depth+1;
  36                 return parse_comp(prev, depth);
  37         } else if (c == ']') {
  38                 *depth = *depth-1;
  39                 return parse_comp(prev, depth);
  40         } else if (c != '\n' && c != EOF) {
  41                 printf("unknown character: '%c': %d\n", c, c);
  42         }
  43         return NULL;
  44 }
  45
  46 struct number *parse_number()
  47 {
  48         int depth = 0;
  49         struct number *head = parse_comp(NULL, &depth);
  50         if (head == NULL)
  51                 return NULL;
  52         struct number *e = head;
  53         while ((e = parse_comp(e, &depth)) != NULL)
  54                 ;
  55         return head;
  56 }
  57
  58 void add_number(struct number *sum, struct number *oper)
  59 {
  60         //increase depth of sum
  61         struct number *e = sum;
  62         for (; e->next != NULL; e = e->next)
  63                 e->depth++;
  64         //append
  65         e->next = oper;
  66         oper->prev = e;
  67         //increase depth of oper
  68         for (; e != NULL; e = e->next)
  69                 e->depth++;
  70 }
  71
  72 bool explode_number(struct number *e)
  73 {
  74         if (e->depth <= 4)
  75                 return false;
  76         struct number *l = e;
  77         struct number *r = e->next;
  78         if (l->prev != NULL)
  79                 l->prev->number += l->number;
  80         if (r->next != NULL)
  81                 r->next->number += r->number;
  82         l->number = 0;
  83         l->depth--;
  84         l->next = r->next;
  85         if (l->next != NULL)
  86                 l->next->prev = l;
  87         if (l->prev != NULL)
  88                 e = l->prev;
  89         free(r);
  90         return true;
  91 }
  92
  93 bool split_number(struct number *e)
  94 {
  95         if (e->number < 10)
  96                 return false;
  97         struct number *i = malloc(sizeof(struct number));
  98         i->number = e->number/2 + (e->number%2);
  99         i->depth = e->depth+1;
 100         i->prev = e;
 101         i->next = e->next;
 102         e->next = i;
 103         e->number = e->number/2;
 104         e->depth = e->depth+1;
 105         return true;
 106 }
 107
 108 void reduce_number(struct number *n)
 109 {
 110         bool appliedaction;
 111         do {
 112                 appliedaction = false;
 113                 for (struct number *e = n; e != NULL && !appliedaction; e = e->next)
 114                         appliedaction |= explode_number(e);
 115                 for (struct number *e = n; e != NULL && !appliedaction; e = e->next)
 116                         appliedaction |= split_number(e);
 117         } while (appliedaction);
 118 }
 119
 120 int magnitude_number(struct number *n)
 121 {
 122         int maxdepth = 4;
 123         while (n->next != NULL) {
 124                 for (struct number *e = n; e != NULL; e = e->next) {
 125                         if (e->depth == maxdepth) {
 126                                 struct number *l = e;
 127                                 struct number *r = e->next;
 128                                 l->depth--;
 129                                 l->number = l->number*3 + r->number*2;
 130                                 l->next = r->next;
 131                                 if (r->next != NULL)
 132                                         r->next->prev = l;
 133                                 free(r);
 134                         }
 135                 }
 136                 maxdepth--;
 137         }
 138         int r = n->number;
 139         free(n);
 140         return r;
 141 }
 142
 143 struct number *copy_number(struct number *n)
 144 {
 145         struct number *copy = malloc(sizeof(struct number));
 146         copy->number = n->number;
 147         copy->depth = n->depth;
 148         copy->prev = NULL;
 149         copy->next = NULL;
 150         struct number *prev = copy;
 151         for (struct number *e = n->next; e != NULL; e = e->next) {
 152                 struct number *c = malloc(sizeof(struct number));
 153                 c->depth = e->depth;
 154                 c->number = e->number;
 155                 c->next = NULL;
 156                 c->prev = prev;
 157                 if (prev != NULL)
 158                         prev->next = c;
 159                 prev = c;
 160         }
 161         return copy;
 162 }
 163
 164 int main ()
 165 {
 166         int nnumber = 0;
 167         struct number *numbers[100] = {0};
 168         while ((numbers[nnumber] = parse_number()) != NULL)
 169                 nnumber++;
 170
 171         int maxmagnitude = 0;
 172         for (int i = 0; i<nnumber; i++) {
 173                 for (int j = 0; j<nnumber; j++) {
 174                         if (i == j)
 175                                 continue;
 176                         struct number *e = copy_number(numbers[i]);
 177                         add_number(e, copy_number(numbers[j]));
 178                         reduce_number(e);
 179                         int magnitude = magnitude_number(e);
 180                         if (magnitude > maxmagnitude)
 181                                 maxmagnitude = magnitude;
 182                 }
 183         }
 184         printf("%d\n", maxmagnitude);
 185 }