Puzzle 16: Speed up the permute skipping code

By realising that the first time we hit the need to skip, the items to
be skipped will be in sorted order; to change them to reverse-sorted
order just requires reversing the items, not re-sorting them backwards.

(On part 1 of the puzzle with a 40 minute limit, the timing goes from
6.6s to 4.3s, average of 5 runs.)

1 files changed, 7 insertions, 13 deletions

diff --git a/16.c b/16.c
index bb565bf..4dff42c 100644
--- a/16.c
+++ b/16.c
@@ -100,13 +100,6 @@ ptrcmp(void const * a, void const * b)
 }
 
 
-int
-ptrcmpr(void const * a, void const * b)
-{
-	return *((void **) b) - *((void **) a);
-}
-
-
 struct valve {
 	char name[3];
 	int flow;
@@ -389,12 +382,13 @@ main(int argc, char ** argv)
 		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
-			// the remining elements in reverse, which is the last
-			// possible permutation, so that the qpermute() will
-			// pick the next path that is substantively different
-			// from this.
-			qsort(path + i + 1, nflows - (i + 1), sizeof(struct valve *), ptrcmpr);
+			// path, because they don't matter.
+			// Remaining elements will be in their first possible
+			// permutation, i.e. in sorted order. If we reverse this
+			// 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 *));
 		}
 	} while (qpermute(path, nflows, sizeof(struct valve *), ptrcmp));