2018/day22.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 MAXX 30
  24 #define MAXY 820
  25 #define SLOP 20
  26 static struct spot {
  27   int idx;
  28   int ero;
  29   char type; /* '.', '=', or '|'; thanks to ASCII, risk is (type/4+1)%3 */
  30   int t;
  31   int c;
  32   int n;
  33 } grid[MAXY][MAXX];
  34 static int maxx;
  35 static int maxy;
  36
  37 static char lookup(int i) {
  38   if (i == -1)
  39     return '-';
  40   if (i < 10)
  41     return '0' + i;
  42   if (i < 10 + 26)
  43     return 'a' + i - 10;
  44   if (i < 10 + 26 + 26)
  45     return 'A' + i - 10 - 26;
  46   return '+';
  47 }
  48
  49 static void dump(int level) {
  50   int i, j;
  51   if (!debug("\niter %d:\n", level))
  52     return;
  53   for (j = 0; j <= maxy; j++) {
  54     for (i = 0; i <= maxx; i++)
  55       debug("%c%c%c%c ", grid[j][i].type, lookup(grid[j][i].t),
  56             lookup(grid[j][i].c), lookup(grid[j][i].n));
  57     debug("\n");
  58   }
  59 }
  60
  61 static bool try(int *p, int other, int add) {
  62   if (other == -1)
  63     return false;
  64   if (*p == -1 || other + add < *p) {
  65     *p = other + add;
  66     return true;
  67   }
  68   return false;
  69 }
  70
  71 static bool process(int x, int y) {
  72   int *p;
  73   bool ret = false;
  74   switch (grid[y][x].type) {
  75   case '.':
  76     p = &grid[y][x].t;
  77     ret |= try(p, grid[y][x].c, 7);
  78     if (y)
  79       ret |= try(p, grid[y - 1][x].t, 1);
  80     if (x)
  81       ret |= try(p, grid[y][x - 1].t, 1);
  82     if (x < maxx)
  83       ret |= try(p, grid[y][x + 1].t, 1);
  84     if (y < maxy)
  85       ret |= try(p, grid[y + 1][x].t, 1);
  86     p = &grid[y][x].c;
  87     ret |= try(p, grid[y][x].t, 7);
  88     if (y)
  89       ret |= try(p, grid[y - 1][x].c, 1);
  90     if (x)
  91       ret |= try(p, grid[y][x - 1].c, 1);
  92     if (x < maxx)
  93       ret |= try(p, grid[y][x + 1].c, 1);
  94     if (y < maxy)
  95       ret |= try(p, grid[y + 1][x].c, 1);
  96     break;
  97   case '=':
  98     p = &grid[y][x].c;
  99     ret |= try(p, grid[y][x].n, 7);
 100     if (y)
 101       ret |= try(p, grid[y - 1][x].c, 1);
 102     if (x)
 103       ret |= try(p, grid[y][x - 1].c, 1);
 104     if (x < maxx)
 105       ret |= try(p, grid[y][x + 1].c, 1);
 106     if (y < maxy)
 107       ret |= try(p, grid[y + 1][x].c, 1);
 108     p = &grid[y][x].n;
 109     ret |= try(p, grid[y][x].c, 7);
 110     if (y)
 111       ret |= try(p, grid[y - 1][x].n, 1);
 112     if (x)
 113       ret |= try(p, grid[y][x - 1].n, 1);
 114     if (x < maxx)
 115       ret |= try(p, grid[y][x + 1].n, 1);
 116     if (y < maxy)
 117       ret |= try(p, grid[y + 1][x].n, 1);
 118     break;
 119   case '|':
 120     p = &grid[y][x].n;
 121     ret |= try(p, grid[y][x].t, 7);
 122     if (y)
 123       ret |= try(p, grid[y - 1][x].n, 1);
 124     if (x)
 125       ret |= try(p, grid[y][x - 1].n, 1);
 126     if (x < maxx)
 127       ret |= try(p, grid[y][x + 1].n, 1);
 128     if (y < maxy)
 129       ret |= try(p, grid[y + 1][x].n, 1);
 130     p = &grid[y][x].t;
 131     ret |= try(p, grid[y][x].n, 7);
 132     if (y)
 133       ret |= try(p, grid[y - 1][x].t, 1);
 134     if (x)
 135       ret |= try(p, grid[y][x - 1].t, 1);
 136     if (x < maxx)
 137       ret |= try(p, grid[y][x + 1].t, 1);
 138     if (y < maxy)
 139       ret |= try(p, grid[y + 1][x].t, 1);
 140     break;
 141   default:
 142     abort();
 143   }
 144   return ret;
 145 }
 146
 147 int main(int argc, char **argv) {
 148   int depth = 510;
 149   int x = 10;
 150   int y = 10;
 151   int i, j;
 152   int risk = 0;
 153
 154   /* Part 1 - populate grid */
 155   if (argc == 3) {
 156     depth = atoi(argv[1]);
 157     x = atoi(argv[2]);
 158     y = atoi(argv[3]);
 159   } else if (argc > 1 &&
 160              (!(stdin = freopen(argv[1], "r", stdin)) ||
 161               scanf("depth: %d\ntarget: %d,%d\n", &depth, &x, &y) != 3)) {
 162     fprintf(stderr, "bad input\n");
 163     exit(2);
 164   }
 165   maxx = x + SLOP;
 166   maxy = y + SLOP;
 167   if (maxx >= MAXX || maxy >= MAXY) {
 168     fprintf(stderr, "bad input\n");
 169     exit(2);
 170   }
 171
 172   for (j = 0; j <= maxy; j++)
 173     for (i = 0; i <= maxx; i++) {
 174       if (i == 0 && j == 0)
 175         grid[j][i].idx = 0;
 176       else if (i == x && j == y)
 177         grid[j][i].idx = 0;
 178       else if (j == 0)
 179         grid[j][i].idx = i * 16807;
 180       else if (i == 0)
 181         grid[j][i].idx = j  * 48271;
 182       else
 183         grid[j][i].idx = grid[j][i - 1].ero * grid[j - 1][i].ero;
 184       grid[j][i].ero = (grid[j][i].idx + depth) % 20183;
 185       if (grid[j][i].ero % 3 == 0)
 186         grid[j][i].type = '.';
 187       else if (grid[j][i].ero % 3 == 1)
 188         grid[j][i].type = '=';
 189       else
 190         grid[j][i].type = '|';
 191       if (i <= x && j <= y)
 192         risk += (grid[j][i].type / 4 + 1) % 3;
 193       grid[j][i].t = -1;
 194       grid[j][i].c = -1;
 195       grid[j][i].n = -1;
 196     }
 197   dump(0);
 198   printf("resulting risk %d\n", risk);
 199
 200   int iter = 0;
 201   bool done = false;
 202   grid[0][0].t = 0;
 203   while (!done) {
 204     done = true;
 205     for (j = 0; j <= maxy; j++)
 206       for (i = 0; i <= maxx; i++)
 207         if (process(i, j))
 208           done = false;
 209     dump(++iter);
 210   }
 211   printf("after %d cycles to settle, shortest path to %d,%d torch is %d\n",
 212          iter, x, y, grid[y][x].t);
 213   return 0;
 214 }