From 8f0114df375c7b9bd750e3e0e6fbecb964639d3d Mon Sep 17 00:00:00 2001 From: Adam Spragg Date: Wed, 18 Jan 2023 14:42:49 +0000 Subject: Puzzle 16: Solve part 2 fully We now manage the general case of dividing up the work between as many plumbers as available, as equally as possible. Works for the test case and the full input case. (Actually, it seems to speed up the full input case, from around 68s to 55s!) --- 16.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 83 insertions(+), 8 deletions(-) (limited to '16.c') diff --git a/16.c b/16.c index 0671a09..057ab8d 100644 --- a/16.c +++ b/16.c @@ -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) { -- cgit v1.2.1