2016/advent19.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include <stdbool.h>
   7 #include <ctype.h>
   8
   9 #define MAX 3005290
  10 bool list[MAX];
  11
  12 int
  13 main (int argc, char **argv)
  14 {
  15   int max = MAX;
  16   if (argc > 1)
  17     max = atoi (argv[1]);
  18   memset (list, true, max);
  19   int cur = 0, steal = max / 2 - 1, i, j;
  20   for (i = 0; i < max - 1; i++) {
  21     if (i && !(i % 20))
  22       printf ("\b\b\b\b\b\b\b\b\b%9d", i), fflush (stdout);
  23     for (j = steal + 1; j < steal + max; j++)
  24       if (list[j % max]) {
  25         if (max < 10)
  26           printf ("position %d taking from %d\n", cur + 1, (j % max) + 1);
  27         list[j % max] = false;
  28         steal = j % max;
  29         break;
  30       }
  31     if ((i & 1) ^ (max & 1))
  32       for (j = steal + 1; j < steal + max; j++)
  33         if (list[j % max]) {
  34           steal = j % max;
  35           break;
  36         }
  37     for (j = cur + 1; j < cur + max; j++)
  38       if (list[j % max]) {
  39         cur = j % max;
  40         break;
  41       }
  42   }
  43   printf ("\na group of %d ends on position %d\n", max, cur + 1);
  44   return 0;
  45 }