2018/day20b.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 1000
  22 #define OFFSET (LIMIT / 2)
  23 static short grid[LIMIT][LIMIT];
  24 typedef struct state {
  25   int depth;
  26   int x;
  27   int y;
  28   const char *p;
  29 } state;
  30 static const char *orig;
  31
  32 static void set(int x, int y, int d) {
  33   if (grid[y][x])
  34     debug("skipping %d,%d to %d, already visited at %d\n",
  35           x, y, d, grid[y][x]);
  36   else
  37     grid[y][x] = d;
  38 }
  39
  40 static void visit(state *s) {
  41   short d = grid[s->y][s->x];
  42   state branches[4];
  43   int b = -1;
  44   int i;
  45
  46   debug("depth %d, visiting %c (%tu) at %d,%d distance %d\n",
  47         s->depth, *s->p, s->p - orig, s->x, s->y, d);
  48   if (s->x < 1 || s->x >= LIMIT - 1 || s->y < 1 || s->y >= LIMIT - 1) {
  49     fprintf(stderr, "recompile with larger limit\n");
  50     exit(1);
  51   }
  52   assert(d);
  53   switch (*s->p) {
  54   default:
  55     assert(false);
  56   case '^':
  57     assert(!s->depth);
  58     break;
  59   case '$':
  60     assert(!s->depth);
  61     return;
  62   case 'N':
  63     set(s->x, --s->y, d + 1);
  64     break;
  65   case 'S':
  66     set(s->x, ++s->y, d + 1);
  67     break;
  68   case 'E':
  69     set(++s->x, s->y, d + 1);
  70     break;
  71   case 'W':
  72     set(--s->x, s->y, d + 1);
  73     break;
  74   case '(':
  75     do {
  76       if (++b == sizeof branches / sizeof *branches) {
  77         fprintf(stderr, "recompile for more alternates\n");
  78         exit(1);
  79       }
  80       branches[b] = *s;
  81       branches[b].depth++;
  82       branches[b].p = b ? branches[b - 1].p + 1 : s->p + 1;
  83       visit(&branches[b]);
  84     } while (*branches[b].p == '|');
  85     for (i = 0; i < b; i++) {
  86       if (branches[i].x != branches[b].x || branches[i].y != branches[b].y) {
  87         branches[i].depth--;
  88         branches[i].p = branches[b].p + 1;
  89         visit(&branches[i]);
  90       } else
  91         debug("skipping round-trip alternative\n");
  92     }
  93     branches[b].depth--;
  94     *s = branches[b];
  95     break;
  96   case '|': case ')':
  97     assert(s->depth);
  98     return;
  99   }
 100   s->p++;
 101   visit(s);
 102 }
 103
 104 int main(int argc, char **argv) {
 105   size_t len = 0, count = 0;
 106   char *line = NULL;
 107   int score = 0;
 108   state s = { .x = OFFSET, .y = OFFSET };
 109   int x, y;
 110   int far = 1000;
 111
 112   if (argc > 2)
 113     far = atoi(argv[2]);
 114   if (argc > 1 && *argv[1] && *argv[1] == '^')
 115     s.p = argv[1];
 116   else {
 117     if (argc > 1 && *argv[1] && !(stdin = freopen(argv[1], "r", stdin))) {
 118       perror("failure");
 119       exit(2);
 120     }
 121     if (getline(&line, &len, stdin) < 0) {
 122       fprintf(stderr, "invalid input\n");
 123       exit(1);
 124     }
 125     s.p = line;
 126   }
 127   orig = s.p;
 128   grid[s.y][s.x] = 1;
 129   visit(&s);
 130   for (y = 0; y < LIMIT; y++)
 131     for (x = 0; x < LIMIT; x++) {
 132       if (grid[y][x] > far)
 133         count++;
 134       if (grid[y][x] > score)
 135         score = grid[y][x];
 136     }
 137   printf("Furthest point is %d doors away, %zu rooms beyond %d\n",
 138          score - 1, count, far);
 139   return 0;
 140 }