2019/day6.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <stdarg.h>
   6 #include <stdbool.h>
   7 #include <limits.h>
   8
   9 static int do_debug = -1;
  10 void debug(const char *fmt, ...) {
  11   va_list ap;
  12   if (do_debug < 0)
  13     do_debug = !!getenv("DEBUG");
  14   if (do_debug > 0) {
  15     va_start(ap, fmt);
  16     vfprintf(stderr, fmt, ap);
  17     va_end(ap);
  18   }
  19 }
  20
  21 #define LIMIT 2000
  22
  23 struct orbit {
  24   char parent[4];
  25   char name[4];
  26   int idx;
  27   bool key;
  28 };
  29 struct orbit list[LIMIT] = { { "", "COM", -1 }, };
  30
  31 static void
  32 dump(int count) {
  33   debug("\n");
  34   if (!do_debug)
  35     return;
  36   for (int i = 0; i < count; i++)
  37     debug("%s)%s %d\n", list[i].parent, list[i].name, list[i].idx);
  38 }
  39
  40 int main(int argc, char **argv) {
  41   int i, j, count = 1, total = 0, trans = 0;
  42   int you = -1, san = -1, pivot = -1;
  43
  44   if (argc > 1)
  45     if (!(stdin = freopen(argv[1], "r", stdin))) {
  46       perror("failure");
  47       exit(2);
  48     }
  49
  50   /* Pass 1 - read relations: O(n) */
  51   while (scanf("%3[^)])%3s ", list[count].parent, list[count].name) == 2) {
  52     list[count++].idx = -1;
  53     if (count >= LIMIT) {
  54       printf("recompile with larger LIMIT\n");
  55       exit(2);
  56     }
  57   }
  58   printf("scanned %d direct relations\n", count);
  59   dump(count);
  60
  61   /* Pass 2 - locate parents: O(n^2) */
  62   for (i = 1; i < count; i++) {
  63     for (j = 0; j < count; j++) {
  64       if (!strcmp(list[i].parent, list[j].name)) {
  65         list[i].idx = j;
  66         break;
  67       }
  68     }
  69     if (list[i].idx == -1) {
  70       printf("incomplete map, missing parent for %s\n", list[i].name);
  71       exit(1);
  72     }
  73     if (!strcmp(list[i].name, "YOU"))
  74       you = i;
  75     else if (!strcmp(list[i].name, "SAN"))
  76       san = i;
  77   }
  78   dump(count);
  79
  80   /* Pass 3 - compute total: O(n+m) */
  81   for (i = 1; i < count; i++) {
  82     j = i;
  83     while (list[j].idx >= 0) {
  84       total++;
  85       if (i == you)
  86         list[j].key = true;
  87       j = list[j].idx;
  88       if (j == i) {
  89         printf("loop detected at %d %s\n", i, list[i].name);
  90         exit(1);
  91       }
  92     }
  93   }
  94   printf("%d total orbits\n", total);
  95
  96   /* Pass 4 - count transfer orbits: O(m) */
  97   if (you == -1 || san == -1)
  98     printf("transfer computation not possible\n");
  99   else {
 100     for (j = san; !list[j].key; j = list[j].idx)
 101       trans++;
 102     pivot = j;
 103     for (j = you; j != pivot; j = list[j].idx)
 104       trans++;
 105     printf("%d total transfers\n", trans - 2);
 106   }
 107   return 0;
 108 }