From 69a900c9b0e720c791f3d3deb28fc8de17f8cc8c Mon Sep 17 00:00:00 2001 From: Adam Spragg Date: Tue, 17 Jan 2023 14:58:52 +0000 Subject: 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.) --- 16.c | 20 +++++++------------- 1 file 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)); -- cgit v1.2.1