Puzzle 16: Commit partial solve of part 2

This solves the actual the puzzle, in the case where two plumbers (you
and the elephant) can't reach all the valves in time. But it doesn't
work for the test case, where you can, and it has to look for the most
efficient split of resources.

So, I got the gold star, but I wanted to create a full solution before
committing it. Obviously that didn't happen at the time. Might as well
commit what I have now, and look at improving it with a later fix.

1 files changed, 43 insertions, 15 deletions

diff --git a/16.c b/16.c
index a36810c..2954ef9 100644
--- a/16.c
+++ b/16.c
@@ -221,7 +221,7 @@ valve_distance(struct valve * valves, int nvalves, int * dists, struct valve con
 int
 main(int argc, char ** argv)
 {
-	int debug = 0, eruption = 30, i;
+	int debug = 0, eruption = 30, plumbers = 1, i;
 	regex_t valvein;
 	regmatch_t rmvalve[4];
 	char buf[BUFSIZ];
@@ -236,12 +236,34 @@ main(int argc, char ** argv)
 		return -1;
 	}
 
-	while ((i = getopt(argc, argv, "dt:")) != -1) {
+	while ((i = getopt(argc, argv, "dp:b:t:")) != -1) {
 		switch (i) {
 		case 'd':
 			debug = 1;
 			break;
 
+		case 'p':
+			switch (atoi(optarg)) {
+			case '1':
+				eruption = 30;
+				plumbers = 1;
+				break;
+
+			case 2:
+				eruption = 26;
+				plumbers = 2;
+				break;
+
+			default:
+				fprintf(stderr, "Unexpected part %s\n", optarg);
+				return -1;
+			}
+			break;
+
+		case 'b':
+			plumbers = atoi(optarg);
+			break;
+
 		case 't':
 			// 'time' is taken by time(3), hence 'eruption'
 			eruption = atoi(optarg);
@@ -273,9 +295,6 @@ main(int argc, char ** argv)
 		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
@@ -299,29 +318,38 @@ main(int argc, char ** argv)
 		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;
+	// Create a path containing all the valves that can flow, which are
+	// reachable from the start position before the eruption
+	path = malloc(nvalves * sizeof(struct valve *));
+	for (v = valves; v < valves + nvalves; ++v) {
+		if (v->flow > 0 && valve_distance(valves, nvalves, dists, start, v) < eruption)
+			path[nflows++] = v;
 	}
 
 	// Go through all permutations of path to find max flow
 	qsort(path, nflows, sizeof(struct valve *), ptrcmp);
 	do {
-		int flow = 0, minutes = eruption;
+		int flow = 0, plumber = 0, minutes = eruption;
 
 		// Calculate the flow of this permutation.
 		for (i = 0; i < nflows && minutes > 0; ++i) {
-			// Subtract travel time
+			// Subtract travel time, and time to turn valve on
 			minutes -= valve_distance(valves, nvalves, dists,
 					i == 0 ? start : path[i - 1], path[i]);
-			// Subtrace time to turn valve on
 			minutes -= 1;
 
+			if (minutes <= 0) {
+				// This plumber is out of time.
+				if (++plumber >= plumbers)
+					// Out of plumbers!
+					break;
+				minutes = eruption;
+				minutes -= valve_distance(valves, nvalves, dists, start, path[i]);
+				minutes -= 1;
+			}
+
 			// Add the amount of flow for being turned on for remaining minutes
-			if (minutes > 0)
-				flow += path[i]->flow * minutes;
+			flow += path[i]->flow * minutes;
 		}
 
 		// Is it a new high?