diff options
| -rw-r--r-- | 16.c | 91 |
1 files changed, 83 insertions, 8 deletions
@@ -260,6 +260,84 @@ path_flow(int * valves_reached, } +// Calculate the best flow for a path, with a given set of plumbers +// +// Note that we only try cases where each subsequent plumber visits an equal or +// decreasing number of valves. This is because, given e.g. +// +// a b c d e f g h +// +// If there are two plumbers with plenty of time to spare, the first might be +// able to get all the way up to 'f' by themselves. And we want to test all +// possible divisions of work to find the one with the most flow. But, we +// don't need to test the case where one plumber checks 'a' to 'c' and the +// other checks 'd' to 'h' here, because that will automatically get tested +// in the permutation. +// +// d e f g h a b c +// +// So we only need to test equal-or-decreasing valves because increasing numbers +// of valves will be tested in a different iteration. Note that we still see +// some duplication of testing in the case of 'a' to 'd' and 'e' to 'h', but +// I can't see a way around that for now. +int +path_flow_plumbers(int * valves_reached, + struct valve const * start, struct valve ** path, int pathlen, + struct valve const * valves, int nvalves, int const * dists, int minutes, + int plumbers, int max_valves) +{ + int flow_max = 0, flow_max_valves = 0; + + if (plumbers == 0) + // No plumbers, no flow. + return 0; + + // If there are 3 other plumbers, we don't want to try to reach the last + // 3 valves, because we want to leave one each for them. + // Or, if there are no other plumbers, we don't want to try more than + // pathlen valves. + if (max_valves > pathlen - (plumbers - 1)) + max_valves = pathlen - (plumbers - 1); + + if (plumbers == 1) + // One plumber, simple case. + return path_flow(valves_reached, + start, path, max_valves, + valves, nvalves, dists, minutes); + + // Try the maximum number of valves we can reach first, and the flow + // that other plumbers can reach from there, and then loop backwards + // through the number of valves we try to see which one gives the max + // flow. + while (max_valves > 0) { + int flow, valves_self = 0, valves_rest = 0; + + flow = path_flow(&valves_self, + start, path, max_valves, + valves, nvalves, dists, minutes); + flow += path_flow_plumbers(&valves_rest, + start, path + valves_self, pathlen - valves_self, + valves, nvalves, dists, minutes, + plumbers - 1, valves_self); + + if (flow > flow_max) { + // New max. + flow_max = flow; + flow_max_valves = valves_self + valves_rest; + } + + // Can't reach all the valves from here. No improvements await + if (valves_self + valves_rest < pathlen) + break; + + max_valves = valves_self - 1; + } + + *valves_reached += flow_max_valves; + return flow_max; +} + + int main(int argc, char ** argv) { @@ -373,14 +451,11 @@ 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, reached = 0, plumber; - - // 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); + int flow, reached = 0; + + flow = path_flow_plumbers(&reached, start, path, nflows, + valves, nvalves, dists, eruption, + plumbers, nflows); // Is it a new high? if (flow > max) { |