2016/advent22.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include <assert.h>
   7 #include <stdbool.h>
   8
   9 #define ROWS 29 // cheat by pre-inspecting input file
  10 #define COLS 35
  11 typedef struct node node;
  12 struct node {
  13   int size;
  14   int used;
  15   int avail;
  16 };
  17 node grid[ROWS][COLS];
  18
  19 static void
  20 move(int x1, int y1, int x2, int y2)
  21 {
  22   printf ("moving data from %d-%d to %d-%d\n", x2, y2, x1, y1);
  23   grid[y1][x1].used += grid[y2][x2].used;
  24   assert (grid[y1][x1].used <= grid[y1][x1].size);
  25   grid[y1][x1].avail -= grid[y2][x2].used;
  26   grid[y2][x2].avail += grid[y2][x2].avail;
  27   grid[y2][x2].used = 0;
  28 }
  29
  30 int main(int argc, char **argv)
  31 {
  32   ssize_t nread;
  33   size_t len = 0;
  34   char *line = NULL;
  35   int maxx = 0, maxy = 0;
  36   while ((nread = getline(&line, &len, stdin)) >= 0) {
  37     if (*line != '/')
  38       continue;
  39     int x, y, s, u, a;
  40     if (sscanf (line, "/dev/grid/node-x%d-y%d %dT %dT %dT", &x, &y, &s, &u,
  41                 &a) != 5)
  42       assert (false);
  43     if (x >= maxx)
  44       maxx = x + 1;
  45     if (y >= maxy)
  46       maxy = y + 1;
  47     grid[y][x].size = s;
  48     grid[y][x].used = u;
  49     grid[y][x].avail = a;
  50   }
  51   printf ("parsed %d columns over %d rows, for %d out of %d grid spots\n",
  52           maxx, maxy, maxx * maxy, ROWS * COLS);
  53   int startx = -1, starty = -1;
  54   int viable = 0;
  55   int x, y;
  56   for (y = 0; y < maxy; y++)
  57     for (x = 0; x < maxx; x++)
  58       for (int i = 0; i < maxy; i++)
  59         for (int j = 0; j < maxx; j++) {
  60           if (x == j && y == i)
  61             continue;
  62           if (!grid[y][x].used)
  63             continue;
  64           if (grid[y][x].used < grid[i][j].avail) {
  65             viable++;
  66             if (startx < 1) {
  67               startx = j;
  68               starty = i;
  69             }
  70           }
  71         }
  72   printf ("found %d viable pairs, all leading to %d-%d\n", viable,
  73           startx, starty);
  74   int steps = 0;
  75   x = startx;
  76   y = starty;
  77   // I really don't feel like coding up an exploratory forking algorithm;
  78   // pre-inspecting the data shows a brick wall from 24-9 through 34-9.
  79   // Route around it by getting x to 23 before moving y to 0
  80   while (x > 23) {
  81     steps++;
  82     move (x, y, x - 1, y);
  83     x--;
  84   }
  85   while (y) {
  86     steps++;
  87     move (x, y, x, y - 1);
  88     y--;
  89   }
  90   while (x < maxx - 1) {
  91     steps++;
  92     move (x, y, x + 1, y);
  93     x++;
  94   }
  95   while (x > 1) {
  96     steps += 5;
  97     move (x, y, x, y + 1);
  98     y++;
  99     move (x, y, x - 1, y);
 100     x--;
 101     move (x, y, x - 1, y);
 102     x--;
 103     move (x, y, x, y - 1);
 104     y--;
 105     move (x, y, x + 1, y);
 106     x++;
 107   }
 108   printf ("total steps: %d\n", steps);
 109   return 0;
 110 }