2019/day10.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 #define LIMIT 21
  25 struct point {
  26   bool asteroid;
  27   int blocked;
  28 };
  29 static struct point grid[LIMIT][LIMIT];
  30 static size_t bound;
  31 struct info {
  32   int level;
  33   float slope;
  34   int coord;
  35 };
  36 static struct info list[LIMIT * LIMIT];
  37 static int next;
  38
  39 static bool
  40 check_one (int to, int from_x, int from_y) {
  41   int to_x = to % bound, to_y = to / bound;
  42   int dx = to_x - from_x, dy = to_y - from_y;
  43   int from = from_y * bound + from_x;
  44   bool result = false;
  45
  46   debug_raw(2, " checking %d.%d, slope %d/%d", to_x, to_y, dy, dx);
  47   if (grid[to_y][to_x].blocked == from) {
  48     debug_raw(2, " already visited\n");
  49     return false;
  50   }
  51   do {
  52     if (grid[to_y][to_x].asteroid)
  53       result = true;
  54     grid[to_y][to_x].blocked = from;
  55     debug_raw(2, " [visiting %d.%d]", to_x, to_y);
  56     to_x += dx;
  57     to_y += dy;
  58   } while (to_x >= 0 && to_x < bound && to_y >= 0 && to_y < bound);
  59   debug_raw(2, " %s\n", result ? "hit" : "clear");
  60   return result;
  61 }
  62
  63 static int
  64 check(int point) {
  65   int x = point % bound, y = point / bound;
  66   int i, total = 0;
  67
  68   debug_raw(2, "checking %d=%d.%d %c\n", point, x, y,
  69             grid[y][x].asteroid ? '#' : '.');
  70   if (!grid[y][x].asteroid)
  71     return 0;
  72   for (i = point - 1; i >= 0; i--)
  73     if (check_one(i, x, y))
  74       total++;
  75   for (i = point + 1; i < bound * bound; i++)
  76     if (check_one(i, x, y))
  77       total++;
  78   debug_raw(2, "hit %d\n", total);
  79   return total;
  80 }
  81
  82 static void
  83 prep_one (int to, int from_x, int from_y) {
  84   int to_x = to % bound, to_y = to / bound;
  85   int dx = to_x - from_x, dy = to_y - from_y;
  86   int from = from_y * bound + from_x;
  87   float slope = (float)-dy / dx;
  88   int level = 1;
  89
  90   debug(" prepping %d.%d, slope %d/%d=%g", to_x, to_y, dy, dx, slope);
  91   if (grid[to_y][to_x].blocked == -from) {
  92     debug(" already visited\n");
  93     return;
  94   }
  95   do {
  96     if (grid[to_y][to_x].asteroid) {
  97       list[next].level = level + (dx < 0);
  98       list[next].slope = slope;
  99       list[next++].coord = to_x * 100 + to_y;
 100       level += 2;
 101     }
 102     grid[to_y][to_x].blocked = -from;
 103     debug(" [visiting %d.%d]", to_x, to_y);
 104     to_x += dx;
 105     to_y += dy;
 106   } while (to_x >= 0 && to_x < bound && to_y >= 0 && to_y < bound);
 107   debug(" %d prepped\n", next);
 108 }
 109
 110 static void
 111 prep(int point) {
 112   int x = point % bound, y = point / bound;
 113   int i;
 114
 115   list[next].level = 0;
 116   list[next].slope = 0;
 117   list[next++].coord = x * 10 + y;
 118   for (i = point - 1; i >= 0; i--)
 119     prep_one(i, x, y);
 120   for (i = point + 1; i < bound * bound; i++)
 121     prep_one(i, x, y);
 122 }
 123
 124 static int
 125 comp(const void *pa, const void *pb) {
 126   const struct info *a = pa, *b = pb;
 127   if (a->level < b->level)
 128     return -1;
 129   if (a->level > b->level)
 130     return 1;
 131   if (a->slope > b->slope)
 132     return -1;
 133   if (a->slope < b->slope)
 134     return 1;
 135   printf("unexpected equality for coord %d and %d\n", a->coord, b->coord);
 136   exit(1);
 137 }
 138
 139 int main(int argc, char **argv) {
 140   size_t len = 0, count = 0, asteroids = 0, total = 0;
 141   int i, best_i = 0, best_t;
 142   char *line;
 143
 144   debug("");
 145   if (argc > 1)
 146     if (!(stdin = freopen(argv[1], "r", stdin))) {
 147       perror("failure");
 148       exit(2);
 149     }
 150
 151   while ((i = getline(&line, &len, stdin)) >= 0) {
 152     if (bound == 0)
 153       bound = i - 1;
 154     else if (bound != i - 1) {
 155       printf("input not a square: column\n");
 156       exit(2);
 157     }
 158     for (i = 0; i < bound; i++)
 159       if (line[i] == '#') {
 160         grid[count][i].asteroid = true;
 161         asteroids++;
 162       }
 163     count++;
 164   }
 165   if (count != bound) {
 166     printf("input not a square: row\n");
 167     exit(2);
 168   }
 169   printf("Read %zu lines, %zd asteroids\n", count, asteroids);
 170
 171   for (i = 0; i < bound * bound; i++) {
 172     total = check(i);
 173     if (total > best_t) {
 174       best_t = total;
 175       best_i = i;
 176     }
 177   }
 178   printf("Best %d at %zd.%zd\n", best_t, best_i % bound, best_i / bound);
 179
 180   prep(best_i);
 181   qsort(list, asteroids, sizeof list[0], comp);
 182   for (i = 0; i < asteroids; i++)
 183     debug("list[%d] = %d %g %d\n", i, list[i].level, list[i].slope,
 184           list[i].coord);
 185   if (asteroids > 200)
 186     printf("200th vaporized at %d\n", list[200].coord);
 187   return 0;
 188 }