diff options
Diffstat (limited to '16.c')
| -rw-r--r-- | 16.c | 33 |
1 files changed, 16 insertions, 17 deletions
@@ -297,45 +297,44 @@ main(int argc, char ** argv) return -1; } - // Create an initial path between all valves that can flow - path = malloc((1 + nflows) * sizeof(struct valve *)); - path[0] = start; - for (v = valves, i = 1; v < valves + nvalves; ++v) { + // 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; } - // Go through all permutations to find max flow - qsort(path + 1, nflows, sizeof(struct valve *), ptrcmp); + // Go through all permutations of path to find max flow + qsort(path, nflows, sizeof(struct valve *), ptrcmp); do { - struct valve ** pv; int flow = 0, minutes = eruption; // Calculate the flow of this permutation. - for (pv = path + 1; pv < path + 1 + nflows && minutes > 0; ++pv) { + for (i = 0; i < nflows && minutes > 0; ++i) { // Subtract travel time - minutes -= valve_distance(valves, nvalves, dists, *(pv - 1), *pv); + minutes -= valve_distance(valves, nvalves, dists, + i == 0 ? start : path[i - 1], path[i]); // Subtrace time to turn valve on minutes -= 1; // Add the amount of flow for being turned on for remaining minutes if (minutes > 0) - flow += (*pv)->flow * minutes; + flow += path[i]->flow * minutes; } // Is it a new high? if (flow > max) { if (debug) { - struct valve ** j; - fprintf(stderr, "Found new max flow: %d: ", max); - for (j = path; j < path + 1 + nflows; ++j) - fprintf(stderr, "%s%s", j == path ? "" : "->", (*j)->name); + int j; + fprintf(stderr, "Found new max flow: %d: %s", max, start->name); + for (j = 0; j < nflows; ++j) + fprintf(stderr, "->%s", path[j]->name); fprintf(stderr, "\n"); } max = flow; } - if (pv < path + 1 + nflows) { + if (i < 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. Do this by sorting @@ -343,9 +342,9 @@ main(int argc, char ** argv) // possible permutation, so that the qpermute() will // pick the next path that is substantively different // from this. - qsort(pv + 1, path + 1 + nflows - (pv + 1), sizeof(struct valve *), ptrcmpr); + qsort(path + i + 1, nflows - (i + 1), sizeof(struct valve *), ptrcmpr); } - } while (qpermute(path + 1, nflows, sizeof(struct valve *), ptrcmp)); + } while (qpermute(path, nflows, sizeof(struct valve *), ptrcmp)); printf("Max flow: %d\n", max); |