2019/day16.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 <stdint.h>
   8 #include <inttypes.h>
   9 #include <ctype.h>
  10
  11 static int debug_level = -1;
  12 static void
  13 debug_raw(int level, const char *fmt, ...) {
  14   va_list ap;
  15   if (debug_level < 0)
  16     debug_level = atoi(getenv("DEBUG") ?: "0");
  17   if (debug_level >= level) {
  18     va_start(ap, fmt);
  19     vfprintf(stderr, fmt, ap);
  20     va_end(ap);
  21   }
  22 }
  23 #define debug(...) debug_raw(1, __VA_ARGS__)
  24
  25 static int __attribute__((noreturn))
  26 die(const char *fmt, ...)
  27 {
  28   va_list ap;
  29   va_start(ap, fmt);
  30   vprintf(fmt, ap);
  31   va_end(ap);
  32   putchar('\n');
  33   exit(1);
  34 }
  35
  36 #define MAX 650
  37 static char orig[MAX];
  38 static char data[2][MAX * 10000];
  39 static int len;
  40 static int phase;
  41
  42 static void
  43 dump(char *s) {
  44   printf("after phase %d, signal begins with %.8s\n", phase, s);
  45 }
  46
  47 static void
  48 do_phase(char *old, char *new, int offset) {
  49   int i, j, t;
  50   static int8_t m[] = { 0, 1, 0, -1 };
  51
  52   /* First half is painful */
  53   for (i = offset; i < len / 2; i++) {
  54     for (t = 0, j = offset; j < len; j++)
  55       t += (old[j] - '0') * m[(j + 1) / (i + 1) % 4];
  56     new[i] = (abs(t) % 10) + '0';
  57     debug(" i=%d: %c\n", i, new[i]);
  58   }
  59   /* Second half is easy */
  60   for (t = 0, i = len - 1; i >= offset && i >= len / 2; i--) {
  61     t += old[i] - '0';
  62     new[i] = t % 10 + '0';
  63     debug(" i=%d: %c\n", i, new[i]);
  64   }
  65   phase++;
  66   if (debug_level)
  67     dump(new);
  68 }
  69
  70 int
  71 main(int argc, char **argv) {
  72   int ch, i;
  73   int iter = 100;
  74   int reps = 10000;
  75   int offset;
  76
  77   debug("");
  78   if (argc > 1 && strcmp(argv[1], "-"))
  79     if (!(stdin = freopen(argv[1], "r", stdin))) {
  80       perror("failure");
  81       exit(2);
  82     }
  83
  84   if (argc > 2)
  85     iter = atoi(argv[2]);
  86   if (argc > 3)
  87     reps = atoi(argv[3]);
  88   if (reps > sizeof data[0] / sizeof orig)
  89     die("too many reps");
  90
  91   while (isdigit(ch = getchar())) {
  92     orig[len] = ch;
  93     if (len++ >= MAX)
  94       die("recompile with larger MAX");
  95   }
  96   printf("Operating on length %d\n", len);
  97   dump(orig);
  98
  99   /* Part 1 */
 100   memcpy(data[0], orig, len);
 101   for (i = 0; i < iter; i++)
 102     do_phase(data[phase % 2], data[1 - phase % 2], 0);
 103   dump(data[phase % 2]);
 104
 105   /* Part 2 */
 106   ch = orig[7];
 107   orig[7] = '\0';
 108   offset = atoi(orig);
 109   orig[7] = ch;
 110   if (argc > 4) {
 111     printf("ignoring offset %d\n", offset);
 112     offset = 0;
 113   } else {
 114     if (offset >= len * 10000)
 115       die("offset too large");
 116     printf("need offset %d among len %d, try %d reps\n", offset, len * 10000,
 117            (len * 10000 - offset + (len / 2 - 1)) / (len / 2));
 118     reps = (len * 10000 - offset + (len / 2 - 1)) / (len / 2);
 119     offset -= (10000 - reps) * len;
 120     printf("trying offset %d among len %d instead\n", offset, len * reps);
 121   }
 122
 123   for (i = 0; i < reps; i++)
 124     memcpy(&data[0][i * len], orig, len);
 125   phase = 0;
 126   len *= reps;
 127   for (i = 0; i < iter; i++) {
 128     if (offset < len / 2)
 129       printf("%d\n", i);
 130     do_phase(data[phase % 2], data[1 - phase % 2], offset);
 131   }
 132
 133   if (argc > 4)
 134     printf("%.*s\n", len, data[phase % 2]);
 135   dump(&data[phase % 2][offset]);
 136   return 0;
 137 }