Solve puzzle 16 part 1

That was a tough one. Still takes 2.5s on my hardware. Should be able to
multithread the permuation search at some point, if I want to.

2 files changed, 356 insertions, 0 deletions

diff --git a/16.c b/16.c
new file mode 100644
index 0000000..bff6c6a
--- /dev/null
+++ b/16.c
@@ -0,0 +1,355 @@
+
+#include <regex.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+
+#define arrlen(x) (sizeof(x)/sizeof((x)[0]))
+
+
+void *
+qelem(void * base, size_t size, int i)
+{
+	return (char *) base + i * size;
+}
+
+
+void
+qswap(void * base, size_t size, int i, int j)
+{
+	char tmp[size];
+	memcpy(tmp, qelem(base, size, i), size);
+	memcpy(qelem(base, size, i), qelem(base, size, j), size);
+	memcpy(qelem(base, size, j), tmp, size);
+}
+
+
+int
+qpermute(void * base, size_t nmemb, size_t size,
+		int(*compar)(const void *, const void *))
+{
+	size_t pivot, next = 0, i, j;
+
+	if (nmemb < 2)
+		// No other permutations!
+		return 0;
+
+	if (nmemb == 2) {
+		if (compar(qelem(base, size, 0), qelem(base, size, 1)) >= 0)
+			return 0;
+
+		qswap(base, size, 0, 1);
+		return 1;
+	}
+
+	for (pivot = nmemb - 1; pivot > 0; --pivot)
+		if (compar(qelem(base, size, pivot - 1), qelem(base, size, pivot)) < 0)
+			break;
+	if (pivot == 0)
+		// In final permutation (anti-sorted) order. None more remain.
+		return 0;
+	--pivot;
+
+	// Find the next item to go in pivot's place, the right-most element
+	// larger than pivot
+	for (i = pivot + 1; i < nmemb; ++i)
+		if (compar(qelem(base, size, pivot), qelem(base, size, i)) < 0)
+			next = i;
+	if (!next)
+		return 0;
+
+	// Swap the pivot with its replacement
+	qswap(base, size, pivot, next);
+
+	// Reverse all the elements after the new pivot
+	for (i = pivot + 1, j = nmemb - 1; i < j; ++i, --j)
+		qswap(base, size, i, j);
+
+	return 1;
+}
+
+
+int
+ptrcmp(void const * a, void const * b)
+{
+	return *((void **) a) - *((void **) b);
+}
+
+
+int
+ptrcmpr(void const * a, void const * b)
+{
+	return *((void **) b) - *((void **) a);
+}
+
+
+struct valve {
+	char name[3];
+	int flow;
+	int ndests;
+	char * destnames;
+	struct valve ** dests;
+};
+
+
+int
+valve_ctor(struct valve * v, char const * name, int flow, char const * dests)
+{
+	int ndests;
+
+	if (strlen(name) != 2
+			|| (ndests = strlen(dests)) % 4 != 2)
+		return -1;
+
+	strcpy(v->name, name);
+	v->flow = flow;
+	v->ndests = (ndests + 2) / 4;
+	v->destnames = strdup(dests);
+	v->dests = calloc(ndests + 1, sizeof(struct valve *));
+
+	return 0;
+}
+
+
+void
+valve_dtor(struct valve * v)
+{
+	if (!v)
+		return;
+	free(v->destnames);
+	free(v->dests);
+}
+
+
+void
+valve_setdests(struct valve * v, struct valve * others, int nothers)
+{
+	int i, j;
+
+	for (i = 0; i < v->ndests; ++i) {
+		for (j = 0; j < nothers; ++j) {
+			if (strncmp(v->destnames + i * 4, others[j].name, 2) == 0) {
+				v->dests[i] = others + j;
+				break;
+			}
+		}
+
+		if (!v->dests[i])
+			fprintf(stderr, "Cannot find %2.2s for %s\n", v->destnames + i * 4, v->name);
+	}
+}
+
+
+#if 0
+void
+valve_distances_dump(struct valve const * valves, int nvalves, int * dists)
+{
+	int i, j;
+
+	fprintf(stderr, "   ");
+	for (i = 0; i < nvalves; ++i) {
+		fprintf(stderr, " %s", valves[i].name);
+	}
+	fprintf(stderr, "\n");
+
+	for (i = 0; i < nvalves; ++i) {
+		fprintf(stderr, " %s", valves[i].name);
+		for (j = 0; j < nvalves; ++j) {
+			fprintf(stderr, " %2d", dists[j + i * nvalves]);
+		}
+		fprintf(stderr, "\n");
+	}
+	fprintf(stderr, "\n");
+}
+#endif
+
+
+// Precalculate distances between all pairs of valves
+int *
+valve_distances(struct valve * valves, int nvalves)
+{
+	int * dists;
+	int i, j, n, more;
+	struct valve ** v;
+
+	if ((dists = malloc(nvalves * nvalves * sizeof(int))) == NULL)
+		return NULL;
+
+	// Initialise.
+	for (i = 0; i < nvalves; ++i) {
+		for (j = 0; j < nvalves; ++j) {
+			dists[j + i * nvalves] = (i == j) ? 0 : -1;
+		}
+	}
+
+	// Find successive distances
+	for (n = 0, more = 1; more == 1; ++n) {
+		more = 0;
+		for (i = 0; i < nvalves; ++i) {
+			// On each row.
+			for (j = 0; j < nvalves; ++j) {
+				// Look for valves that takes n steps to get to.
+				if (dists[j + i * nvalves] != n)
+					continue;
+
+				for (v = valves[j].dests; v < valves[j].dests + valves[j].ndests; ++v) {
+					if (dists[*v - valves + i * nvalves] != -1)
+						continue;
+
+					// Found a neighbor that we can't get to quicker
+					// so we can get to it in n + 1 steps
+					dists[(*v - valves) + i * nvalves] = n + 1;
+					more = 1;
+				}
+			}
+		}
+	}
+
+	return dists;
+}
+
+
+int
+valve_distance(struct valve * valves, int nvalves, int * dists, struct valve const * a, struct valve const * b)
+{
+	return dists[(a - valves) + nvalves * (b - valves)];
+}
+
+
+int
+main(int argc, char ** argv)
+{
+	int debug = 0, i;
+	regex_t valvein;
+	regmatch_t rmvalve[4];
+	char buf[BUFSIZ];
+	struct valve * valves = NULL, * v, * start = NULL, ** path;
+	int nvalves = 0, nflows = 0, max = 0;
+	int * dists;
+
+	if (regcomp(&valvein, "Valve ([[:upper:]]{2}) has flow rate=([[:digit:]]+);"
+				" tunnels? leads? to valves? (([[:upper:]]{2}(, )?)+)", REG_EXTENDED) != 0)
+	{
+		fprintf(stderr, "Bad regex\n");
+		return -1;
+	}
+
+	while ((i = getopt(argc, argv, "d")) != -1) {
+		switch (i) {
+		case 'd':
+			debug = 1;
+			break;
+
+		default:
+			return -1;
+		}
+	}
+
+	// Read in valve data
+	while (fgets(buf, sizeof(buf), stdin)
+			&& regexec(&valvein, buf, arrlen(rmvalve), rmvalve, 0) == 0)
+	{
+		void * p;
+
+		if ((p = realloc(valves, ++nvalves * sizeof(struct valve))) == NULL) {
+			fprintf(stderr, "Bad realloc(%zd)\n", nvalves * sizeof(struct valve));
+			free(valves);
+			return -1;
+		}
+		valves = p;
+		v = valves + nvalves - 1;
+
+		buf[rmvalve[1].rm_eo] = '\0';
+		buf[rmvalve[2].rm_eo] = '\0';
+		buf[rmvalve[3].rm_eo] = '\0';
+		valve_ctor(v, buf + rmvalve[1].rm_so,
+				atoi(buf + rmvalve[2].rm_so),
+				buf + rmvalve[3].rm_so);
+
+		if (v->flow > 0)
+			++nflows;
+	}
+
+	// Set up valve dests
+	for (v = valves; v < valves + nvalves; ++v)
+		valve_setdests(v, valves, nvalves);
+
+	// Calculate distances between all valves
+	dists = valve_distances(valves, nvalves);
+
+	// Find start position
+	for (v = valves; v < valves + nvalves && !start; ++v) {
+		if (strcmp(v->name, "AA") == 0)
+			start = v;
+	}
+	if (!start) {
+		fprintf(stderr, "Unable to find start valve in %d valves\n", nvalves);
+		for (v = valves; v < valves + nvalves; ++v)
+			valve_dtor(v);
+		free(valves);
+		return -1;
+	}
+
+	// Create an initial path between all valves that can flow
+	path = malloc((1 + nflows) * sizeof(struct valve *));
+	path[0] = start;
+	for (v = valves, i = 1; v < valves + nvalves; ++v) {
+		if (v->flow > 0)
+			path[i++] = v;
+	}
+
+	// Go through all permutations to find max flow
+	qsort(path + 1, nflows, sizeof(struct valve *), ptrcmp);
+	do {
+		struct valve ** pv;
+		int flow = 0, minutes = 30;
+
+		// Calculate the flow of this permutation.
+		for (pv = path + 1; pv < path + 1 + nflows && minutes > 0; ++pv) {
+			// Subtract travel time
+			minutes -= valve_distance(valves, nvalves, dists, *(pv - 1), *pv);
+			// Subtrace time to turn valve on
+			minutes -= 1;
+
+			// Add the amount of flow for being turned on for remaining minutes
+			if (minutes > 0)
+				flow += (*pv)->flow * minutes;
+		}
+
+		// Is it a new high?
+		if (flow > max) {
+			if (debug) {
+				fprintf(stderr, "Found new max flow: %d: ", max);
+				for (pv = path; pv < path + 1 + nflows; ++pv)
+					fprintf(stderr, "%s%s", pv == path ? "" : "->", (*pv)->name);
+				fprintf(stderr, "\n");
+			}
+			max = flow;
+		}
+
+		if (pv < path + 1 + nflows) {
+			// We didn't get to the end of the path. We can skip all
+			// the permutations of all the remaining elements in the
+			// path, because they don't matter. Do this by sorting
+			// the remining elements in reverse, which is the last
+			// possible permutation, so that the qpermute() will
+			// pick the next path that is substantively different
+			// from this.
+			qsort(pv + 1, path + 1 + nflows - (pv + 1), sizeof(struct valve *), ptrcmpr);
+		}
+	} while (qpermute(path + 1, nflows, sizeof(struct valve *), ptrcmp));
+
+	printf("Max flow: %d\n", max);
+
+	// Done.
+	free(path);
+	free(dists);
+	for (v = valves; v < valves + nvalves; ++v)
+		valve_dtor(v);
+	free(valves);
+
+	return 0;
+}
+
diff --git a/makefile b/makefile
index ce27a0a..241807e 100644
--- a/makefile
+++ b/makefile
@@ -17,6 +17,7 @@ all: bin \
 	bin/13 \
 	bin/14 \
 	bin/15 \
+	bin/16 \
 
 bin:
 	mkdir -p $@