#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;
}