#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, eruption = 30, 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, "dt:")) != -1) {
		switch (i) {
		case 'd':
			debug = 1;
			break;

		case 't':
			// 'time' is taken by time(3), hence 'eruption'
			eruption = atoi(optarg);
			break;

		default:
			regfree(&valvein);
			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);
		regfree(&valvein);
		return -1;
	}

	// Create a path containing all the valves that can flow
	path = malloc(nflows * sizeof(struct valve *));
	for (v = valves, i = 0; v < valves + nvalves; ++v) {
		if (v->flow > 0)
			path[i++] = v;
	}

	// Go through all permutations of path to find max flow
	qsort(path, nflows, sizeof(struct valve *), ptrcmp);
	do {
		int flow = 0, minutes = eruption;

		// Calculate the flow of this permutation.
		for (i = 0; i < nflows && minutes > 0; ++i) {
			// Subtract travel time
			minutes -= valve_distance(valves, nvalves, dists,
					i == 0 ? start : path[i - 1], path[i]);
			// Subtrace time to turn valve on
			minutes -= 1;

			// Add the amount of flow for being turned on for remaining minutes
			if (minutes > 0)
				flow += path[i]->flow * minutes;
		}

		// Is it a new high?
		if (flow > max) {
			if (debug) {
				int j;
				fprintf(stderr, "Found new max flow: %d: %s", max, start->name);
				for (j = 0; j < nflows; ++j)
					fprintf(stderr, "->%s", path[j]->name);
				fprintf(stderr, "\n");
			}
			max = flow;
		}

		if (i < 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(path + i + 1, nflows - (i + 1), sizeof(struct valve *), ptrcmpr);
		}
	} while (qpermute(path, 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);
	regfree(&valvein);

	return 0;
}