2018/day18.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
  10 bool debug(const char *fmt, ...) {
  11   va_list ap;
  12   if (getenv("DEBUG")) {
  13     va_start(ap, fmt);
  14     vfprintf(stderr, fmt, ap);
  15     va_end(ap);
  16     return true;
  17   }
  18   return false;
  19 }
  20
  21 #define LIMIT 50
  22 static char grida[2][LIMIT + 2][LIMIT + 2]; /* slow */
  23 static char gridb[2][LIMIT + 2][LIMIT + 2]; /* fast */
  24
  25 static void dump(int ticks, int max) {
  26   if (!debug("time %d\n", ticks))
  27     return;
  28   for (int i = 1; i <= max; i++)
  29     debug("%s\n", &grida[ticks % 2][i][1]);
  30   debug("\n");
  31 }
  32
  33 static char compute(char grid[LIMIT + 2][LIMIT + 2], int x, int y,
  34                     int *wooded, int *lumber) {
  35   int o = 0, w = 0, l = 0;
  36   switch (grid[y - 1][x - 1]) {
  37   case '.': o++; break;
  38   case '|': w++; break;
  39   case '#': l++; break;
  40   }
  41   switch (grid[y - 1][x]) {
  42   case '.': o++; break;
  43   case '|': w++; break;
  44   case '#': l++; break;
  45   }
  46   switch (grid[y - 1][x + 1]) {
  47   case '.': o++; break;
  48   case '|': w++; break;
  49   case '#': l++; break;
  50   }
  51   switch (grid[y][x - 1]) {
  52   case '.': o++; break;
  53   case '|': w++; break;
  54   case '#': l++; break;
  55   }
  56   switch (grid[y][x + 1]) {
  57   case '.': o++; break;
  58   case '|': w++; break;
  59   case '#': l++; break;
  60   }
  61   switch (grid[y + 1][x - 1]) {
  62   case '.': o++; break;
  63   case '|': w++; break;
  64   case '#': l++; break;
  65   }
  66   switch (grid[y + 1][x]) {
  67   case '.': o++; break;
  68   case '|': w++; break;
  69   case '#': l++; break;
  70   }
  71   switch (grid[y + 1][x + 1]) {
  72   case '.': o++; break;
  73   case '|': w++; break;
  74   case '#': l++; break;
  75   }
  76   switch (grid[y][x]) {
  77   case '.':
  78     if (w >= 3) {
  79       if (wooded)
  80         ++*wooded;
  81       return '|';
  82     }
  83     return '.';
  84   case '|':
  85     if (l >= 3) {
  86       if (lumber)
  87         ++*lumber;
  88       return '#';
  89     }
  90     if (wooded)
  91       ++*wooded;
  92     return '|';
  93   case '#':
  94     if (w && l) {
  95       if (lumber)
  96         ++*lumber;
  97       return '#';
  98     }
  99     return '.';
 100   default:
 101     assert(false);
 102   }
 103 }
 104
 105 int main(int argc, char **argv) {
 106   size_t len = 0, count = 0;
 107   char *line;
 108   char *p;
 109   int x, y;
 110   int ticks;
 111   int wooded, lumber;
 112
 113   /* Part 1 - read in initial map */
 114   if (argc > 1 && !(stdin = freopen(argv[1], "r", stdin))) {
 115     perror("failure");
 116     exit(2);
 117   }
 118
 119   while (getline(&line, &len, stdin) >= 0) {
 120     p = stpcpy(&grida[0][++count][1], line);
 121     *--p = '\0';
 122     if (p - &grida[0][count][1] >= LIMIT + 1) {
 123       fprintf(stderr, "LIMIT too small\n");
 124       exit(1);
 125     }
 126   }
 127   printf("Read %zu lines\n", count);
 128   if(p - &grida[0][count][1] != count) {
 129     fprintf(stderr, "non-square grid read in\n");
 130     exit(1);
 131   }
 132   memcpy(gridb, grida, sizeof grida);
 133   dump(0, count);
 134
 135   /* Part 2 - first 10 mintes */
 136   for (ticks = 0; ticks < 10; ticks++) {
 137     wooded = lumber = 0;
 138     for (y = 1; y <= count; y++)
 139       for (x = 1; x <= count; x++) {
 140         grida[(ticks + 1) % 2][y][x] = compute(grida[ticks % 2], x, y,
 141                                                &wooded, &lumber);
 142         gridb[1][y][x] = compute(gridb[0], x, y, NULL, NULL);
 143       }
 144     for (y = 1; y <= count; y++)
 145       for (x = 1; x <= count; x++)
 146         gridb[0][y][x] = compute(gridb[1], x, y, NULL, NULL);
 147     dump(ticks + 1, count);
 148     printf("After %d minutes, resource value %d*%d = %d\n", ticks + 1,
 149            wooded, lumber, wooded * lumber);
 150   }
 151
 152   /* Part 3 - iterate until cycle detected */
 153   while (memcmp(grida[ticks % 2], gridb[0], sizeof gridb[0])) {
 154     if (!(ticks % 10))
 155       printf("%5d\n", ticks);
 156     for (y = 1; y <= count; y++)
 157       for (x = 1; x <= count; x++) {
 158         grida[(ticks + 1) % 2][y][x] = compute(grida[ticks % 2], x, y,
 159                                                NULL, NULL);
 160         gridb[1][y][x] = compute(gridb[0], x, y, NULL, NULL);
 161       }
 162     for (y = 1; y <= count; y++)
 163       for (x = 1; x <= count; x++)
 164         gridb[0][y][x] = compute(gridb[1], x, y, NULL, NULL);
 165     ticks++;
 166   }
 167   printf("detected cycle at minute %d\n", ticks);
 168
 169   /* Part 4 - fast forward, then finish the task */
 170   memcpy(gridb[1], gridb[0], sizeof gridb[0]);
 171   for (ticks = 1000000000 - 1000000000 % ticks; ticks < 1000000000; ticks++) {
 172     wooded = lumber = 0;
 173     for (y = 1; y <= count; y++)
 174       for (x = 1; x <= count; x++)
 175         gridb[(ticks + 1) % 2][y][x] = compute(gridb[ticks % 2], x, y,
 176                                                &wooded, &lumber);
 177     printf("After %d minutes, resource value %d*%d = %d\n", ticks + 1,
 178            wooded, lumber, wooded * lumber);
 179   }
 180   return 0;
 181 }