2017/advent6.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6
   7 static void
   8 dump(const char *prefix, int banks, int *state)
   9 {
  10   puts(prefix);
  11   for (int i = 0; i < banks; i++)
  12     printf(" %d", state[i]);
  13   puts("");
  14 }
  15
  16 typedef struct entry entry;
  17 struct entry {
  18   int *state;
  19   entry *next;
  20 } head;
  21
  22 static entry *
  23 cycle(int banks, entry *in)
  24 {
  25   int i;
  26   int max = 0;
  27   for (i = 0; i < banks; i++)
  28     if (in->state[i] > in->state[max])
  29       max = i;
  30   int remaining = in->state[max];
  31   entry *out = calloc(1, sizeof *out);
  32   out->state = malloc(banks * sizeof *out->state);
  33   memcpy(out->state, in->state, banks * sizeof *out->state);
  34   in->next = out;
  35   out->state[max] = 0;
  36   while (remaining--)
  37     out->state[++max % banks]++;
  38   return out;
  39 }
  40
  41 int
  42 main(int argc, char **argv)
  43 {
  44   if (argc < 3)
  45     return 1;
  46   int banks = atoi(argv[1]);
  47   if (banks != argc - 2)
  48     return 2;
  49   head.state = malloc(banks * sizeof *head.state);
  50   int i;
  51   for (i = 0; i < banks; i++)
  52     head.state[i] = atoi(argv[i + 2]);
  53   dump("starting with", banks, head.state);
  54   entry *e = &head;
  55   while (1) {
  56     entry *next = cycle(banks, e);
  57     //    dump("next", banks, next->state);
  58     e = &head;
  59     while (memcmp(e->state, next->state, banks * sizeof *e->state))
  60       e = e->next;
  61     if (e->next)
  62       break;
  63   }
  64   dump("repeat state", banks, e->state);
  65   const char *msg;
  66 #if 0 // part 1
  67   e = &head;
  68   msg = "loop at cycle";
  69 #else // part 2
  70   msg = "loop length";
  71 #endif
  72   for (i = 0; e->next; i++, e = e->next);
  73   printf("%s %d\n", msg, i);
  74   return 0;
  75 }