From 557d12e35e3fdf7d5a3e90d3afb042606fe990aa Mon Sep 17 00:00:00 2001
From: Adam Spragg <adam@spra.gg>
Date: Thu, 15 Dec 2022 14:34:44 +0000
Subject: Solve puzzle 15 part 1

---
 15.c     | 138 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 makefile |   1 +
 2 files changed, 139 insertions(+)
 create mode 100644 15.c

diff --git a/15.c b/15.c
new file mode 100644
index 0000000..9e9f70c
--- /dev/null
+++ b/15.c
@@ -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;
+}
+
diff --git a/makefile b/makefile
index 9c956b4..ce27a0a 100644
--- a/makefile
+++ b/makefile
@@ -16,6 +16,7 @@ all: bin \
 	bin/12 \
 	bin/13 \
 	bin/14 \
+	bin/15 \
 
 bin:
 	mkdir -p $@
-- 
cgit v1.2.1