2018/day24.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 LIMIT 10
  24
  25 typedef enum Type {
  26                    RADIATION,
  27                    COLD,
  28                    FIRE,
  29                    BLUDGEONING,
  30                    SLASHING,
  31                    _MAX,
  32 } Type;
  33
  34 typedef struct group group;
  35 struct group {
  36   bool infect;
  37   int id;
  38   int units;
  39   int hp;
  40   int weak;
  41   int immune;
  42   int attack;
  43   Type type;
  44   int initiative;
  45   group *attacker;
  46   group *attacking;
  47 };
  48
  49 static group immune[LIMIT];
  50 static group infect[LIMIT];
  51 static group *order[LIMIT * 2];
  52
  53 static int list(int round) {
  54   int i;
  55   int count1 = 0, count2 = 0;
  56   debug("\nBeginning round %d\n", round);
  57   debug("Immune:\n");
  58   for (i = 0; i < LIMIT; i++)
  59     if (immune[i].units > 0) {
  60       immune[i].attacker = NULL;
  61       immune[i].attacking = NULL;
  62       debug("Group %d(%d) contains %d units, effective power %d\n",
  63             immune[i].id, immune[i].initiative,
  64             immune[i].units, immune[i].units * immune[i].attack);
  65       order[count1++] = &immune[i];
  66     }
  67   debug("Infect:\n");
  68   for (i = 0; i < LIMIT; i++)
  69     if (infect[i].units > 0) {
  70       infect[i].attacker = NULL;
  71       infect[i].attacking = NULL;
  72       debug("Group %d(%d) contains %d units, effective power %d\n",
  73             infect[i].id, infect[i].initiative,
  74             infect[i].units, infect[i].units * infect[i].attack);
  75       order[count1 + count2++] = &infect[i];
  76     }
  77   return count1 && count2 ? count1 + count2 : 0;
  78 }
  79
  80 static int sort_effective(const void *one, const void *two) {
  81   const group *a = *(const group**)one;
  82   const group *b = *(const group**)two;
  83   assert(a->units > 0);
  84   assert(b->units > 0);
  85   if (b->units * b->attack - a->units * a->attack)
  86     return b->units * b->attack - a->units * a->attack;
  87   return b->initiative - a->initiative;
  88 }
  89
  90 static int sort_initiative(const void *one, const void *two) {
  91   const group *a = *(const group**)one;
  92   const group *b = *(const group**)two;
  93   assert(a->units > 0);
  94   assert(b->units > 0);
  95   return b->initiative - a->initiative;
  96 }
  97
  98 static void __attribute__((noreturn)) die(void) {
  99   fprintf(stderr, "unexpected input\n");
 100   exit(1);
 101 }
 102
 103 static const char *lookup(Type t) {
 104   switch (t) {
 105   case RADIATION: return "radiation";
 106   case COLD: return "cold";
 107   case FIRE: return "fire";
 108   case BLUDGEONING: return "bludgeoning";
 109   case SLASHING: return "slashing";
 110   default:
 111     abort();
 112   }
 113 }
 114
 115 static Type decode(const char *s) {
 116   if (!strcmp(s, "radiation"))
 117     return RADIATION;
 118   if (!strcmp(s, "cold"))
 119     return COLD;
 120   if (!strcmp(s, "fire"))
 121     return FIRE;
 122   if (!strcmp(s, "bludgeoning"))
 123     return BLUDGEONING;
 124   if (!strcmp(s, "slashing"))
 125     return SLASHING;
 126   die();
 127 }
 128
 129 static void parse(const char *line, group *g, int boost) {
 130   char *p, *q;
 131   char buf[20];
 132
 133   if (sscanf(line, "%d units each with %d hit points", &g->units,
 134              &g->hp) != 2)
 135     die();
 136   if ((p = strstr(line, "immune to"))) {
 137     p += strlen("immune to");
 138     do {
 139       while (*p == ',' || *p == ' ')
 140         p++;
 141       q = buf;
 142       while (isalpha(*p))
 143         *q++ = *p++;
 144       *q = '\0';
 145       g->immune |= 1 << decode(buf);
 146     } while (*p == ',');
 147   }
 148   if ((p = strstr(line, "weak to"))) {
 149     p += strlen("weak to");
 150     do {
 151       while (*p == ',' || *p == ' ')
 152         p++;
 153       q = buf;
 154       while (isalpha(*p))
 155         *q++ = *p++;
 156       *q = '\0';
 157       g->weak |= 1 << decode(buf);
 158     } while (*p == ',');
 159   }
 160   p = strstr(line, "with an attack");
 161   if (!p || sscanf(p, "with an attack that does %d %20[a-z] damage at "
 162                    "initiative %d\n", &g->attack, buf, &g->initiative) != 3)
 163     die();
 164   g->type = decode(buf);
 165   g->attack += boost;
 166   if (debug("%s group %d: %d units, %d hit points, attack %d %s, "
 167             "initiative %d\n", g->infect ? "infect" : "immune", g->id,
 168             g->units, g->hp, g->attack, lookup(g->type), g->initiative)) {
 169     for (int i = 0; i < _MAX; i++) {
 170       assert(!(g->weak & (1 << i)) || !(g->immune & (1 << i)));
 171       debug(" %s %s,", lookup(i), g->weak & (1 << i) ? "weak" :
 172             g->immune & (1 << i) ? "immune" : "normal");
 173     }
 174     debug("\n");
 175   }
 176 }
 177
 178 static void selection(int count) {
 179   int i, j;
 180   group *attacker;
 181   static group dummy;
 182   group *target;
 183   group *enemies;
 184   int best;
 185   int damage;
 186
 187   debug("\n");
 188   for (i = 0; i < count; i++) {
 189     attacker = order[i];
 190     target = &dummy;
 191     best = 0;
 192     enemies = attacker->infect ? immune : infect;
 193     for (j = 0; j < LIMIT; j++) {
 194       if (enemies[j].units > 0 && !enemies[j].attacker
 195           && !(enemies[j].immune & (1 << attacker->type))) {
 196         damage = attacker->attack * attacker->units;
 197         if (enemies[j].weak & (1 << attacker->type))
 198           damage *= 2;
 199         debug("%s group %d(%d) would deal group %d(%d) %d damage\n",
 200               attacker->infect ? "infect" : "immune", attacker->id,
 201               attacker->initiative, enemies[j].id, enemies[j].initiative,
 202               damage);
 203         if (damage > best ||
 204             (damage == best && enemies[j].attack * enemies[j].units >
 205              target->attack * target->units) ||
 206             (damage == best && enemies[j].attack * enemies[j].units ==
 207              target->attack * target->units
 208              && enemies[j].initiative > target->initiative)) {
 209           best = damage;
 210           target = &enemies[j];
 211         }
 212       }
 213     }
 214     if (target != &dummy) {
 215       attacker->attacking = target;
 216       target->attacker = attacker;
 217     }
 218   }
 219 }
 220
 221 static int attack(int count) {
 222   int i;
 223   int damage;
 224   int killed;
 225   group *attacker;
 226   int ret = 0;
 227
 228   debug("\n");
 229   for (i = 0; i < count; i++) {
 230     attacker = order[i];
 231     if (!attacker->attacking || attacker->units <= 0)
 232       continue;
 233     damage = attacker->attack * attacker->units;
 234     if (attacker->attacking->weak & (1 << attacker->type))
 235       damage *= 2;
 236     ret += killed = damage / attacker->attacking->hp;
 237     debug("%s group %d(%d) attacks group %d(%d), killing %d of %d units\n",
 238           attacker->infect ? "infect" : "immune", attacker->id,
 239           attacker->initiative, attacker->attacking->id,
 240           attacker->attacking->initiative, killed, attacker->attacking->units);
 241     attacker->attacking->units -= killed;
 242   }
 243   return ret;
 244 }
 245
 246 int main(int argc, char **argv) {
 247   size_t len = 0, count = 0;
 248   char *line;
 249   int round = 0;
 250   int sum = 0;
 251   int i;
 252   int boost = 0;
 253
 254   /* Part 1 - read data */
 255   if (argc > 2)
 256     boost = atoi(argv[2]);
 257   if (argc > 1)
 258     if (!(stdin = freopen(argv[1], "r", stdin))) {
 259       perror("failure");
 260       exit(2);
 261     }
 262
 263   if (getline(&line, &len, stdin) < 0 || (strcmp(line, "Immune System:\n")))
 264     die();
 265   while (getline(&line, &len, stdin) > 0) {
 266     if (*line == '\n')
 267       break;
 268     if (count >= LIMIT) {
 269       fprintf(stderr, "recompile with larger LIMIT!\n");
 270       exit(1);
 271     }
 272     immune[count].id = count + 1;
 273     parse(line, &immune[count++], boost);
 274   }
 275   printf("Read %zu immune lines\n", count);
 276   count = 0;
 277   if (getline(&line, &len, stdin) < 0 || (strcmp(line, "Infection:\n")))
 278     die();
 279   while (getline(&line, &len, stdin) > 0) {
 280     if (count >= LIMIT) {
 281       fprintf(stderr, "recompile with larger LIMIT!\n");
 282       exit(1);
 283     }
 284     infect[count].infect = true;
 285     infect[count].id = count + 1;
 286     parse(line, &infect[count++], 0);
 287   }
 288   printf("Read %zu infect lines\n", count);
 289
 290   /* Part 2 - battle */
 291   while ((count = list(round))) {
 292     round++;
 293     qsort(order, count, sizeof *order, sort_effective);
 294     selection(count);
 295     qsort(order, count, sizeof *order, sort_initiative);
 296     if (!attack(count)) {
 297       printf("Stalemate after %d rounds\n", round);
 298       exit(1);
 299     }
 300   }
 301   for (i = 0; i < LIMIT; i++) {
 302     if (immune[i].units > 0)
 303       sum -= immune[i].units;
 304     if (infect[i].units > 0)
 305       sum += infect[i].units;
 306   }
 307   printf("After %d rounds, %d %s units remain\n", round, abs(sum),
 308          sum > 0 ? "infect" : "immune");
 309   return sum > 0;
 310 }