2019/day12.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 <stdint.h>
   8 #include <inttypes.h>
   9
  10 static int debug_level = -1;
  11 static void __attribute__((unused))
  12 debug_raw(int level, const char *fmt, ...) {
  13   va_list ap;
  14   if (debug_level < 0)
  15     debug_level = atoi(getenv("DEBUG") ?: "0");
  16   if (debug_level >= level) {
  17     va_start(ap, fmt);
  18     vfprintf(stderr, fmt, ap);
  19     va_end(ap);
  20   }
  21 }
  22 #define debug(...) debug_raw(1, __VA_ARGS__)
  23
  24 struct point {
  25   int px, py, pz;
  26   int vx, vy, vz;
  27 };
  28 static struct point a[4], orig[4];
  29 static int perx, pery, perz;
  30
  31 static void
  32 dump(int step) {
  33   int i;
  34
  35   printf("After %d steps:\n", step);
  36   for (i = 0; i < 4; i++)
  37     printf("pos=<x=%3d, y=%3d, z=%3d>, vel=<x=%3d, y=%3d, z=%3d>\n",
  38            a[i].px, a[i].py, a[i].pz, a[i].vx, a[i].vy, a[i].vz);
  39 }
  40
  41 static void
  42 gravity_one(int one, int two) {
  43   if (a[one].px < a[two].px) {
  44     a[one].vx++;
  45     a[two].vx--;
  46   } else if (a[one].px > a[two].px) {
  47     a[one].vx--;
  48     a[two].vx++;
  49   }
  50   if (a[one].py < a[two].py) {
  51     a[one].vy++;
  52     a[two].vy--;
  53   } else if (a[one].py > a[two].py) {
  54     a[one].vy--;
  55     a[two].vy++;
  56   }
  57   if (a[one].pz < a[two].pz) {
  58     a[one].vz++;
  59     a[two].vz--;
  60   } else if (a[one].pz > a[two].pz) {
  61     a[one].vz--;
  62     a[two].vz++;
  63   }
  64 }
  65
  66 static void
  67 gravity(void) {
  68   gravity_one(0, 1);
  69   gravity_one(0, 2);
  70   gravity_one(0, 3);
  71   gravity_one(1, 2);
  72   gravity_one(1, 3);
  73   gravity_one(2, 3);
  74 }
  75
  76 static void
  77 velocity(void) {
  78   int i;
  79
  80   for (i = 0; i < 4; i++) {
  81     a[i].px += a[i].vx;
  82     a[i].py += a[i].vy;
  83     a[i].pz += a[i].vz;
  84   }
  85 }
  86
  87 static void
  88 energy(int i) {
  89   int t = 0;
  90
  91   printf("after %d steps, ", i);
  92   for (i = 0; i < 4; i++)
  93     t += (abs(a[i].px) + abs(a[i].py) + abs(a[i].pz)) *
  94       (abs(a[i].vx) + abs(a[i].vy) + abs(a[i].vz));
  95   printf("energy is %d\n", t);
  96 }
  97
  98 static struct collision {
  99   int x;
 100   int px;
 101   int nx;
 102   int y;
 103   int py;
 104   int ny;
 105   int z;
 106   int pz;
 107   int nz;
 108 } collide[6];
 109
 110 static void check_collide(struct point *p1, struct point *p2,
 111                           struct collision *c, int i) {
 112   if (!perx && p1->px == p2->px && i % 6 == 5) {
 113     if (c->x)
 114       c->nx++;
 115     else {
 116       c->x = i;
 117       c->px = p1->px;
 118     }
 119   }
 120   if (!pery && p1->py == p2->py && i % 6 == 5) {
 121     if (c->y)
 122       c->ny++;
 123     else {
 124       c->y = i;
 125       c->py = p1->py;
 126     }
 127   }
 128   if (!perz && p1->pz == p2->pz && i % 6 == 5) {
 129     if (c->z)
 130       c->nz++;
 131     else {
 132       c->z = i;
 133       c->pz = p1->pz;
 134     }
 135   }
 136   if (p1->px == p2->px && p1->py == p2->py && p1->pz == p2->pz) {
 137     printf("collision occurred!");
 138     exit(1);
 139   }
 140 }
 141
 142 static bool
 143 check(int i) {
 144   check_collide(&a[0], &a[1], &collide[0], i);
 145   check_collide(&a[0], &a[2], &collide[1], i);
 146   check_collide(&a[0], &a[3], &collide[2], i);
 147   check_collide(&a[1], &a[2], &collide[3], i);
 148   check_collide(&a[1], &a[3], &collide[4], i);
 149   check_collide(&a[2], &a[3], &collide[5], i);
 150   if (!perx && !(a[0].vx | a[1].vx | a[2].vx | a[3].vx) &&
 151       a[0].px == orig[0].px && a[1].px == orig[1].px &&
 152       a[2].px == orig[2].px && a[3].px == orig[3].px) {
 153     perx = i;
 154   }
 155   if (!pery && !(a[0].vy | a[1].vy | a[2].vy | a[3].vy) &&
 156       a[0].py == orig[0].py && a[1].py == orig[1].py &&
 157       a[2].py == orig[2].py && a[3].py == orig[3].py) {
 158     pery = i;
 159   }
 160   if (!perz && !(a[0].vz | a[1].vz | a[2].vz | a[3].vz) &&
 161       a[0].pz == orig[0].pz && a[1].pz == orig[1].pz &&
 162       a[2].pz == orig[2].pz && a[3].pz == orig[3].pz) {
 163     perz = i;
 164   }
 165   return perx && pery && perz;
 166 }
 167
 168 static long long
 169 gcd(long long one, long long two) {
 170   if (one == two)
 171     return one;
 172   if (one > two)
 173     return gcd(one - two, two);
 174   return gcd(one, two - one);
 175 }
 176
 177 int main(int argc, char **argv) {
 178   int i, limit = 1000000, progress;
 179
 180   debug("");
 181   if (argc > 1 && strcmp(argv[1], "-"))
 182     if (!(stdin = freopen(argv[1], "r", stdin))) {
 183       perror("failure");
 184       exit(2);
 185     }
 186
 187   if (argc > 2)
 188     limit = atoi(argv[2]);
 189   if (argc > 3)
 190     progress = atoi(argv[3]);
 191   else
 192     progress = limit / 10;
 193
 194   for (i = 0; i < 4; i++)
 195     if (scanf("<x=%d, y=%d, z=%d>\n", &a[i].px, &a[i].py, &a[i].pz) != 3) {
 196       printf("unexpected input\n");
 197       exit(2);
 198     }
 199   memcpy(orig, a, sizeof a);
 200   for (i = 0; i < limit; i++) {
 201     if (argc > 2) {
 202       if (!(i % progress))
 203         dump(i);
 204     } else if (i == 1000)
 205       energy(i);
 206     if (i && check(i))
 207       break;
 208     gravity();
 209     velocity();
 210   }
 211   if (argc > 2) {
 212     dump(i);
 213     energy(i);
 214   }
 215   if (perx && pery && perz) {
 216     long long tmp;
 217     printf("cycles at %d %d %d\n", perx, pery, perz);
 218     tmp = perx / gcd(perx, pery) * pery;
 219     printf("overall at %lld\n", tmp / gcd(tmp, perz) * perz);
 220   } else
 221     printf("must run longer to find cycles\n");
 222
 223   for (i = 0; i < 6; i++)
 224     if (collide[i].x && collide[i].y && collide[i].z)
 225       debug("potential collision in pair %d? %d(+%d)@%d, %d(+%d)@%d, "
 226             "%d(+%d)@%d\n", i,
 227             collide[i].x, collide[i].nx, collide[i].px,
 228             collide[i].y, collide[i].ny, collide[i].py,
 229             collide[i].z, collide[i].nz, collide[i].pz);
 230   return 0;
 231 }