diff options
| -rw-r--r-- | 15.c | 138 | ||||
| -rw-r--r-- | makefile | 1 |
2 files changed, 139 insertions, 0 deletions
@@ -0,0 +1,138 @@ + +#include <limits.h> +#include <regex.h> +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> + + +#define arrlen(x) (sizeof(x)/sizeof((x)[0])) + +#define min(x, y) ((x) < (y) ? (x) : (y)) + +#define max(x, y) ((x) > (y) ? (x) : (y)) + + +struct sensor { + long x; + long y; + long beaconx; + long beacony; +}; + + +long +sensor_distance(struct sensor const * s, long x, long y) +{ + return labs(s->x - x) + labs(s->y - y); +} + + +long +sensor_zone(struct sensor const * s) +{ + return sensor_distance(s, s->beaconx, s->beacony); +} + + +int +sensor_isbeacon(struct sensor const * s, long x, long y) +{ + return x == s->beaconx && y == s->beacony; +} + + +int +main(int argc, char ** argv) +{ + regex_t coords; + char buf[BUFSIZ]; + struct sensor * sensors = NULL, * s; + int nsensors = 0, i; + long xmin, xmax, ymin, ymax, zone; + long x, y = LONG_MIN, empty = 0; + + while ((i = getopt(argc, argv, "y:")) != -1) { + switch (i) { + case 'y': + y = atol(optarg); + break; + + default: + return -1; + } + } + + if (y == LONG_MIN) { + fprintf(stderr, "Required option: y\n"); + return -1; + } + + if (regcomp(&coords, "Sensor at x=(-?[[:digit:]]+), y=(-?[[:digit:]]+):" + " closest beacon is at x=(-?[[:digit:]]+), y=(-?[[:digit:]]+)", + REG_EXTENDED) != 0) + { + fprintf(stderr, "Bad regex\n"); + return -1; + } + + // Read the sensors and their beacons + while (fgets(buf, sizeof(buf), stdin)) { + regmatch_t xy[5]; + void * p; + + if (regexec(&coords, buf, arrlen(xy), xy, 0) != 0) { + fprintf(stderr, "No coords found in %s\n", buf); + free(sensors); + regfree(&coords); + return -1; + } + if ((p = realloc(sensors, ++nsensors * sizeof(struct sensor))) == NULL) { + fprintf(stderr, "Bad realloc(%zd)\n", nsensors * sizeof(struct sensor)); + free(sensors); + regfree(&coords); + return -1; + } + sensors = p; + sensors[nsensors - 1].x = atol(buf + xy[1].rm_so); + sensors[nsensors - 1].y = atol(buf + xy[2].rm_so); + sensors[nsensors - 1].beaconx = atol(buf + xy[3].rm_so); + sensors[nsensors - 1].beacony = atol(buf + xy[4].rm_so); + } + + // Calculate max bounds for sensors/beacons + s = sensors; + zone = sensor_zone(s); + xmin = s->x - zone; + xmax = s->x + zone; + ymin = s->y - zone; + ymax = s->y + zone; + for (s = sensors + 1; s < sensors + nsensors; ++s) { + zone = sensor_zone(s); + xmin = min(xmin, s->x - zone); + xmax = max(xmax, s->x + zone); + ymin = min(ymin, s->y - zone); + ymax = max(ymax, s->y + zone); + } + + // Check for spots without beacons + for (x = xmin; x <= xmax; ++x) { + for (s = sensors; s < sensors + nsensors; ++s) { + if (sensor_distance(s, x, y) <= sensor_zone(s) + && !sensor_isbeacon(s, x, y)) + { + break; + } + } + if (s < sensors + nsensors) + ++empty; + } + + printf("Positions without a beacon on row %ld: %ld\n", y, empty); + + free(sensors); + regfree(&coords); + + return 0; +} + @@ -16,6 +16,7 @@ all: bin \ bin/12 \ bin/13 \ bin/14 \ + bin/15 \ bin: mkdir -p $@ |