diff options
Diffstat (limited to '16.c')
| -rw-r--r-- | 16.c | 63 |
1 files changed, 39 insertions, 24 deletions
@@ -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)); |