2019/day14.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 <limits.h>
   8
   9 static int do_debug = -1;
  10 void debug(const char *fmt, ...) {
  11   va_list ap;
  12   if (do_debug < 0)
  13     do_debug = !!getenv("DEBUG");
  14   if (do_debug > 0) {
  15     va_start(ap, fmt);
  16     vfprintf(stderr, fmt, ap);
  17     va_end(ap);
  18   }
  19 }
  20
  21 #define LIMIT 60
  22 #define MAXIN 8
  23
  24 struct react {
  25   char out[6];
  26   int produce;
  27   long long avail;
  28   int n_in;
  29   struct {
  30     char in[6];
  31     int consume;
  32     int idx;
  33   } in[MAXIN];
  34 };
  35 struct react list[LIMIT] = { { .out = "ORE", .produce = 1,
  36                                .avail = 1000000000000LL, }, };
  37 static int count;
  38 static int fuel_idx;
  39 static long long produced;
  40
  41 static int __attribute__((noreturn))
  42 die(const char *fmt, ...)
  43 {
  44   va_list ap;
  45   va_start(ap, fmt);
  46   vprintf(fmt, ap);
  47   va_end(ap);
  48   putchar('\n');
  49   exit(1);
  50 }
  51
  52 static int
  53 find(const char *name, int *idx) {
  54   int i;
  55
  56   if (*idx >= 0)
  57     return *idx;
  58   for (i = 0; i <= count; i++)
  59     if (!strcmp(list[i].out, name))
  60       return *idx = i;
  61   die("missing rule for %s", name);
  62 }
  63
  64 static bool
  65 produce(int idx, long long amt) {
  66   int i;
  67   long long need = amt - list[idx].avail;
  68   long long mult = need > 0 ? (need + list[idx].produce
  69                                - 1) / list[idx].produce : 0;
  70
  71   debug("want %lld of %s, have %lld, needs %lld more batches\n", amt,
  72         list[idx].out, list[idx].avail, mult);
  73   if (!idx && need > 0)
  74     return false;
  75   for (i = 0; i < list[idx].n_in; i++)
  76     if (!produce(find(list[idx].in[i].in, &list[idx].in[i].idx),
  77                  mult * list[idx].in[i].consume))
  78       return false;
  79   list[idx].avail += mult * list[idx].produce - amt;
  80   if (idx == fuel_idx)
  81     produced += amt;
  82   return true;
  83 }
  84
  85 int main(int argc, char **argv) {
  86   int ch, i;
  87   long long min;
  88
  89   if (argc > 1)
  90     if (!(stdin = freopen(argv[1], "r", stdin))) {
  91       perror("failure");
  92       exit(2);
  93     }
  94
  95   while ((ch = getchar()) != EOF) {
  96     count++;
  97     if (count >= LIMIT)
  98       die("recompile with larger LIMIT");
  99     ungetc(ch, stdin);
 100     i = 0;
 101     do {
 102       if (scanf(" %d %5[A-Z]", &list[count].in[i].consume,
 103                 list[count].in[i].in) != 2)
 104         die("parse failure at line %d", count - 1);
 105       list[count].in[i].idx = -1;
 106       if (i++ >= MAXIN)
 107         die("recompile with larger MAXIN");
 108     } while (getchar() != ' ');
 109     list[count].n_in = i;
 110     if (scanf("=> %d %5[A-Z]\n", &list[count].produce, list[count].out) != 2)
 111       die("parse failure at line %d", count - 1);
 112     if (!strcmp(list[count].out, "FUEL"))
 113       fuel_idx = count;
 114     debug("parsed instructions for %d %s from %d inputs\n",
 115           list[count].produce, list[count].out, list[count].n_in);
 116   }
 117   printf("scanned %d formulas, fuel at line %d\n", count, fuel_idx - 1);
 118
 119   if (!produce(fuel_idx, 1))
 120     die("unable to produce 1 fuel");
 121   min = 1000000000000LL - list[0].avail;
 122   printf("1 fuel requires %lld ore\n", min);
 123   while (list[0].avail > min) {
 124     printf("producing %lld more...\n", list[0].avail / min);
 125     if (!produce(fuel_idx, list[0].avail / min))
 126       die("unexpected failure in bulk production");
 127   }
 128   while (produce(fuel_idx, 1))
 129     printf("at %lld, used up spares for 1 more...\n", produced);
 130   printf("produced %lld total\n", produced);
 131   return 0;
 132 }