2018/day17.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 void 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   }
  17 }
  18
  19 #define MAXX 700
  20 #define MAXY 2000
  21 #define MIN(a,b) ((a)<(b)?(a):(b))
  22 #define MAX(a,b) ((a)>(b)?(a):(b))
  23
  24 static char grid[MAXY][MAXX];
  25 static int calls;
  26 static int tiles;
  27
  28 static void dump(int minx, int miny, int maxx, int maxy) {
  29   int i;
  30   if (!getenv("DEBUG"))
  31     return;
  32   debug("%4d: % *c\n", 0, 500 - minx + 1, '+');
  33   for (i = miny; i <= maxy; i++)
  34     debug("%4d: %.*s\n", i, maxx - minx + 1, &grid[i][minx]);
  35 }
  36
  37 static void fill(int x, int y, int minx, int miny, int maxx, int maxy) {
  38   int l, r, i;
  39   calls++;
  40   debug("fill(%d,%d) at %c above %c\n", x, y, grid[y][x], grid[y + 1][x]);
  41   if (y > maxy)
  42     return;
  43   if (grid[y + 1][x] == '|') {
  44     debug("point %d,%d already being filled elsewhere\n", x, y + 1);
  45     dump(MAX(minx, x - 5), MAX(0, y - 5), MIN(maxx, x + 5), y + 2);
  46     return;
  47   }
  48   if (grid[y + 1][x] == '.') {
  49     if (y + 1 >= miny && y + 1 <= maxy)
  50       tiles++;
  51     grid[y + 1][x] = '|';
  52     fill(x, y + 1, minx, miny, maxx, maxy);
  53     return;
  54   }
  55   assert(y >= miny && y <= maxy);
  56   for (l = x; l >= minx; l--) {
  57     if (grid[y][l - 1] == '#' ||
  58         grid[y + 1][l - 1] == '.' || grid[y + 1][l - 1] == '|')
  59       break;
  60   }
  61   for (r = x; r <= maxx; r++) {
  62     if (grid[y][r + 1] == '#' ||
  63         grid[y + 1][r + 1] == '.' || grid[y + 1][r + 1] == '|')
  64       break;
  65   }
  66   debug("found bounds %d to %d\n", l, r);
  67   if (grid[y][l - 1] == '#' && grid[y][r + 1] == '#') {
  68     for (i = l; i <= r; i++) {
  69       if (grid[y][i] == '.')
  70         tiles++;
  71       grid[y][i] = '~';
  72     }
  73     dump(MAX(minx, l - 2), MAX(0, y - 5), MIN(maxx, r + 2), y + 2);
  74     fill(x, y - 1, minx, miny, maxx, maxy);
  75     return;
  76   }
  77   for (i = l; i <= r; i++) {
  78     if (grid[y][i] == '.')
  79       tiles++;
  80     grid[y][i] = '|';
  81   }
  82   if (grid[y][l - 1] == '.') {
  83     tiles++;
  84     grid[y][l - 1] = '|';
  85     debug("spilling left from %d,%d\n", x, y);
  86     dump(MAX(minx, l - 2), MAX(0, y - 5), MIN(maxx, r + 2), y + 2);
  87     fill(l - 1, y, minx, miny, maxx, maxy);
  88   }
  89   if (grid[y][r + 1] == '.') {
  90     tiles++;
  91     grid[y][r + 1] = '|';
  92     debug("spilling right from %d,%d\n", x, y);
  93     dump(MAX(minx, l - 2), MAX(0, y - 5), MIN(maxx, r + 2), y + 2);
  94     fill(r + 1, y, minx, miny, maxx, maxy);
  95   }
  96 }
  97
  98 int main(int argc, char **argv) {
  99   size_t len = 0, count = 0;
 100   char *line;
 101   char a, b;
 102   int minx = 500, maxx = 500, miny = 10000, maxy = 0;
 103   int q, r, s;
 104   int x1, x2, y1, y2;
 105
 106   /* Part 0 - read in map */
 107   if (argc > 1 && !(stdin = freopen(argv[1], "r", stdin))) {
 108     perror("failure");
 109     exit(2);
 110   }
 111
 112   memset(grid, '.', sizeof grid);
 113   while (getline(&line, &len, stdin) >= 0) {
 114     count++;
 115     if (sscanf(line, "%c=%d, %c=%d..%d\n", &a, &q, &b, &r, &s) != 5
 116         || a == b || r >= s) {
 117       fprintf(stderr, "bad input: %s\n", line);
 118       exit(1);
 119     }
 120     if (a == 'x') {
 121       x1 = x2 = q;
 122       y1 = r;
 123       y2 = s;
 124       for (q = y1; q <= y2; q++)
 125         grid[q][x1] = '#';
 126     } else {
 127       assert(b == 'x');
 128       x1 = r;
 129       x2 = s;
 130       y1 = y2 = q;
 131       for (q = x1; q <= x2; q++)
 132         grid[y1][q] = '#';
 133     }
 134     debug("clay at %d,%d to %d,%d\n", x1, y1, x2, y2);
 135     if (x1 < minx)
 136       minx = x1;
 137     if (x2 > maxx)
 138       maxx = x2;
 139     if (y1 < miny)
 140       miny = y1;
 141     if (y2 > maxy)
 142       maxy = y2;
 143     if (minx < 1 || maxx > MAXX - 1 || miny < 1 || maxy > MAXY - 1) {
 144       fprintf(stderr, "recompile with larger limit\n");
 145       exit(1);
 146     }
 147   }
 148   minx--;
 149   maxx++;
 150   printf("read %zu lines, bounds: %d,%d to %d,%d\n",
 151          count, minx, miny, maxx, maxy);
 152   dump(minx, miny, maxx, maxy);
 153
 154   /* Part 2 - fill grid */
 155   if (argc > 2)
 156     maxy = atoi(argv[2]);
 157   grid[0][500] = '|';
 158   fill(500, 0, minx, miny, maxx, maxy);
 159   dump(minx, miny, maxx, maxy);
 160   printf("completed %d calls, change %d tiles\n", calls, tiles);
 161   q = count = 0;
 162   for (s = miny; s <= maxy; s++)
 163     for (r = minx; r <= maxx; r++) {
 164       if (grid[s][r] == '~' || grid[s][r] == '|')
 165         count++;
 166       if (grid[s][r] == '~')
 167         q++;
 168     }
 169   printf("found %zu points touched by water, %d retained\n", count, q);
 170   return 0;
 171 }