Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Cookies in boxes - algorithmic challenge Date: Sat, 11 Apr 2026 04:27:54 -0700 Organization: A noiseless patient Spider Lines: 49 Message-ID: <86mrz9ag91.fsf@linuxsc.com> References: <20260401163447.000052de@yahoo.com> <86tstlwjak.fsf@linuxsc.com> <20260408222330.00005cf8@yahoo.com> <865x5zbg10.fsf@linuxsc.com> <20260410161638.00007745@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Sat, 11 Apr 2026 11:27:55 +0000 (UTC) Injection-Info: dont-email.me; posting-host="21f9f6d525ecd04de8977c5f6117a238"; logging-data="1813112"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19oyqtjmUF3ywp9gjrvE03k/q3ZQ3QhtTM=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:8uEAdc5L6if49JhKSKltAUGCaEw= sha1:dozvp9qPdEVzjOUULgmVAx1+szc= Xref: csiph.com comp.lang.c:397484 Michael S writes: > On Thu, 09 Apr 2026 21:22:51 -0700 > Tim Rentsch wrote: (just a few short replies) >> [...] >> >> At each level of recursion, do the following: >> >> If the search depth is the number of boxes, longjmp() >> >> Next find the cookie of cookies in the solution state at or >> above this level that has the smallest number of boxes. Because >> the box count is held in the uppermost bits the 64-bit values can >> simply be directly compared, without any masking. > > Is it proven that this step helps? > To me it sounds unnecessary. My experience with backtracking algorithms tells me that selecting a path where the number of possible choices is smallest usually does a better job of finding a solution quickly. >> [...] >> >> I think that's it. I hope it makes sense. > > It makes sense, but it looks to me as solution by exhausting, augmented > by "smallest number of boxes" heuristic. > It's not obvious [to me] without further thinking that the worst case is > not very slow. Several short responses. I think "by exhaustion" is usually taken to mean an unguided exploration of all alternatives, even ones that aren't plausible. Backtracking isn't that. Backtracking is recognized as a viable search strategy in lots of different kinds of problems, including problems that are known to be NP complete. It has a good pedigree. My goals in writing the program were to write a program that is understandable, that does find solutions, and that has reasonable performance. Since the program did find answers and also met your stated performance goals, I have no reason to be dissatisfied.