2016/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 // determined by pre-inspecting input with wc
  11 #define COLS 181
  12 #define ROWS 37
  13 #define KEYS 8
  14
  15 typedef struct point point;
  16 typedef struct key key;
  17 struct point {
  18   char c;
  19   int distance;
  20 };
  21 static point grid[ROWS][COLS];
  22 struct key {
  23   int x;
  24   int y;
  25   int d[KEYS];
  26 };
  27 static key keys[KEYS];
  28
  29 static int min = 99999999;
  30
  31 static void
  32 permute (int *a, int size, int n)
  33 {
  34   int i, t;
  35   if (size == 1) {
  36     int k = 0;
  37     int d = 0;
  38     if (getenv ("DEBUG"))
  39       printf ("path 0");
  40     for (i = 0; i < n; i++) {
  41       if (getenv ("DEBUG"))
  42         printf (" %d", a[i]);
  43       d += keys[k].d[a[i]];
  44       k = a[i];
  45     }
  46     d += keys[k].d[0];
  47     if (getenv ("DEBUG"))
  48       printf (": %d\n", d);
  49     if (d < min)
  50       min = d;
  51     return;
  52   }
  53   for (i = 0; i < size; i++) {
  54     permute (a, size - 1, n);
  55     if (size & 1) {
  56       t = a[0];
  57       a[0] = a[size - 1];
  58       a[size - 1] = t;
  59     } else {
  60       t = a[i];
  61       a[i] = a[size - 1];
  62       a[size - 1] = t;
  63     }
  64   }
  65 }
  66
  67 int main(int argc, char **argv)
  68 {
  69   int i = 0, j = 0;
  70   int c;
  71   int count = 0;
  72   while ((c = getchar ()) >= 0) {
  73     switch (c) {
  74     case '0' ... '7':
  75       keys[c - '0'].x = j;
  76       keys[c - '0'].y = i;
  77       count++;
  78       // fallthrough
  79     case '#':
  80     case '.':
  81       grid[i][j++].c = c;
  82       break;
  83     case '\n':
  84       i++;
  85       assert (j <= COLS);
  86       j = 0;
  87       break;
  88     default:
  89       assert (false);
  90     }
  91   }
  92   assert (i <= ROWS);
  93   printf ("parsed grid, found %d interesting points to visit\n", count);
  94   for (int k = 0; k < count; k++) {
  95     printf ("finding distances from key %d:", k);
  96     for (i = 0; i < ROWS; i++)
  97       for (j = 0; j < COLS; j++)
  98         grid[i][j].distance = -(grid[i][j].c == '#');
  99     grid[keys[k].y][keys[k].x].distance = 1;
 100     int found = 0;
 101     int gen = 1;
 102     while (found < count) {
 103       for (i = 0; i < ROWS; i++)
 104         for (j = 0; j < COLS; j++)
 105           if (grid[i][j].distance == gen) {
 106             if (grid[i][j].c != '.') {
 107               found++;
 108               keys[k].d[grid[i][j].c - '0'] = gen - 1;
 109             }
 110             if (!grid[i - 1][j].distance)
 111               grid[i - 1][j].distance = gen + 1;
 112             if (!grid[i + 1][j].distance)
 113               grid[i + 1][j].distance = gen + 1;
 114             if (!grid[i][j - 1].distance)
 115               grid[i][j - 1].distance = gen + 1;
 116             if (!grid[i][j + 1].distance)
 117               grid[i][j + 1].distance = gen + 1;
 118           }
 119       gen++;
 120     }
 121     for (i = 0; i < count; i++)
 122       printf ("%4d", keys[k].d[i]);
 123     printf ("\n");
 124   }
 125   int a[] = { 1, 2, 3, 4, 5, 6, 7 };
 126   permute (a, count - 1, count - 1);
 127   printf ("best case visit requires %d steps\n", min);
 128   return 0;
 129 }