Puzzle 16: Extract function to find the flow of a given path

1 files changed, 39 insertions, 24 deletions

diff --git a/16.c b/16.c
index 6ad137e..0671a09 100644
--- a/16.c
+++ b/16.c
@@ -225,12 +225,41 @@ valve_distances(struct valve * valves, int nvalves)
 
 
 int
-valve_distance(struct valve * valves, int nvalves, int * dists, struct valve const * a, struct valve const * b)
+valve_distance(struct valve const * valves, int nvalves, int const * dists,
+		struct valve const * a, struct valve const * b)
 {
 	return dists[(a - valves) + nvalves * (b - valves)];
 }
 
 
+// Calculate flow of a given path
+int
+path_flow(int * valves_reached,
+		struct valve const * start, struct valve ** path, int pathlen,
+		struct valve const * valves, int nvalves, int const * dists,
+		int minutes)
+{
+	int flow = 0, i;
+
+	for (i = 0; i < pathlen; ++i) {
+		// Subtract travel time, and time to turn valve on
+		minutes -= valve_distance(valves, nvalves, dists,
+				i == 0 ? start : path[i - 1], path[i]);
+		minutes -= 1;
+
+		// Add the amount of flow for being turned on for remaining minutes
+		if (minutes <= 0)
+			break;
+
+		flow += path[i]->flow * minutes;
+	}
+
+	*valves_reached += i;
+
+	return flow;
+}
+
+
 int
 main(int argc, char ** argv)
 {
@@ -344,28 +373,14 @@ main(int argc, char ** argv)
 	// Go through all permutations of path to find max flow
 	qsort(path, nflows, sizeof(struct valve *), ptrcmp);
 	do {
-		int flow = 0, plumber = 0, minutes = eruption;
-
-		// Calculate the flow of this permutation.
-		for (i = 0; i < nflows && minutes > 0; ++i) {
-			// Subtract travel time, and time to turn valve on
-			minutes -= valve_distance(valves, nvalves, dists,
-					i == 0 ? start : path[i - 1], path[i]);
-			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;
-			}
+		int flow = 0, reached = 0, plumber;
 
-			// Add the amount of flow for being turned on for remaining minutes
-			flow += path[i]->flow * minutes;
-		}
+		// Calculate the flow of this permutation of path
+		for (plumber = 0; plumber < plumbers; ++plumber)
+			flow += path_flow(&reached,
+					start, path + reached,
+					nflows - reached - (plumbers - plumber - 1),
+					valves, nvalves, dists, eruption);
 
 		// Is it a new high?
 		if (flow > max) {
@@ -379,7 +394,7 @@ main(int argc, char ** argv)
 			}
 		}
 
-		if (i < nflows) {
+		if (reached < 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.
@@ -388,7 +403,7 @@ main(int argc, char ** argv)
 			// they'll be in their last permutation, and qpermute()
 			// will then pick the next path that is substantively
 			// different from this.
-			qreverse(path + i + 1, nflows - (i + 1), sizeof(struct valve *));
+			qreverse(path + reached + 1, nflows - (reached + 1), sizeof(struct valve *));
 		}
 	} while (qpermute(path, nflows, sizeof(struct valve *), ptrcmp));