2017/advent16.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include <stdint.h>
   7 #include <stdbool.h>
   8
   9 char buf[50000]; // cheat, pre-inspect file
  10
  11 extern uint64_t doit(uint64_t);
  12
  13 const char *
  14 output (uint64_t array)
  15 {
  16   static char out[17];
  17   for (int i = 0; i < 16; i++)
  18     out[i] = ((array & (0xfULL << ((15 - i) * 4))) >> ((15 - i) * 4)) + 'a';
  19   return out;
  20 }
  21
  22 int main(int argc, char **argv)
  23 {
  24   int limit = 1000000000;
  25   if (argc == 2)
  26     limit = atoi (argv[1]);
  27   int a, b, c, j, n;
  28   char x, y;
  29   char *s;
  30   if (getenv ("GEN")) {
  31     int ops = 0;
  32     fread (buf, 1, sizeof buf, stdin);
  33     printf ("#include <stdint.h>\n");
  34     printf ("uint64_t doit(uint64_t n)\n");
  35     printf ("{\n");
  36     printf ("  int i;\n");
  37     printf ("  uint64_t a, b;\n");
  38     s = buf;
  39     while (*s) {
  40       switch (*s++) {
  41       case 's':
  42         ops++;
  43         sscanf(s, "%d%n", &a, &n);
  44         s += n;
  45         printf ("  // s%d\n", a);
  46         printf ("  n = (n >> %d) | (n << %d);\n", a * 4, 64 - a * 4);
  47         break;
  48       case 'x':
  49         ops++;
  50         sscanf(s, "%d/%d%n", &a, &b, &n);
  51         s += n;
  52         printf ("  // x%d/%d\n", a, b);
  53         if (a > b) {
  54           c = a;
  55           a = b;
  56           b = c;
  57         }
  58         printf ("  a = (n & (0xfULL << %d)) >> %d;\n",
  59                 (15 - a) * 4, (b - a) * 4);
  60         printf ("  b = (n & (0xfULL << %d)) << %d;\n",
  61                 (15 - b) * 4, (b - a) * 4);
  62         printf ("  n = (n & %#llx) | a | b;\n",
  63                 -1ULL ^ (0xfULL << ((15 - a) * 4)) ^
  64                 (0xfULL << ((15 - b)  * 4)));
  65         break;
  66       case 'p':
  67         ops++;
  68         sscanf(s, "%c/%c%n", &x, &y, &n);
  69         s += n;
  70         printf ("  // p%c/%c\n", x, y);
  71         x -= 'a';
  72         y -= 'a';
  73         printf ("  for (i = 0; i < 64; i += 4) {\n");
  74         printf ("    if (((n & (0xfULL << i)) >> i) == %d)\n", x);
  75         printf ("      n = (n & ~(0xfULL << i)) | (%dULL << i);\n", y);
  76         printf ("    else if (((n & (0xfULL << i)) >> i) == %d)\n", y);
  77         printf ("      n = (n & ~(0xfULL << i)) | (%dULL << i);\n", x);
  78         printf ("  }\n");
  79         break;
  80       }
  81     }
  82     printf ("  // %d ops\n", ops);
  83     printf ("  return n;\n");
  84     printf ("}\n");
  85     return 0;
  86   }
  87   uint64_t array1 = 0x0123456789abcdefULL;
  88   uint64_t array2 = 0x0123456789abcdefULL;
  89   bool cycle = false;
  90   for (j = 0; j < limit; j++) {
  91     if (j < 10)
  92       printf ("after dance %d: %s\n", (cycle ? j : j * 2), output (array1));
  93     else if (!(j % 1000))
  94       printf ("\b\b\b\b\b\b\b\b\b\b\b\b%10d", j), fflush (stdout);
  95     array1 = doit (array1);
  96     if (!cycle && j < limit) {
  97       array1 = doit (array1);
  98       array2 = doit (array2);
  99       if (array1 == array2) {
 100         printf ("cycle detected at %d\n", j);
 101         j = limit - limit % (j + 1) - 1;
 102         cycle = true;
 103       }
 104     }
 105   }
 106   printf ("\nfinal string: %s\n", output (array1));
 107   return 0;
 108 }