Solve puzzle 18 part 2

Wow, it's hard figuring out the interior of a space. Did it the brute
force way, which worked OK because the total volume was small enough.

After part 1, I was hoping to be able to catch up the day I'm behind.
That's not happening today. We'll see how tomorrow's challenge goes.

1 files changed, 231 insertions, 69 deletions

diff --git a/18.c b/18.c
index 6d7ca6d..1e6c209 100644
--- a/18.c
+++ b/18.c
@@ -1,14 +1,19 @@
 
-//#define _GNU_SOURCE
+#define _GNU_SOURCE
 
 #include <regex.h>
 #include <search.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <unistd.h>
 
 
 #define arrlen(x) (sizeof(x)/sizeof((x)[0]))
 
+#define min(a, b) ((a) < (b) ? (a) : (b))
+
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
 
 struct point {
 	int x;
@@ -17,6 +22,49 @@ struct point {
 };
 
 
+struct point *
+point_create(int x, int y, int z)
+{
+	struct point * p;
+
+	if ((p = malloc(sizeof(struct point))) == NULL)
+		return NULL;
+
+	p->x = x;
+	p->y = y;
+	p->z = z;
+	return p;
+}
+
+
+struct point *
+point_copy(struct point * other)
+{
+	if (!other)
+		return NULL;
+	return point_create(other->x, other->y, other->z);
+}
+
+
+struct point *
+point_neighbour(struct point * dest, struct point const * src, int direction)
+{
+	if (!src)
+		return NULL;
+	*dest = *src;
+	switch (direction) {
+	case 0: ++dest->x; break;
+	case 1: --dest->x; break;
+	case 2: ++dest->y; break;
+	case 3: --dest->y; break;
+	case 4: ++dest->z; break;
+	case 5: --dest->z; break;
+	default: return NULL;
+	}
+	return dest;
+}
+
+
 int
 point_cmp(struct point const * a, struct point const * b)
 {
@@ -37,77 +85,109 @@ point_cmp_t(void const * a, void const * b)
 
 // Get one of the faces of a cube
 //
-// x = left-right
-// y = up-down
-// z = front-back
-//
 // To uniquely identify the faces of a cube, we scale the cube by a factor of
-// two, and then identify each face by the point at the face's center.
+// two, and then identify each face by a point in one direction
 struct point *
-cube_face(int x, int y, int z, int face)
+cube_face(struct point const * p, int direction)
 {
-	struct point * f;
+	struct point dbl, face;
 
-	x *= 2;
-	y *= 2;
-	z *= 2;
+	dbl.x = p->x * 2;
+	dbl.y = p->y * 2;
+	dbl.z = p->z * 2;
 
-	switch (face) {
-	case 0: // Bottom face
-		x += 1;
-		z += 1;
-		break;
+	return point_copy(point_neighbour(&face, &dbl, direction));
+}
 
-	case 1: // Top face
-		x += 1;
-		y += 2;
-		z += 1;
-		break;
 
-	case 2: // Left face
-		y += 1;
-		z += 1;
-		break;
+char *
+volpos(char * base, struct point const * p, struct point const * min, struct point const * max)
+{
+	if (p->x < min->x || p->x > max->x
+			|| p->y < min->y || p->y > max->y
+			|| p->z < min->z || p->z > max->z)
+		return NULL;
 
-	case 3: // Right face
-		x += 2;
-		y += 1;
-		z += 1;
-		break;
+	return base
+		+ (p->x - min->x) * (1 + max->y - min->y) * (1 + max->z - min->z)
+		+ (p->y - min->y) * (1 + max->z - min->z)
+		+ (p->z - min->z);
+}
 
-	case 4: // Front face
-		x += 1;
-		y += 1;
-		break;
 
-	case 5: // Back face
-		x += 1;
-		y += 1;
-		z += 2;
+void
+fillvolume(void const * nodep, VISIT which, void * p)
+{
+	struct point * pt = *(struct point **) nodep;
+	void ** pp = p;
+	char * vol = pp[0];
+	struct point const * pmin = pp[1];
+	struct point const * pmax = pp[2];
+	char const * pch = pp[3];
+
+	switch (which) {
+	case postorder:
+	case leaf:
+		*volpos(vol, pt, pmin, pmax) = *pch;
 		break;
 
-	default:
-		return NULL;
+	case preorder:
+	case endorder:
+		break;
 	}
+}
 
-	if ((f = malloc(sizeof(struct point))) == NULL)
-		return NULL;
 
-	f->x = x;
-	f->y = y;
-	f->z = z;
-	return f;
+int
+faces_add(void ** faces, struct point * p)
+{
+	int nfaces = 0, dir;
+
+	for (dir = 0; dir < 6; ++dir) {
+		struct point * face, * exists;
+
+		face = cube_face(p, dir);
+
+		exists = *((struct point **) tsearch(face, faces, point_cmp_t));
+
+		if (exists == face) {
+			// Inserted new face
+			++nfaces;
+		}
+		else {
+			// Face already existed, so delete it
+			tdelete(face, faces, point_cmp_t);
+			--nfaces;
+			free(face);
+			free(exists);
+		}
+	}
+
+	return nfaces;
 }
 
 
 int
-main()
+main(int argc, char ** argv)
 {
+	int i, part = 1;
 	char buf[BUFSIZ];
 	regex_t cube;
 	regmatch_t coords[4];
-	void * faces = NULL;
-	int nfaces = 0;
+	void * lava = NULL, * faces = NULL;
+	int nfaces = 0, nintfaces = 0;
+	struct point pmin = {0}, pmax = {0};
+
+	while ((i = getopt(argc, argv, "p:")) != -1) {
+		switch (i) {
+		case 'p':
+			part = atoi(optarg);
+			break;
+
+		default:
+			return -1;
+		}
+	}
 
 	if (regcomp(&cube, "(-?[[:digit:]]+),(-?[[:digit:]]+),(-?[[:digit:]]+)", REG_EXTENDED) != 0) {
 		fprintf(stderr, "Bad regex\n");
@@ -117,36 +197,118 @@ main()
 	while (fgets(buf, sizeof(buf), stdin)
 			&& regexec(&cube, buf, arrlen(coords), coords, 0) == 0)
 	{
-		int x, y, z, f;
+		struct point * p, * exists;
+
+		p = point_create(atoi(buf + coords[1].rm_so),
+				atoi(buf + coords[2].rm_so),
+				atoi(buf + coords[3].rm_so));
+
+		pmin.x = min(pmin.x, p->x);
+		pmax.x = max(pmax.x, p->x);
+		pmin.y = min(pmin.y, p->y);
+		pmax.y = max(pmax.y, p->y);
+		pmin.z = min(pmin.z, p->z);
+		pmax.z = max(pmax.z, p->z);
+
+		exists = *((struct point **) tsearch(p, &lava, point_cmp_t));
+		if (exists != p) {
+			fprintf(stderr, "Duplicate lava at %d,%d,%d?\n", p->x, p->y, p->z);
+			free(p);
+		}
 
-		x = atoi(buf + coords[1].rm_so);
-		y = atoi(buf + coords[2].rm_so);
-		z = atoi(buf + coords[3].rm_so);
+		nfaces += faces_add(&faces, p);
+	}
 
-		for (f = 0; f < 6; ++f) {
-			struct point * face = cube_face(x, y, z, f);
+	if (part == 2) {
+		// Have to find interior volume. This is tricky, because it's
+		// hard to tell the difference between an interior, and a
+		// concave space, especially if the geometry is complex. When
+		// in doubt, try brute force. First, flood fill the entire
+		// exterior volume, and keep track of those cubes.
+		// Then look for all cubes in the bounding box that aren't part
+		// of the flood fill or the cubes given, and those are the
+		// interior cubes. Then work out the faces of *those* cubes,
+		// and those are the interior faces.
+		char * vol;
+		char chlava;
+		void * fillargs[4];
+		int filling;
+		struct point p;
+		void * intfaces = NULL;
+
+		// Increase the bounding box by 1 in all directions, so a flood
+		// fill can go all the way around the cube.
+		--pmin.x;
+		--pmin.y;
+		--pmin.z;
+		++pmax.x;
+		++pmax.y;
+		++pmax.z;
+
+		// Create the volume bounding box.
+		vol = calloc((1 + pmax.x - pmin.x) * (1 + pmax.y - pmin.y) * (1 + pmax.z - pmin.z), 1);
+
+		// Place the lava in the bounding box.
+		// Uses 'L' for lava.
+		chlava = 'L';
+		fillargs[0] = vol;
+		fillargs[1] = &pmin;
+		fillargs[2] = &pmax;
+		fillargs[3] = &chlava;
+		twalk_r(lava, fillvolume, fillargs);
+
+		// Fill the exterior of the bounding box.
+		// Uses 'F' for search front, 'X' for filled in eXterior.
+		vol[0] = 'F';
+		filling = 1;
+		while (filling) {
+			filling = 0;
+			for (p.x = pmin.x; p.x <= pmax.x; ++p.x) {
+				for (p.y = pmin.y; p.y <= pmax.y; ++p.y) {
+					for (p.z = pmin.z; p.z <= pmax.z; ++p.z) {
+						int dir;
+
+						if (*volpos(vol, &p, &pmin, &pmax) != 'F')
+							continue;
+
+						for (dir = 0; dir < 6; ++dir) {
+							struct point n;
+							char * pvol;
+
+							point_neighbour(&n, &p, dir);
+
+							if ((pvol = volpos(vol, &n, &pmin, &pmax)) != NULL
+									&& *pvol == '\0')
+							{
+								*pvol = 'F';
+								filling = 1;
+							}
+						}
+
+						*volpos(vol, &p, &pmin, &pmax) = 'X';
+					}
+				}
+			}
+		}
 
-			struct point * exists = *((struct point **) tsearch(face, &faces, point_cmp_t));
+		// Search for interior spaces, and get their total face count.
+		for (p.x = pmin.x; p.x <= pmax.x; ++p.x) {
+			for (p.y = pmin.y; p.y <= pmax.y; ++p.y) {
+				for (p.z = pmin.z; p.z <= pmax.z; ++p.z) {
+					if (*volpos(vol, &p, &pmin, &pmax) != '\0')
+						continue;
 
-			if (exists == face) {
-				// Inserted new face
-				++nfaces;
-			}
-			else {
-				// Face already existed, so delete it
-				tdelete(face, &faces, point_cmp_t);
-				--nfaces;
-				free(face);
-				free(exists);
+					nintfaces += faces_add(&intfaces, &p);
+				}
 			}
 		}
+
+		tdestroy(intfaces, free);
 	}
 
-	printf("Faces: %d\n", nfaces);
+	printf("Faces: %d\n", nfaces - nintfaces);
 
-#ifdef _GNU_SOURCE
 	tdestroy(faces, free);
-#endif
 	regfree(&cube);
 
 	return 0;