2018/day25.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 <inttypes.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10
  11 bool __attribute__((format(printf, 1, 2)))
  12 debug(const char *fmt, ...) {
  13   va_list ap;
  14   if (getenv("DEBUG")) {
  15     va_start(ap, fmt);
  16     vfprintf(stderr, fmt, ap);
  17     va_end(ap);
  18     return true;
  19   }
  20   return false;
  21 }
  22
  23 #define LIMIT 1300
  24
  25 static struct data {
  26   int x;
  27   int y;
  28   int z;
  29   int t;
  30   int c;
  31 } array[LIMIT];
  32 static bool used[LIMIT + 1];
  33
  34 int main(int argc, char **argv) {
  35   size_t len = 0, count = 0;
  36   char *line;
  37   int i, j, k, t;
  38
  39   /* Part 1 - read data */
  40   if (argc > 1)
  41     if (!(stdin = freopen(argv[1], "r", stdin))) {
  42       perror("failure");
  43       exit(2);
  44     }
  45
  46   while (getline(&line, &len, stdin) >= 0) {
  47     if (count >= LIMIT) {
  48       fprintf(stderr, "recompile with larger LIMIT!\n");
  49       exit(1);
  50     }
  51     if (sscanf(line, "%d,%d,%d,%d\n", &array[count].x, &array[count].y,
  52                &array[count].z, &array[count].t) != 4) {
  53       fprintf(stderr, "bad input\n");
  54       exit(1);
  55     }
  56     ++count;
  57   }
  58   printf("Read %zu lines\n", count);
  59
  60   array[0].c = 1;
  61   used[1] = true;
  62   for (i = 1; i < count; i++) {
  63     for (j = 0; j < i; j++) {
  64       if (abs(array[i].x - array[j].x) + abs(array[i].y - array[j].y)
  65           + abs(array[i].z - array[j].z) + abs(array[i].t - array[j].t) <= 3) {
  66         debug("point at index %d near index %d\n", j, i);
  67         if (array[i].c) {
  68           if (array[i].c != array[j].c) {
  69             /* merge */
  70             t = array[j].c;
  71             for (k = 0; k < i; k++)
  72               if (array[k].c == t)
  73                 array[k].c = array[i].c;
  74             used[t] = false;
  75           }
  76         } else {
  77           assert(array[j].c);
  78           array[i].c = array[j].c;
  79         }
  80       }
  81     }
  82     if (!array[i].c) {
  83       for (j = 1; j <= i + 1; j++)
  84         if (!used[j]) {
  85           used[j] = true;
  86           array[i].c = j;
  87           break;
  88         }
  89     }
  90   }
  91   j = 0;
  92   for (i = 1; i < count + 1; i++)
  93     if (used[i])
  94       j++;
  95   printf("Found %d constellations\n", j);
  96   return 0;
  97 }