2018/day9.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 <assert.h>
   8 #include <inttypes.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 typedef struct marble marble;
  20 struct marble {
  21   int value;
  22   marble *l;
  23   marble *r;
  24 };
  25
  26 static void dump1(marble *c) {
  27   debug("%d,%d,%d\n", c->l->value, c->value, c->r->value);
  28 }
  29
  30 static void dump(int i, marble *c) {
  31   if (i > 25)
  32     return;
  33   debug(" Iteration %d:\n", i);
  34   dump1(c->l->l);
  35   dump1(c->l);
  36   dump1(c);
  37   dump1(c->r);
  38   dump1(c->r->r);
  39 }
  40
  41 int main(int argc, char **argv) {
  42   int players = 9;
  43   int marbles = 25;
  44   int i;
  45   uint64_t best = 0;
  46   uint64_t *list;
  47   marble *current;
  48   marble *tmp;
  49
  50   if (argc > 1)
  51     players = atoi(argv[1]);
  52   if (argc > 2)
  53     marbles = atoi(argv[2]);
  54
  55   current = calloc(1, sizeof *current);
  56   current->l = current->r = current;
  57   list = calloc(players, sizeof *list);
  58   assert(list);
  59
  60   dump(0, current);
  61   for (i = 1; i <= marbles; dump(i++, current)) {
  62     if (i % 23) {
  63       tmp = calloc(1, sizeof *tmp);
  64       assert(tmp);
  65       tmp->value = i;
  66       tmp->l = current->r;
  67       tmp->r = current->r->r;
  68       current = current->r->r = tmp->r->l = tmp;
  69     } else {
  70       tmp = current->l->l->l->l->l->l->l;
  71       current = tmp->l->r = tmp->r;
  72       tmp->r->l = tmp->l;
  73       list[i % players] += i + tmp->value;
  74       free(tmp);
  75     }
  76   }
  77
  78   for (i = 0; i < players; i++)
  79     if (list[i] > best)
  80       best = list[i];
  81   printf("best: %" PRIu64 "\n", best);
  82   return 0;
  83 }