2018/day20a.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 char visit(int depth, char end, int *score) {
  22   int c = getchar();
  23   debug("depth %d, visiting %c while looking for %c, score %d\n",
  24         depth, c, end, *score);
  25   switch (c) {
  26   case 'N': case 'E': case 'S': case 'W':
  27     ++*score;
  28     return visit(depth, end, score);
  29   case '$':
  30     if (end != c || depth != 0) {
  31       fprintf(stderr, "unbalanced regex\n");
  32       exit(1);
  33     }
  34     return c;
  35   case '(':
  36     {
  37       int tmp = 0;
  38       int best = 0;
  39       c = visit(depth + 1, '|', &best);
  40       assert(c == '|' && best);
  41       while (visit(depth + 1, ')', &tmp) == '|') {
  42         assert(tmp);
  43         if (tmp > best)
  44           best = tmp;
  45         tmp = 0;
  46       }
  47       if (tmp > best)
  48         best = tmp;
  49       if (tmp) {
  50         *score += best;
  51         return visit(depth, end, score);
  52       }
  53       debug("checking after empty alternation at depth %d\n", depth);
  54       best = *score + best / 2;
  55       c = visit(depth, end, score);
  56       if (best > *score)
  57         *score = best;
  58       return c;
  59     }
  60   case '|': case ')':
  61     if (end != ')' && end != c) {
  62       fprintf(stderr, "unbalanced regex\n");
  63       exit(1);
  64     }
  65     return c;
  66   default:
  67     fprintf(stderr, "unexpected EOF\n");
  68     exit(1);
  69   }
  70 }
  71
  72 int main(int argc, char **argv) {
  73   int score = 0;
  74
  75   if (argc > 1 && !(stdin = freopen(argv[1], "r", stdin))) {
  76     perror("failure");
  77     exit(2);
  78   }
  79   if (getchar() != '^') {
  80     fprintf(stderr, "invalid start\n");
  81     exit(1);
  82   }
  83   visit(0, '$', &score);
  84   printf("Furthest point is %d doors away\n", score);
  85   return 0;
  86 }