diff options
Diffstat (limited to '15.c')
| -rw-r--r-- | 15.c | 134 |
1 files changed, 103 insertions, 31 deletions
@@ -42,18 +42,51 @@ sensor_isbeacon(struct sensor const * s, long x, long y) } +long +beacon_frequency(long x, long y) +{ + return x * 4000000 + y; +} + + int main(int argc, char ** argv) { + int part = 1; regex_t coords; + regmatch_t xy[5]; char buf[BUFSIZ]; struct sensor * sensors = NULL, * s; int nsensors = 0, i; - long xmin, xmax, ymin, ymax, zone; + long xmin = LONG_MIN, xmax = LONG_MAX, ymin = LONG_MIN, ymax = LONG_MAX, zone; long x, y = LONG_MIN, empty = 0; - while ((i = getopt(argc, argv, "y:")) != -1) { + while ((i = getopt(argc, argv, "p:l:y:")) != -1) { switch (i) { + case 'p': + part = atoi(optarg); + break; + + case 'l': + if (regcomp(&coords, "(-?[[:digit:]]+),(-?[[:digit:]]+)" + ":(-?[[:digit:]]+),(-?[[:digit:]]+)", + REG_EXTENDED) != 0) + { + fprintf(stderr, "Bad regex\n"); + return -1; + } + if (regexec(&coords, optarg, arrlen(xy), xy, 0) != 0) { + fprintf(stderr, "Bad limit: \"-l x,y:x,y\"\n"); + regfree(&coords); + return -1; + } + xmin = atol(optarg + xy[1].rm_so); + ymin = atol(optarg + xy[2].rm_so); + xmax = atol(optarg + xy[3].rm_so); + ymax = atol(optarg + xy[4].rm_so); + regfree(&coords); + break; + case 'y': y = atol(optarg); break; @@ -63,11 +96,6 @@ main(int argc, char ** argv) } } - 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) @@ -78,7 +106,6 @@ main(int argc, char ** argv) // 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) { @@ -100,35 +127,80 @@ main(int argc, char ** argv) 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) { + // Check for spots without beacons + if (part == 1) { + if (y == LONG_MIN) { + fprintf(stderr, "Required option (row): \"-y row\"\n"); + free(sensors); + regfree(&coords); + return -1; + } + + // Calculate max bounds for sensors/beacons + s = sensors; 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); - } + 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; + // Count positions that cannot be 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; } - if (s < sensors + nsensors) - ++empty; + + printf("Positions without a beacon on row %ld: %ld\n", y, empty); } + else if (part == 2) { + if (ymin == LONG_MIN) { + fprintf(stderr, "Required option (limit): \"-l x,y:x,y\"\n"); + free(sensors); + regfree(&coords); + return -1; + } - printf("Positions without a beacon on row %ld: %ld\n", y, empty); + // Find positions that are not in any sensor zone + for (y = ymin; y <= ymax; ++y) { + for (x = xmin; x <= xmax; ++x) { + for (s = sensors; s < sensors + nsensors; ++s) { + zone = sensor_zone(s); + if (sensor_distance(s, x, y) <= zone) + break; + } + if (s < sensors + nsensors) { + // In a zone. Skip to the end of this sensors zone on this row + long end = s->x + zone - labs(s->y - y); + if (end > x) + x = end; + } + else { + printf("Possible beacon with frequency %ld at %ld,%ld\n", + beacon_frequency(x, y), x, y); + } + } + } + } + else { + fprintf(stderr, "Unexpected part: %d\n", part); + free(sensors); + regfree(&coords); + return -1; + } free(sensors); regfree(&coords); |