2018/day6.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
   8 void debug(const char *fmt, ...) {
   9   va_list ap;
  10   if (getenv("DEBUG")) {
  11     va_start(ap, fmt);
  12     vfprintf(stderr, fmt, ap);
  13     va_end(ap);
  14   }
  15 }
  16
  17 #define LIMIT 1000
  18 #define LINES 60
  19
  20 static struct data {
  21   unsigned char line; /* non-zero only for coordinates in list */
  22   unsigned char nearby; /* 0 for unchecked or tie, else line id of nearest */
  23 } array[LIMIT][LIMIT];
  24 static struct line {
  25   unsigned short x;
  26   unsigned short y;
  27   bool edge;
  28   unsigned short count;
  29 } list[LINES]; /* line 0 unused */
  30 static unsigned short minx = LIMIT, miny = LIMIT, maxx = 0, maxy = 0;
  31
  32 /* Return 0 to keep looking, non-zero for tie */
  33 static int check(int x, int y, int *r) {
  34   if (x < minx || x > maxx || y < miny || y > maxy)
  35     return 0;
  36   if (array[x][y].line) {
  37     if (*r) {
  38       debug("point %d,%d has at least two nearest neighbors\n", x, y);
  39       return 1;
  40     }
  41     *r = array[x][y].line;
  42   }
  43   return 0;
  44 }
  45
  46 /* Return 0 for tie, else line of nearest coordinate */
  47 static unsigned char compute(int x, int y) {
  48   int d = 1, i;
  49   int r = 0;
  50   if (array[x][y].line)
  51     return array[x][y].line;
  52   while (true) {
  53     int tryx = x + d;
  54     int tryy = y;
  55     r = 0;
  56     for (i = 0; i < d; i++) {
  57       if (check(tryx, tryy, &r))
  58         return 0;
  59       tryx--;
  60       tryy++;
  61     }
  62     for (i = 0; i < d; i++) {
  63       if (check(tryx, tryy, &r))
  64         return 0;
  65       tryx--;
  66       tryy--;
  67     }
  68     for (i = 0; i < d; i++) {
  69       if (check(tryx, tryy, &r))
  70         return 0;
  71       tryx++;
  72       tryy--;
  73     }
  74     for (i = 0; i < d; i++) {
  75       if (check(tryx, tryy, &r))
  76         return 0;
  77       tryx++;
  78       tryy++;
  79     }
  80     if (r)
  81       return r;
  82     debug("no neighbors of %d,%d within %d\n", x, y, d);
  83     d++;
  84   }
  85 }
  86
  87 int main(int argc, char **argv) {
  88   size_t len = 0, count = 0;
  89   char *line;
  90   int i, j;
  91   int x, y;
  92
  93   /* Part 1 - read in lines */
  94   if (argc > 1)
  95     if (!(stdin = freopen(argv[1], "r", stdin))) {
  96       perror("failure");
  97       exit(2);
  98     }
  99
 100   while (getline(&line, &len, stdin) >= 0) {
 101     ++count;
 102     if (count >= LINES) {
 103       fprintf(stderr, "recompile with larger LINES!\n");
 104       exit(1);
 105     }
 106     if (sscanf(line, "%d, %d ", &x, &y) != 2) {
 107       fprintf(stderr, "bad input\n");
 108       exit(1);
 109     }
 110     if (x > LIMIT || y > LIMIT) {
 111       fprintf(stderr, "recompile with larger LIMIT!\n");
 112       exit(1);
 113     }
 114     list[count].x = x;
 115     list[count].y = y;
 116     array[x][y].line = count;
 117     if (x > maxx)
 118       maxx = x;
 119     if (x < minx)
 120       minx = x;
 121     if (y > maxy)
 122       maxy = y;
 123     if (y < miny)
 124       miny = y;
 125   }
 126   printf("Read %zu lines, bounding box %d,%d to %d,%d\n", count,
 127          minx, miny, maxx, maxy);
 128   minx--;
 129   miny--;
 130   maxx++;
 131   maxy++;
 132
 133   /* Part 2 - compute nearest neighbors */
 134   for (j = miny; j <= maxy; j++)
 135     for (i = minx; i <= maxx; i++) {
 136       unsigned char nearest = compute(i, j);
 137       if (nearest) {
 138         array[i][j].nearby = nearest;
 139         list[nearest].count++;
 140         if (i == minx || i == maxx || j == miny || j == maxy)
 141           list[nearest].edge = true;
 142       }
 143     }
 144
 145   /* Part 3 - determine non-edge point with most neighbors */
 146   int best = 0;
 147   for (i = 1; i <= count; i++) {
 148     debug("point %d,%d has %d neighbors\n", list[i].x, list[i].y,
 149           list[i].count);
 150     if (list[i].edge)
 151       continue;
 152     if (list[i].count > list[best].count)
 153       best = i;
 154   }
 155   printf("best point %d,%d has %d neighbors\n", list[best].x, list[best].y,
 156          list[best].count);
 157
 158   /* Part 4 - determine number of points within 10000 of all list members */
 159   int good = 0;
 160   for (j = miny; j <= maxy; j++)
 161     for (i = minx; i <= maxx; i++) {
 162       int sum = 0;
 163       for (x = 1; x <= count; x++)
 164         sum += abs(i - list[x].x) + abs(j - list[x].y);
 165       debug("point %d,%d sum %d\n", i, j, sum);
 166       if (sum < 10000)
 167         good++;
 168     }
 169   printf("found %d points within 10000\n", good);
 170   return 0;
 171 }