2017/advent7.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6
   7 // cheat - pre-examined input to learn max name length (7+NUL), children (7)
   8 #define MAXNAME 8
   9 #define MAXCHILD 7
  10
  11 typedef struct node node;
  12 struct node {
  13   char name[MAXNAME];
  14   int weight;
  15   int nchildren;
  16   char childname[MAXCHILD][MAXNAME];
  17   node *next; // global list form
  18   node *children[MAXCHILD]; // tree form
  19   int total;
  20 };
  21 node *list;
  22
  23 static int compute(node *n)
  24 {
  25   for (int i = 0; i < n->nchildren; i++)
  26     for (node *iter = list; iter; iter = iter->next)
  27       if (!strcmp(n->childname[i], iter->name)) {
  28         n->children[i] = iter;
  29         n->total += compute(iter);
  30         break;
  31       }
  32   if (n->nchildren && n->total != n->children[0]->total * n->nchildren) {
  33     printf("node %s is bad, with %d children\n", n->name, n->nchildren);
  34     for (int i = 0; i < n->nchildren; i++) {
  35       int w1 = n->children[(i+1) % n->nchildren]->total;
  36       int w2 = n->children[(i+2) % n->nchildren]->total;
  37       if (getenv("DEBUG"))
  38         printf(" child %d: %s %d %d vs. %d %d\n", i, n->children[i]->name,
  39                n->children[i]->weight, n->children[i]->total, w1, w2);
  40       if (n->children[i]->total != w1 && n->children[i]->total != w2) {
  41         printf("fix by adjusting %s weight to %d\n", n->children[i]->name,
  42                n->children[i]->weight - n->children[i]->total + w1);
  43         break;
  44       }
  45     }
  46   }
  47   n->total += n->weight;
  48   return n->total;
  49 }
  50
  51 int main(void)
  52 {
  53   int count = 0;
  54   // ugly, but works because our data is sane
  55   while (1) {
  56     node *item = calloc(sizeof *item, 1);
  57     item->nchildren = scanf(" %8[a-z] (%d) -> %8[a-z], %8[a-z], %8[a-z], "
  58                             "%8[a-z], %8[a-z], %8[a-z], %8[a-z]",
  59                             item->name, &item->weight, item->childname[0],
  60                             item->childname[1], item->childname[2],
  61                             item->childname[3], item->childname[4],
  62                             item->childname[5], item->childname[6]) - 2;
  63     if (item->nchildren < 0) {
  64       free (item);
  65       break;
  66     }
  67     if (getenv("DEBUG"))
  68       printf("%s (%d) -> %d: %s %s %s %s %s %s %s\n", item->name, item->weight,
  69              item->nchildren, item->childname[0], item->childname[1],
  70              item->childname[2], item->childname[3], item->childname[4],
  71              item->childname[5], item->childname[6]);
  72     item->next = list;
  73     list = item;
  74     count++;
  75   }
  76   printf("parsed %d lines\n", count);
  77   node *root = list;
  78   int change = 1;
  79   while (change) {
  80     change = 0;
  81     for (node *iter = list; iter; iter = iter->next)
  82       for (int i = 0; i < iter->nchildren; i++)
  83         if (!strcmp(root->name, iter->childname[i])) {
  84           change++;
  85           if (getenv("DEBUG"))
  86             printf("%s is parent of %s\n", iter->name, root->name);
  87           root = iter;
  88         }
  89   }
  90   printf("root is %s\n", root->name);
  91   printf("root weight is %d\n", compute(root));
  92   return 0;
  93 }