2016/advent17.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 "md5.h"
   8
   9 void
  10 generate (int x, int y, const char *prefix, FILE *f)
  11 {
  12   unsigned char sum[16];
  13   md5_buffer(prefix, strlen (prefix), sum);
  14   if ((sum[0] >> 4) > 10 && y < 3)
  15     fprintf (f, "%d%d%sU\n", x, y + 1, prefix);
  16   if ((sum[0] & 15) > 10 && y)
  17     fprintf (f, "%d%d%sD\n", x, y - 1, prefix);
  18   if ((sum[1] >> 4) > 10 && x)
  19     fprintf (f, "%d%d%sL\n", x - 1, y, prefix);
  20   if ((sum[1] & 15) > 10 && x < 3)
  21     fprintf (f, "%d%d%sR\n", x + 1, y, prefix);
  22 }
  23
  24 int
  25 main (int argc, char **argv)
  26 {
  27   char *salt = "edjrjqaa";
  28   if (argc == 2)
  29     salt = argv[1];
  30   int gen = 0;
  31   char *str1, *str2 = NULL;
  32   size_t size1, size2 = 0;
  33   size1 = asprintf (&str1, "03%s\n", salt);
  34   FILE *f;
  35   int max = 0;
  36   while (1) {
  37     gen++;
  38     if (getenv ("DEBUG"))
  39       printf (" starting generation %d\n", gen);
  40     char *p = str1;
  41     int seen = 0;
  42     if (!size1) {
  43       printf ("no longer path possible\n");
  44       break;
  45     }
  46     f = open_memstream (&str2, &size2);
  47     do {
  48       int x = *p++ - '0';
  49       int y = *p++ - '0';
  50       char *q = strchr (p, '\n');
  51       *q = '\0';
  52       if (getenv ("DEBUG"))
  53         printf ("  visiting %d %d %s\n", x, y, p);
  54       seen++;
  55       if (x == 3 && !y) {
  56         static bool print = true;
  57         if (print)
  58           printf ("shortest solution: %s\n", p);
  59         print = false;
  60         max = gen - 1;
  61       } else
  62         generate (x, y, p, f);
  63       p = q + 1;
  64     } while (p < str1 + size1);
  65     if (getenv ("DEBUG"))
  66       printf (" generation %d visited %d paths\n", gen, seen);
  67     fflush (f);
  68     free (str1);
  69     str1 = str2;
  70     size1 = size2;
  71     str2 = NULL;
  72     size2 = 0;
  73   }
  74   printf ("completed after %d steps, longest at %d\n", gen, max);
  75   return 0;
  76 }