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 03:45:21 -0700 Organization: A noiseless patient Spider Lines: 94 Message-ID: <86wlydai7y.fsf@linuxsc.com> References: <20260401163447.000052de@yahoo.com> <20260408234507.00002dd6@yahoo.com> <86ecknbt8l.fsf@linuxsc.com> <20260410170258.00000a01@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Sat, 11 Apr 2026 10:45:22 +0000 (UTC) Injection-Info: dont-email.me; posting-host="21f9f6d525ecd04de8977c5f6117a238"; logging-data="1813112"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+J1D57Mf/bu/anJpanumO8wWlg6AEzwB0=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:4LksVX4SKKTjPYVtx+q0EuF3QEU= sha1:Vq1eefY+QefrkpmIJBi/95+PrAw= Xref: csiph.com comp.lang.c:397483 Michael S writes: > On Thu, 09 Apr 2026 16:37:30 -0700 > Tim Rentsch wrote: > >> Michael S writes: >> >>> On Wed, 1 Apr 2026 16:34:47 +0300 >>> Michael S wrote: >>> >>> >>> >>> My implementation #1. >>> It is based on the proof provided by somebody with abstract math >>> attitude. >>> He said that his proof is something that the 5th grade >>> schoolchildren could find with in 5 minutes. >>> I am no 5th pupil any longer. Even understanding of his proof took >>> me significantly longer than 5 minutes :( >>> Here is my attempt of translation (original proof was not in >>> English): >>> >>> "Solution would be done by induction by number of cookies of each >>> sort (the same for all sorts). >>> For K=2 the solution is simple. Please figure it out yourself. >>> Now let's take K > 2 and postulate that for numbers of cookies per >>> box that are smaller than K the assertion already proven. >>> Let's take some disposition for which the assertion is correct and >>> remove the corresponding "thread" (i.e. one cookie from each box, >>> all of different sorts). Then supposition of induction is correct >>> for remaining disposition, which means that we can remove yet >>> another thread, then yet another etc.. for a total of K threads. >>> That is, for K>2 there are more than 2 threads. >>> Now let's exchange places between any 2 two cookies from different >>> boxes. Since by doing so we are touching 1 or 2 threads then there >>> still be at least one thread untouched (at least k-2 threads, >>> actually [M.S.]). It means that the property "we can remove a >>> thread" is not disturbed by our action (i.e. by exchange of two >>> cookies). What is left it is to realize that by means of such >>> exchanges any disposition can be mutated from any other disposition. >>> That's all." >> >> I am confident that my understanding of this description, if indeed >> it ever occurs, would take a good deal longer than five minutes. >> Sadly I think it is representative of many of the explanations >> offered by mathematical types. > > He was not fully sutisfied himself. 20 hours later he came with other > formulation. Here is my attemp of translatioon: > > 1. There exist a disposition of cookies in boxes, for which it is > possible to select one cookie from each box, all of different sorts. > That is obvious. [MS: For example, each sort of cookies in its own > dedicated box. That is a disposition that I use in my code] Let's call > the selection "thread". > > 2. There exists an operation that changes the disposition, but > preserves the property "it is possible to select a thread" (the > description of the operation would be given separately, a.t.m. it does > not matter). > > 3. By means of multiple operations of that type it is possible to turn > any arbitrary disposition to any other. Since after every step the > property "it is possible to select a thread" is preserved and because > there exist a disposition, for which this property is true, it means > that the property is true for any possible disposition. > > 4. The operations in question - exchange of any pair of cookies. > Comment: Induction is used only in (2) for proof that an operation > preserves the desired property. > > For me, the second variant was less helpful. May be, for you it would > be more helpful. I do at least understand it. It doesn't really help me construct a solution, because I don't see how to transition from one choice function (aka "thread") to another after exchanging a pair of cookies. (Nor do I want an explanation of how to do so.) >>> [...code...] >> >> In most cases I'm not a big fan of interactive debugging, but >> trying to understand how this works might merit an exception. > > Frankly, not all difficulties of following my code caused by the fact > that algorithm is derived from abstract proof. > Significant share of hurdles are rooted in my somewhat conflicting > desires to avoid all searches, except for inevitable search in the > innermost loop of the second pass, but at the same time to keep format > of the governing database (xch array+na array) minimalistic. For what it's worth, I think your code has a better chance of being understandable than the mathematical description of finding a solution. Not interested enough to pursue it though.