2018/day13.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 LIMIT 160
  20 #define MAX 20
  21
  22 static uint8_t map[LIMIT][LIMIT];
  23 static struct cart {
  24   char id;
  25   uint8_t x; /* coordinate on map to learn current direction */
  26   uint8_t y;
  27   char current; /* what character to put back into map */
  28   uint8_t turn; /* next intersection: 0 left, 1 straight, 2 right, 3 dead */
  29 } carts[MAX];
  30
  31 static int sorter(const void *one, const void *two) {
  32   const struct cart *a = one;
  33   const struct cart *b = two;
  34   if (a->turn != 3 && b->turn == 3)
  35     return -1;
  36   if (a->turn == 3 && b->turn != 3)
  37     return 1;
  38   if (a->y < b->y)
  39     return -1;
  40   if (a->y > b->y)
  41     return 1;
  42   if (a->x < b->x)
  43     return -1;
  44   if (a->x > b->x)
  45     return 1;
  46   return 0;
  47 }
  48
  49 static void dump(int tick, int max, int ncarts) {
  50   int i;
  51   debug("\ntick %d:\n", tick);
  52   for (i = 0; (getenv("DEBUG") ?: "1")[0] == '2' && i < max; i++)
  53     debug("%s\n", map[i]);
  54   debug("%d carts at:\n", ncarts);
  55   for (i = 0; i < ncarts; i++) {
  56     char p = map[carts[i].y][carts[i].x];
  57     debug("%d: %d,%d %c on %c next %c turn %c\n", carts[i].id, carts[i].x,
  58           carts[i].y, map[carts[i].y][carts[i].x], carts[i].current,
  59           map[carts[i].y - (p == '^') + (p == 'v')]
  60           [carts[i].x - (p == '<') + (p == '>')],
  61           "lsrX"[carts[i].turn]);
  62   }
  63 }
  64
  65 int move(int ticks, struct cart *cart) {
  66   uint8_t c = map[cart->y][cart->x];
  67   uint8_t *p;
  68   map[cart->y][cart->x] = cart->current;
  69   switch (c) {
  70   case '^':
  71     assert(cart->y);
  72     p = &map[--cart->y][cart->x];
  73     switch (cart->current = *p) {
  74     case '|': *p = '^'; break;
  75     case '\\': *p = '<'; break;
  76     case '/': *p = '>'; break;
  77     case '+':
  78       switch (cart->turn) {
  79       case 0: *p = '<'; cart->turn = 1; break;
  80       case 1: *p = '^'; cart->turn = 2; break;
  81       case 2: *p = '>'; cart->turn = 0; break;
  82       default: assert(0);
  83       }
  84       break;
  85     default:
  86       goto collide;
  87     }
  88     break;
  89   case 'v':
  90     assert(cart->y < LIMIT - 1);
  91     p = &map[++cart->y][cart->x];
  92     switch (cart->current = *p) {
  93     case '|': *p = 'v'; break;
  94     case '\\': *p = '>'; break;
  95     case '/': *p = '<'; break;
  96     case '+':
  97       switch (cart->turn) {
  98       case 0: *p = '>'; cart->turn = 1; break;
  99       case 1: *p = 'v'; cart->turn = 2; break;
 100       case 2: *p = '<'; cart->turn = 0; break;
 101       default: assert(0);
 102       }
 103       break;
 104     default:
 105       goto collide;
 106     }
 107     break;
 108   case '<':
 109     assert(cart->x);
 110     p = &map[cart->y][--cart->x];
 111     switch (cart->current = *p) {
 112     case '-': *p = '<'; break;
 113     case '\\': *p = '^'; break;
 114     case '/': *p = 'v'; break;
 115     case '+':
 116       switch (cart->turn) {
 117       case 0: *p = 'v'; cart->turn = 1; break;
 118       case 1: *p = '<'; cart->turn = 2; break;
 119       case 2: *p = '^'; cart->turn = 0; break;
 120       default: assert(0);
 121       }
 122       break;
 123     default:
 124       goto collide;
 125     }
 126     break;
 127   case '>':
 128     assert(cart->x < LIMIT - 1);
 129     p = &map[cart->y][++cart->x];
 130     switch (cart->current = *p) {
 131     case '-': *p = '>'; break;
 132     case '\\': *p = 'v'; break;
 133     case '/': *p = '^'; break;
 134     case '+':
 135       switch (cart->turn) {
 136       case 0: *p = '^'; cart->turn = 1; break;
 137       case 1: *p = '>'; cart->turn = 2; break;
 138       case 2: *p = 'v'; cart->turn = 0; break;
 139       default: assert(0);
 140       }
 141       break;
 142     default:
 143       goto collide;
 144     }
 145     break;
 146   default:
 147     assert(0);
 148   }
 149   return 0;
 150  collide:
 151   printf("tick %d: collision at coordinate %d,%d\n", ticks, cart->x, cart->y);
 152   debug("removing %d\n", cart->id);
 153   cart->turn = 3;
 154   return 1;
 155 }
 156
 157 int main(int argc, char **argv) {
 158   size_t len = 0, count = 0;
 159   char *line;
 160   char *p;
 161   int ncarts = 0;
 162   int ticks = 0;
 163   int i;
 164
 165   /* Part 1 - read in map */
 166   if (argc > 1 && !(stdin = freopen(argv[1], "r", stdin))) {
 167     perror("failure");
 168     exit(2);
 169   }
 170
 171   while (getline(&line, &len, stdin) >= 0) {
 172     p = strspn(line, "^v<> /\\|-+") + line;
 173     if (*p != '\n' || p - line > LIMIT) {
 174       fprintf(stderr, "recompile with larger limit\n");
 175       exit(1);
 176     }
 177     p = strcspn(line, "^v<>\n") + line;
 178     while (*p != '\n') {
 179       carts[ncarts].x = p - line;
 180       carts[ncarts].y = count;
 181       if (*p == '^' || *p == 'v')
 182         carts[ncarts].current = '|';
 183       else
 184         carts[ncarts].current = '-';
 185       carts[ncarts].id = ncarts;
 186       ncarts++;
 187       p++;
 188       p = strcspn(p, "^v<>\n") + p;
 189     }
 190     memcpy(map[count++], line, p - line);
 191     if (count == LIMIT) {
 192       fprintf(stderr, "recompile with larger limit\n");
 193       exit(1);
 194     }
 195   }
 196   printf("read %zu lines, found %d carts\n", count, ncarts);
 197   qsort(carts, ncarts, sizeof *carts, sorter);
 198   dump(ticks, count, ncarts);
 199   if (!(ncarts % 2)) {
 200     fprintf(stderr, "expecting odd number of carts\n");
 201     exit(1);
 202   }
 203
 204   /* Part 2 - iterate until last collision */
 205   int n = ncarts;
 206   while (n > 1) {
 207     ticks++;
 208     for (i = 0; i < ncarts; i++)
 209       if (carts[i].turn < 3 && move(ticks, &carts[i]))
 210         for (int j = 0; j < ncarts; j++)
 211           if (i != j && carts[j].turn < 3 &&
 212               carts[i].x == carts[j].x && carts[i].y == carts[j].y) {
 213             debug("removing %d\n", carts[j].id);
 214             carts[j].turn = 3;
 215             map[carts[i].y][carts[i].x] = carts[j].current;
 216             n -= 2;
 217           }
 218     qsort(carts, ncarts, sizeof *carts, sorter);
 219     dump(ticks, count, n);
 220   }
 221   printf("completed in %d ticks, last cart at %d,%d\n", ticks, carts->x,
 222          carts->y);
 223   return 0;
 224 }