2018/day15.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 33 /* Grid size */
  20 #define MAX 30 /* Initial units */
  21
  22 static uint8_t map[LIMIT][LIMIT + 1];
  23 static uint8_t distance[LIMIT][LIMIT];
  24 static uint8_t from[LIMIT][LIMIT];
  25 static struct unit {
  26   char id;
  27   char type; /* E, G, or X */
  28   uint8_t x; /* coordinate on map */
  29   uint8_t y;
  30   short hp;
  31   short attack;
  32 } units[MAX];
  33
  34 static int sorter(const void *one, const void *two) {
  35   const struct unit *a = one;
  36   const struct unit *b = two;
  37   if (a->type != 'X' && b->type == 'X')
  38     return -1;
  39   if (a->type == 'X' && b->type != 'X')
  40     return 1;
  41   if (a->y < b->y)
  42     return -1;
  43   if (a->y > b->y)
  44     return 1;
  45   if (a->x < b->x)
  46     return -1;
  47   if (a->x > b->x)
  48     return 1;
  49   return 0;
  50 }
  51
  52 /* Return character type of enemy */
  53 static char enemy(struct unit *u) {
  54   assert(u->type != 'X');
  55   return "EG"[u->type == 'E'];
  56 }
  57
  58 /* Return bitmap of spots where c is found: 1 up, 2 left, 4 right, 8 down */
  59 static int nextto(int x, int y, char c) {
  60   int ret = 0;
  61   assert(x && x < LIMIT && y && y < LIMIT);
  62   if (map[y - 1][x] == c)
  63     ret |= 1;
  64   if (map[y][x - 1] == c)
  65     ret |= 2;
  66   if (map[y][x + 1] == c)
  67     ret |= 3;
  68   if (map[y + 1][x] == c)
  69     ret |= 4;
  70   return ret;
  71 }
  72
  73 /* Check for a best candidate */
  74 static int check(int old, int x, int y) {
  75   if (old == 0 || y < (old & 0xff) ||
  76       (y == (old & 0xff) && (x << 8 < (old & 0xff00))))
  77     return (from[y][x] << 16) | (x << 8) | y;
  78   return old;
  79 }
  80
  81 /* Return (dir << 16) | (x << 8) | y of the current position or best '.'
  82    position that neighbors @c, else -1 */
  83 static int locate(int startx, int starty, char c) {
  84   int i, x, y;
  85   int best = 0;
  86   bool found = true;
  87   if (nextto(startx, starty, c))
  88     return (startx << 8) | starty;
  89   memset(distance, -1, sizeof(distance));
  90   memset(from, 0, sizeof(from));
  91   i = distance[starty][startx] = 1;
  92   from[starty - 1][startx] = 1;
  93   from[starty][startx - 1] = 2;
  94   from[starty][startx + 1] = 4;
  95   from[starty + 1][startx] = 8;
  96   while (!best && found) {
  97     found = false;
  98     for (y = 1; y < LIMIT - 1; y++)
  99       for (x = 1; x < LIMIT - 1; x++)
 100         if (distance[y][x] == i) {
 101           if (map[y - 1][x] == '.' && distance[y - 1][x] > i) {
 102             from[y - 1][x] |= from[y][x];
 103             if (nextto(x, y - 1, c))
 104               best = check(best, x, y - 1);
 105             else
 106               found = (distance[y - 1][x] = i + 1);
 107           }
 108           if (map[y][x - 1] == '.' && distance[y][x - 1] > i) {
 109             from[y][x - 1] |= from[y][x];
 110             if (nextto(x - 1, y, c))
 111               best = check(best, x - 1, y);
 112             else
 113               found = (distance[y][x - 1] = i + 1);
 114           }
 115           if (map[y][x + 1] == '.' && distance[y][x + 1] > i) {
 116             from[y][x + 1] |= from[y][x];
 117             if (nextto(x + 1, y, c))
 118               best = check(best, x + 1, y);
 119             else
 120               found = (distance[y][x + 1] = i + 1);
 121           }
 122           if (map[y + 1][x] == '.' && distance[y + 1][x] > i) {
 123             from[y + 1][x] |= from[y][x];
 124             if (nextto(x, y + 1, c))
 125               best = check(best, x, y + 1);
 126             else
 127               found = (distance[y + 1][x] = i + 1);
 128           }
 129         }
 130     i++;
 131   }
 132   return best ? best : -1;
 133 }
 134
 135 static void dump(int tick, int rows, int nunits) {
 136   int i;
 137   debug("\ntick %d:\n", tick);
 138   for (i = 0; (getenv("DEBUG") ?: "1")[0] == '2' && i < rows; i++)
 139     debug("%s\n", map[i]);
 140   debug("%d units at:\n", nunits);
 141   for (i = 0; i < nunits; i++) {
 142     if (units[i].type == 'X')
 143       debug("%d: dead\n", units[i].id);
 144     else {
 145       assert(map[units[i].y][units[i].x] == units[i].type);
 146       debug("%d: %d,%d %c with hp %d attack %d\n", units[i].id, units[i].x,
 147             units[i].y, units[i].type, units[i].hp, units[i].attack);
 148     }
 149   }
 150 }
 151
 152 int main(int argc, char **argv) {
 153   size_t len = 0, count = 0;
 154   char *line;
 155   char *p;
 156   int nunits = 0;
 157   int ticks = 0;
 158   int i, j;
 159   int sum = 0;
 160   int attack = 3;
 161   int ret = 0;
 162
 163   /* Part 1 - read in map */
 164   if (argc > 2)
 165     attack = atoi(argv[2]);
 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, "#.GE") + line;
 173     if (*p != '\n' || p - line > LIMIT) {
 174       fprintf(stderr, "recompile with larger limit\n");
 175       exit(1);
 176     }
 177     p = strcspn(line, "GE\n") + line;
 178     while (*p != '\n') {
 179       units[nunits].id = nunits + 1;
 180       units[nunits].type = *p;
 181       units[nunits].x = p - line;
 182       units[nunits].y = count;
 183       units[nunits].hp = 200;
 184       units[nunits].attack = *p == 'G' ? 3 : attack;
 185       nunits++;
 186       p++;
 187       p = strcspn(p, "GE\n") + p;
 188     }
 189     memcpy(map[count++], line, p - line);
 190     if (count == LIMIT) {
 191       fprintf(stderr, "recompile with larger limit\n");
 192       exit(1);
 193     }
 194   }
 195   printf("read %zu lines, found %d units\n", count, nunits);
 196   qsort(units, nunits, sizeof *units, sorter);
 197   dump(ticks, count, nunits);
 198
 199   /* Part 2 - iterate until one side wins */
 200   while (1) {
 201     for (i = 0; i < nunits; i++) {
 202       /* Part 2a: Check */
 203       if (units[i].type == 'X')
 204         continue;
 205       for (j = 0; j < nunits; j++) {
 206         if (i == j)
 207           continue;
 208         if (units[j].type == enemy(&units[i]))
 209           break;
 210       }
 211       if (j == nunits) {
 212         printf("combat ended during tick %d\n", ticks);
 213         goto complete;
 214       }
 215
 216       /* Part 2b: Move */
 217       int xy = locate(units[i].x, units[i].y, enemy(&units[i]));
 218       if (xy < 0)
 219         debug("No move possible for unit %d\n", units[i].id);
 220       else if ((xy & 0xffff) != ((units[i].x << 8) | units[i].y)) {
 221         debug("Moving unit %d closer to %d,%d", units[i].id,
 222               xy >> 8 & 0xff, xy & 0xff);
 223         assert(xy >> 16);
 224         map[units[i].y][units[i].x] = '.';
 225         if (xy & 0x10000)
 226           units[i].y--;
 227         else if (xy & 0x20000)
 228           units[i].x--;
 229         else if (xy & 0x40000)
 230           units[i].x++;
 231         else
 232           units[i].y++;
 233         debug(" via %d,%d\n", units[i].x, units[i].y);
 234         map[units[i].y][units[i].x] = units[i].type;
 235       } else
 236         debug("Unit %d already in range\n", units[i].id);
 237
 238       /* Part 2c: Attack */
 239       if (nextto(units[i].x, units[i].y, enemy(&units[i]))) {
 240         int best = i;
 241         int hp = 201;
 242         for (j = 0; j < nunits; j++) {
 243           if (units[j].type != enemy(&units[i]))
 244             continue;
 245           if (abs(units[i].x - units[j].x) +
 246               abs(units[i].y - units[j].y) == 1) {
 247             if (units[j].hp < hp) {
 248               best = j;
 249               hp = units[j].hp;
 250             } else if (units[j].hp == hp &&
 251                        units[j].y * LIMIT + units[j].x <
 252                        units[best].y * LIMIT + units[best].x) {
 253               best = j;
 254             }
 255           }
 256         }
 257         if (best != i) {
 258           units[best].hp -= units[i].attack;
 259           debug("unit %d attacking %d to %d\n", units[i].id, units[best].id,
 260                 units[best].hp);
 261           if (units[best].hp <= 0) {
 262             debug("%c unit %d killed\n", units[best].type, units[best].id);
 263             if (units[best].type == 'E') {
 264               printf("attack %d too low: elf casualty in tick %d\n",
 265                      attack, ticks);
 266               ret = 1;
 267             }
 268             units[best].type = 'X';
 269             units[best].hp = 0;
 270             map[units[best].y][units[best].x] = '.';
 271           }
 272         }
 273       }
 274     }
 275     qsort(units, nunits, sizeof *units, sorter);
 276     dump(++ticks, count, nunits);
 277   }
 278  complete:
 279   qsort(units, nunits, sizeof *units, sorter);
 280   dump(ticks + 1, count, nunits);
 281   for (i = 0; i < nunits; i++) {
 282     sum += units[i].hp;
 283   }
 284   printf("%c wins, remaining hitpoints %d, score %d\n", units->type, sum,
 285          sum * ticks);
 286   return ret;
 287 }