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


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 = LONG_MIN, xmax = LONG_MAX, ymin = LONG_MIN, ymax = LONG_MAX, zone;
	long x, y = LONG_MIN, empty = 0;

	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;

		default:
			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)) {
		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);
	}

	// 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 = 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);
		}

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

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

		// 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);

	return 0;
}