2018/day23.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <stdarg.h>
   6 #include <stdbool.h>
   7 #include <inttypes.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10
  11 bool __attribute__((format(printf, 1, 2)))
  12 debug(const char *fmt, ...) {
  13   va_list ap;
  14   if (getenv("DEBUG")) {
  15     va_start(ap, fmt);
  16     vfprintf(stderr, fmt, ap);
  17     va_end(ap);
  18     return true;
  19   }
  20   return false;
  21 }
  22
  23 #define LIMIT 1000
  24
  25 static struct data {
  26   int x;
  27   int y;
  28   int z;
  29   int r;
  30 } array[LIMIT];
  31
  32 static int near[3][3][3];
  33
  34 static bool inrange(int minx, int miny, int minz, int step, struct data *d) {
  35   int dx, dy, dz;
  36   minx -= step / 2;
  37   miny -= step / 2;
  38   minz -= step / 2;
  39   if (0 && d == &array[0])
  40     debug(" inrange(%d,%d,%d - %d,%d,%d)\n",
  41         minx, miny, minz, minx + step, miny + step, minz + step);
  42   if (d->x >= minx && d->x <= minx + step) {
  43     if (d->y >= miny && d->y <= miny + step) {
  44       if (d->z >= minz && d->z <= minz + step) {
  45         // x,y,z
  46         return true;
  47       } else {
  48         // x,y but not z
  49         dz = abs((d->z < minz ? minz : minz + step) - d->z);
  50         return dz <= d->r;
  51       }
  52     } else {
  53       if (d->z >= minz && d->z <= minz + step) {
  54         // x,z but not y
  55         dy = abs((d->y < miny ? miny : miny + step) - d->y);
  56         return dy <= d->r;
  57       } else {
  58         // x but not y,z
  59         dy = abs((d->y < miny ? miny : miny + step) - d->y);
  60         dz = abs((d->z < minz ? minz : minz + step) - d->z);
  61         return dy + dz <= d->r;
  62       }
  63     }
  64   } else {
  65     if (d->y >= miny && d->y <= miny + step) {
  66       if (d->z >= minz && d->z <= minz + step) {
  67         // y,z but not x
  68         dx = abs((d->x < minx ? minx : minx + step) - d->x);
  69         return dx <= d->r;
  70       } else {
  71         // y but not x,z
  72         dx = abs((d->x < minx ? minx : minx + step) - d->x);
  73         dz = abs((d->z < minz ? minz : minz + step) - d->z);
  74         return dx + dz <= d->r;
  75       }
  76     } else {
  77       if (d->z >= minz && d->z <= minz + step) {
  78         // z but not x,y
  79         dx = abs((d->x < minx ? minx : minx + step) - d->x);
  80         dy = abs((d->y < miny ? miny : miny + step) - d->y);
  81         return dx + dy <= d->r;
  82       } else {
  83         // not x,y,z
  84         dx = abs((d->x < minx ? minx : minx + step) - d->x);
  85         dy = abs((d->y < miny ? miny : miny + step) - d->y);
  86         dz = abs((d->z < minz ? minz : minz + step) - d->z);
  87         return dx + dy + dz <= d->r;
  88       }
  89     }
  90   }
  91 }
  92
  93 static bool closer(int x1, int y1, int z1, int x2, int y2, int z2, int step) {
  94   int d = step / 2;
  95   return abs(x1 + d) + abs(y1 + d) + abs(z1 + d)
  96     > abs(x2 + d) + abs(y2 + d) + abs(z2 + d);
  97 }
  98
  99 static bool search(int count, int *x, int *y, int *z, int step, int *found) {
 100   int i, j, k, l;
 101   struct data best = {0};
 102   bool move;
 103   memset(near, 0, sizeof near);
 104   for (i = 0; i <= 2; i++)
 105     for (j = 0; j <= 2; j++)
 106       for (k = 0; k <= 2; k++) {
 107         int tryx = step > 1 ? *x + step / 2 * (i - 1) : *x + i - 1;
 108         int tryy = step > 1 ? *y + step / 2 * (j - 1) : *y + j - 1;
 109         int tryz = step > 1 ? *z + step / 2 * (k - 1) : *z + k - 1;
 110         for (l = 0; l < count; l++)
 111           if (inrange(tryx, tryy, tryz, step, &array[l]))
 112             near[i][j][k]++;
 113         if (near[i][j][k] > best.r
 114             || (near[i][j][k] == best.r
 115                 && closer(best.x, best.y, best.z, tryx, tryy, tryz, step))) {
 116           best.x = tryx;
 117           best.y = tryy;
 118           best.z = tryz;
 119           best.r = near[i][j][k];
 120           move = i != 1 || j != 1 || k != 1;
 121         }
 122       }
 123   if (debug("after search %d,%d,%d step %d:\n", *x, *y, *z, step)) {
 124     for (j = 0; j <= 2; j++)
 125       debug("%5d %5d %5d   %5d %5d %5d   %5d %5d %5d\n",
 126             near[0][j][0], near[1][j][0], near[2][j][0],
 127             near[0][j][1], near[1][j][1], near[2][j][1],
 128             near[0][j][2], near[1][j][2], near[2][j][2]);
 129     debug("best %d at %d,%d,%d, move %d, next step %d\n", best.r, best.x,
 130           best.y, best.z, move, move ? step : step / 2);
 131   }
 132   *x = best.x;
 133   *y = best.y;
 134   *z = best.z;
 135   *found = best.r;
 136   return move;
 137 }
 138
 139 int main(int argc, char **argv) {
 140   size_t len = 0, count = 0;
 141   char *line;
 142   int best = 0;
 143   int i;
 144   int nearby = 0;
 145   int x = 0, y = 0, z = 0;
 146   int step = -1;
 147   int iter = 0;
 148
 149   /* Part 1 - read data */
 150   if (argc > 5)
 151     step = atoi(argv[5]);
 152   if (argc > 4) {
 153     x = atoi(argv[2]);
 154     y = atoi(argv[3]);
 155     z = atoi(argv[4]);
 156   }
 157   if (argc > 1)
 158     if (!(stdin = freopen(argv[1], "r", stdin))) {
 159       perror("failure");
 160       exit(2);
 161     }
 162
 163   while (getline(&line, &len, stdin) >= 0) {
 164     if (count >= LIMIT) {
 165       fprintf(stderr, "recompile with larger LIMIT!\n");
 166       exit(1);
 167     }
 168     if (sscanf(line, "pos=<%d,%d,%d>, r=%d\n", &array[count].x,
 169                &array[count].y, &array[count].z, &array[count].r) != 4) {
 170       fprintf(stderr, "bad input\n");
 171       exit(1);
 172     }
 173     if (array[count].r > array[best].r)
 174       best = count;
 175     ++count;
 176   }
 177   printf("Read %zu lines, largest r %d at %d,%d,%d\n", count, array[best].r,
 178          array[best].x, array[best].y, array[best].z);
 179
 180   for (i = 0; i < count; i++)
 181     if (abs(array[i].x - array[best].x) + abs(array[i].y - array[best].y)
 182         + abs(array[i].z - array[best].z) <= array[best].r)
 183       nearby++;
 184   printf("Found %d nodes within range of %d,%d,%d\n", nearby,
 185          array[best].x, array[best].y, array[best].z);
 186   if (step < 0)
 187     step = 1 << (32 - __builtin_clz(array[best].r));
 188   printf("Beginning search at %d,%d,%d with step of %d\n", x, y, z, step);
 189
 190   /* Part 2 - find best spot */
 191   while (step) {
 192     if (!(iter % 1000) || step < 2)
 193       printf("%d iterations, currently at %d,%d,%d nearby %d step %d\n",
 194              iter, x, y, z, nearby, step);
 195     iter++;
 196     if (!search(count, &x, &y, &z, step, &nearby))
 197       step = step * 3 / 4;
 198   }
 199   while (search(count, &x, &y, &z, step, &nearby)) {
 200     iter++;
 201     printf("%d iterations, currently at %d,%d,%d nearby %d step %d\n",
 202            iter, x, y, z, nearby, step);
 203   }
 204   printf("After %d iterations, best is %d,%d,%d with %d nearby, or %d\n",
 205          iter, x, y, z, nearby, abs(x) + abs(y) + abs(z));
 206   return 0;
 207 }