Groups | Search | Server Info | Login | Register

Groups > comp.lang.c > #397483

Re: Cookies in boxes - algorithmic challenge

From Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups comp.lang.c
Subject Re: Cookies in boxes - algorithmic challenge
Date 2026-04-11 03:45 -0700
Organization A noiseless patient Spider
Message-ID <86wlydai7y.fsf@linuxsc.com> (permalink)
References <20260401163447.000052de@yahoo.com> <20260408234507.00002dd6@yahoo.com> <86ecknbt8l.fsf@linuxsc.com> <20260410170258.00000a01@yahoo.com>

Show all headers | View raw

Michael S <already5chosen@yahoo.com> writes:

> On Thu, 09 Apr 2026 16:37:30 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>> On Wed, 1 Apr 2026 16:34:47 +0300
>>> Michael S <already5chosen@yahoo.com> wrote:
>>>
>>> <snip>
>>>
>>> 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.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 16:34 +0300
  Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 10:02 -0400
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:15 +0300
      Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 10:28 -0400
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:58 +0300
  Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 15:20 +0100
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:56 +0300
      Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 19:50 +0100
        Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 15:56 -0400
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 23:33 +0100
        Re: Cookies in boxes - algorithmic challenge Richard Harnden <richard.nospam@gmail.invalid> - 2026-04-04 07:43 +0100
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-04 11:54 +0100
  Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 15:24 -0400
  Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 17:24 -0400
    Re: Cookies in boxes - algorithmic challenge Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-04-02 16:25 +0100
      Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-02 17:10 +0100
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:19 +0300
      Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-02 13:03 -0400
        Re: Cookies in boxes - algorithmic challenge Richard Harnden <richard.nospam@gmail.invalid> - 2026-04-02 18:52 +0100
        Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-02 19:50 +0100
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:24 +0300
        Re: Cookies in boxes - algorithmic challenge Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-04-02 20:13 +0100
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:36 +0300
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:14 +0300
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:10 +0300
      Re: Cookies in boxes - algorithmic challenge Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-04-06 22:36 +0100
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 15:42 -0700
        Re: Cookies in boxes - algorithmic challenge Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-04-06 15:44 -0700
  Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-04 13:33 -0400
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-04 21:03 +0300
      Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-04 14:19 -0400
      Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-04 20:22 +0100
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-04 22:40 +0300
  Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-04 17:08 -0700
  Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-08 08:42 -0700
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 22:23 +0300
      Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 21:22 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 12:23 +0300
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-10 22:41 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 16:16 +0300
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:27 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-11 22:56 +0300
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 15:57 -0700
            Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-12 02:15 +0300
            Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-13 02:03 +0300
            Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-13 17:11 +0300
              Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 23:52 -0700
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 14:44 +0300
                Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-17 07:40 -0700
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 18:30 +0300
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-20 00:43 +0300
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-21 20:37 +0300
                Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-21 18:22 -0700
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-22 12:05 +0300
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-15 02:15 +0300
      Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 02:57 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 17:04 +0300
  Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 23:45 +0300
    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 16:37 -0700
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 17:02 +0300
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 03:45 -0700
  Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-09 00:01 +0300
    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 17:07 -0700
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 18:06 +0300
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:31 -0700
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 03:22 -0700
  Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 17:58 +0200
    Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 18:08 +0200
    Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-17 17:47 +0100
      Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:24 +0200
    Re: Cookies in boxes - algorithmic challenge scott@slp53.sl.home (Scott Lurndal) - 2026-04-17 19:58 +0000
      Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-18 05:52 +0200
        Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 11:53 +0100
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 12:04 +0100
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-18 20:35 +0300
  Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:52 +0200
    Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 20:17 +0200

csiph-web