2017/advent24.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 #include <assert.h>
   9
  10 #define MAX 60 // pre-inspect input
  11 typedef struct pair pair;
  12 static struct pair {
  13   int a;
  14   int b;
  15 } pairs[MAX];
  16 static int npairs;
  17 static int chains;
  18 static int max_d;
  19 static int max;
  20
  21 void
  22 visit (int depth, int sum, int current, unsigned long long remaining)
  23 {
  24   bool found = false;
  25   printf ("%d, %d, %d, %llx\n", depth, sum, current, remaining);
  26   for (int i = 0; i < 64; i++)
  27     if (remaining & (1ULL << i)) {
  28       if (pairs[i].a == current) {
  29         found = true;
  30         visit (depth + 1, sum + pairs[i].a + pairs[i].b, pairs[i].b,
  31                remaining & ~(1ULL << i));
  32       } else if (pairs[i].b == current) {
  33         found = true;
  34         visit (depth + 1, sum + pairs[i].a + pairs[i].b, pairs[i].a,
  35                remaining & ~(1ULL << i));
  36       }
  37     }
  38   if (!found) {
  39     chains++;
  40     if (depth > max_d) {
  41       max_d = depth;
  42       max = 0;
  43     }
  44     if (depth == max_d && sum > max)
  45       max = sum;
  46   }
  47 }
  48
  49 int main(int argc, char **argv)
  50 {
  51   while (scanf ("%d/%d\n", &pairs[npairs].a, &pairs[npairs].b) == 2)
  52     npairs++;
  53   assert(npairs < MAX);
  54   visit (0, 0, 0, (1ULL << npairs) - 1);
  55   printf ("found %d chains, max %d\n", chains, max);
  56   return 0;
  57 }