2017/advent12.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include <stdbool.h>
   7
   8 typedef struct node node;
   9 typedef struct neighbor neighbor;
  10 struct neighbor {
  11   int n;
  12   neighbor *next;
  13 };
  14 struct node {
  15   int group;
  16   neighbor *next;
  17 };
  18 node nodes[2000]; // cheat, by pre-inspecting input file
  19
  20 int main(void)
  21 {
  22   int count = 0;
  23   ssize_t nread;
  24   size_t len = 0;
  25   char *line = NULL;
  26   while ((nread = getline(&line, &len, stdin)) >= 0) {
  27     char *p = line;
  28     char *e;
  29     if (strtol (p, &e, 10) != count)
  30       return 1;
  31     if (strncmp (e, " <-> ", 5))
  32       return 2;
  33     p = e + 5;
  34     *e = ',';
  35     while (*e == ',') {
  36       int n = strtol (p, &e, 10);
  37       neighbor *next = calloc (1, sizeof *next);
  38       next->n = n;
  39       next->next = nodes[count].next;
  40       nodes[count].next = next;
  41       p = e + 1;
  42     }
  43     count++;
  44   }
  45   printf ("parsed connections for %d nodes\n", count);
  46   int groups = 0;
  47   int i;
  48   while (1) {
  49     for (i = 0; i < count; i++)
  50       if (!nodes[i].group)
  51         break;
  52     if (i == count)
  53       break;
  54     bool changed = true;
  55     nodes[i].group = ++groups;
  56     while (changed) {
  57       changed = false;
  58       for (i = 0; i < count; i++) {
  59         if (nodes[i].group != groups)
  60           continue;
  61         for (neighbor *next = nodes[i].next; next; next = next->next)
  62           if (!nodes[next->n].group)
  63             changed = (nodes[next->n].group = groups);
  64       }
  65     }
  66   }
  67   int size = 0;
  68   for (i = 0; i < count; i++)
  69     if (nodes[i].group == 1)
  70       size++;
  71   printf ("node 0 among group of %d nodes\n", size);
  72   printf ("total of %d groups\n", groups);
  73   return 0;
  74 }