diff options
| -rw-r--r-- | 16.c | 58 |
1 files changed, 43 insertions, 15 deletions
@@ -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? |