path: root/18.c

#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;
	int y;
	int z;
};


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)
{
	if (a->x != b->x)
		return a->x - b->x;
	if (a->y != b->y)
		return a->y - b->y;
	return a->z - b->z;
}


int
point_cmp_t(void const * a, void const * b)
{
	return point_cmp(a, b);
}


// Get one of the faces of a cube
//
// To uniquely identify the faces of a cube, we scale the cube by a factor of
// two, and then identify each face by a point in one direction
struct point *
cube_face(struct point const * p, int direction)
{
	struct point dbl, face;

	dbl.x = p->x * 2;
	dbl.y = p->y * 2;
	dbl.z = p->z * 2;

	return point_copy(point_neighbour(&face, &dbl, direction));
}


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;

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


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;

	case preorder:
	case endorder:
		break;
	}
}


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(int argc, char ** argv)
{
	int i, part = 1;
	char buf[BUFSIZ];
	regex_t cube;
	regmatch_t coords[4];
	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");
		return -1;
	}

	while (fgets(buf, sizeof(buf), stdin)
			&& regexec(&cube, buf, arrlen(coords), coords, 0) == 0)
	{
		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);
		}

		nfaces += faces_add(&faces, p);
	}

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

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

					nintfaces += faces_add(&intfaces, &p);
				}
			}
		}

		tdestroy(intfaces, free);
	}

	printf("Faces: %d\n", nfaces - nintfaces);

	tdestroy(faces, free);
	regfree(&cube);

	return 0;
}