From 816b7d55d6d3dfb31904cb5d4813fb500984ab5b Mon Sep 17 00:00:00 2001 From: Adam Spragg Date: Thu, 19 Jan 2023 13:56:59 +0000 Subject: Puzzle 20: Do a linear scan for the num we're looking for When the number of iterations was small, looking near the original position of the num was a good idea. As the number of iterations increases, the positions are fairly random, so speed of lookup is mostly a factor of how quickly we can scan the whole buffer. Speeds up part 2 of the problem from 2.2s to 0.12s. --- 20.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to '20.c') diff --git a/20.c b/20.c index e427217..677c9df 100644 --- a/20.c +++ b/20.c @@ -101,10 +101,9 @@ main(int argc, char ** argv) int newpos; struct num tmp; - // Look for the num whose ordinal is i, starting from the - // position of the last num we looked at. - while (nums[pos].ord != i) - pos = modulo(pos + 1, nnums); + // Look for the num whose ordinal is i + for (pos = 0; nums[pos].ord != i; ++pos) + ; if (nums[pos].val == 0) continue; -- cgit v1.2.1