2016/advent11.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 #if 0 // sample problem
  10 #define PAIRS 2
  11 char initial[] = "1.11.23";
  12 //  "hydrogen", "lithium",
  13
  14 #elif 0 // day11.input, part 1
  15 #define PAIRS 5
  16 char initial[] = "1.13333.12222";
  17 //  "promethium", "cobalt", "Curium", "ruthenium", "Plutonium",
  18
  19 #else // day11.input, part 2
  20 #define PAIRS 7
  21 char initial[] = "1.1333311.1222211";
  22 //  "promethium", "cobalt", "Curium", "ruthenium", "Plutonium", "elerium",
  23 //  "dilithium",
  24
  25 #endif
  26
  27 typedef struct state state;
  28 struct state {
  29   char elevator;
  30   union {
  31     struct {
  32       char chips[PAIRS];
  33       char gens[PAIRS];
  34     };
  35     char items[PAIRS * 2];
  36   };
  37 };
  38
  39 char cache[1 << ((PAIRS * 2 + 1) * 2 - 3)];
  40
  41 int hash (state *s)
  42 {
  43   int h = s->elevator - 1;
  44   for (int i = 0; i < PAIRS * 2; i++)
  45     h = (h << 2) + s->items[i] - 1;
  46   return h;
  47 }
  48
  49 bool
  50 valid (state *s)
  51 {
  52   if (s->elevator < 1 || s->elevator > 4)
  53     return false;
  54   for (int i = 0; i < PAIRS; i++) {
  55     if (s->chips[i] == s->gens[i]) // A chip with own generator is safe
  56       continue;
  57     for (int j = 0; j < PAIRS; j++) {
  58       if (i == j)
  59         continue;
  60       if (s->chips[i] == s->gens[j]) // A chip with any other generator fails
  61         return false;
  62     }
  63   }
  64   // No point revisiting a configuration already seen
  65   int h = hash (s);
  66   if (cache[h >> 3] & (1 << (h & 3)))
  67     return false;
  68   cache[h >> 3] |= 1 << (h & 3);
  69   return true;
  70 }
  71
  72 bool
  73 goal (state *s)
  74 {
  75   for (int i = 0; i < PAIRS * 2; i++)
  76     if (s->items[i] != 4)
  77       return false;
  78   return true;
  79 }
  80
  81 state *
  82 parse (const char *str)
  83 {
  84   state *s = malloc (sizeof *s);
  85   const char *p = str;
  86   s->elevator = *p++ - '0';
  87   if (*p++ != '.')
  88     exit (1);
  89   for (int i = 0; i < PAIRS; i++)
  90     s->chips[i] = *p++ - '0';
  91   if (*p++ != '.')
  92     exit (1);
  93   for (int i = 0; i < PAIRS; i++)
  94     s->gens[i] = *p++ - '0';
  95   if (*p && *p != '\n')
  96     exit (1);
  97   return s;
  98 }
  99
 100 bool
 101 out (state *s, FILE *f)
 102 {
 103   putc (s->elevator + '0', f);
 104   putc ('.', f);
 105   for (int i = 0; i < PAIRS; i++)
 106     putc (s->chips[i] + '0', f);
 107   putc ('.', f);
 108   for (int i = 0; i < PAIRS; i++)
 109     putc (s->gens[i] + '0', f);
 110   putc ('\n', f);
 111   return goal (s);
 112 }
 113
 114 bool
 115 generate (state *s, FILE *f)
 116 {
 117   int count = 0;
 118   int e = s->elevator;
 119   int i, j;
 120   bool ret = false;
 121   for (i = 0; i < PAIRS * 2; i++)
 122     if (e == s->items[i])
 123       count++;
 124   if (getenv ("DEBUG"))
 125     printf ("%d items to choose from, producing up to %d states\n", count,
 126             count * (count + 1));
 127   s->elevator++;
 128   for (i = 0; i < PAIRS * 2; i++) {
 129     if (e == s->items[i]) {
 130       s->items[i]++;
 131       if (valid (s))
 132         ret |= out (s, f);
 133       for (j = i + 1; j < PAIRS * 2; j++)
 134         if (e == s->items[j]) {
 135           s->items[j]++;
 136           if (valid (s))
 137             ret |= out (s, f);
 138           s->items[j]--;
 139         }
 140       s->items[i]--;
 141     }
 142   }
 143   s->elevator -= 2;
 144   for (i = 0; i < PAIRS * 2; i++) {
 145     if (e == s->items[i]) {
 146       s->items[i]--;
 147       if (valid (s))
 148         ret |= out (s, f);
 149       for (j = i + 1; j < PAIRS * 2; j++)
 150         if (e == s->items[j]) {
 151           s->items[j]--;
 152           if (valid (s))
 153             ret |= out (s, f);
 154           s->items[j]++;
 155         }
 156       s->items[i]++;
 157     }
 158   }
 159   s->elevator++;
 160   return ret;
 161 }
 162
 163 int main(int argc, char **argv)
 164 {
 165   int generations = 0;
 166   char *str1 = initial, *str2 = NULL;
 167   size_t size1 = strlen (str1), size2 = 0;
 168   bool done = false;
 169   FILE *f;
 170   while (!done) {
 171     printf (" starting generation %d\n", ++generations);
 172     char *p = str1;
 173     int seen = 0;
 174     f = open_memstream (&str2, &size2);
 175     do {
 176       char *q = strchrnul (p, '\n');
 177       state *s = parse (p);
 178       if (getenv ("DEBUG"))
 179         out (s, stdout);
 180       if (generate (s, f))
 181         done = true;
 182       free (s);
 183       seen++;
 184       p = q + 1;
 185     } while (p < str1 + size1 - 1);
 186     printf (" generation %d visited %d states\n", generations, seen);
 187     fflush (f);
 188     if (str1 != initial)
 189       free (str1);
 190     str1 = str2;
 191     size1 = size2;
 192     str2 = NULL;
 193     size2 = 0;
 194   }
 195   printf ("found solution in %d generations\n", generations);
 196   return 0;
 197 }