Groups | Search | Server Info | Keyboard shortcuts | Login | Register
Groups > comp.lang.c > #397469
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-10 17:02 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260410170258.00000a01@yahoo.com> (permalink) |
| References | <20260401163447.000052de@yahoo.com> <20260408234507.00002dd6@yahoo.com> <86ecknbt8l.fsf@linuxsc.com> |
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.
> > And here is a code. It is not very fast. But the speed is almost
> > the same on average and in the worst case.
> >
> > #include <stdint.h>
> > #include <stdbool.h>
> >
> > #include "solver.h"
> >
> > peek_t solver(boxes_t boxes)
> > {
> > uint8_t na[N_BOXES] = {0};
> > typedef struct { uint8_t s,d; } xch_t;
> > xch_t xch[N_BOXES*BOX_SIZE];
> > int i = 0;
> > for (int src_bi = 0; src_bi < N_BOXES; ++src_bi) {
> > for (int src_ci = na[src_bi]; src_ci < BOX_SIZE; ++src_ci) {
> > uint8_t dst_bi = boxes.b[src_bi][src_ci];
> > while (dst_bi != src_bi) {
> > uint8_t dst_ci = na[dst_bi];
> > uint8_t dst_v = boxes.b[dst_bi][dst_ci];
> > na[dst_bi] = dst_ci+1;
> > xch[i++] = (xch_t){ .s=src_bi, .d=dst_bi};
> > dst_bi = dst_v;
> > }
> > xch[i++] = (xch_t){ .s=src_bi, .d=dst_bi};
> > }
> > na[src_bi] = BOX_SIZE;
> > }
> >
> > for (int bi = 0; bi < N_BOXES; ++bi)
> > for (int ci = 0; ci < BOX_SIZE; ++ci)
> > boxes.b[bi][ci] = bi;
> >
> > uint8_t tx[N_BOXES][BOX_SIZE];
> > for (int bi = 0; bi < N_BOXES; ++bi)
> > for (int ci = 0; ci < BOX_SIZE; ++ci)
> > tx[bi][ci] = ci;
> >
> > peek_t threads[BOX_SIZE];
> > for (int ci = 0; ci < BOX_SIZE; ++ci)
> > for (int bi = 0; bi < N_BOXES; ++bi)
> > threads[ci].b[bi] = ci;
> >
> > for (int i = N_BOXES*BOX_SIZE-1; i >= 0; --i) {
> > uint8_t src_bi = xch[i].s;
> > uint8_t dst_bi = xch[i].d;
> > uint8_t dst_ci = na[dst_bi] - 1;
> > na[dst_bi] = dst_ci;
> > if (src_bi != dst_bi) {
> > uint8_t src_ci = na[src_bi];
> > uint8_t src_v = boxes.b[src_bi][src_ci];
> > if (src_v != dst_bi) {
> > uint8_t src_t = tx[src_bi][src_ci];
> > uint8_t dst_t = tx[dst_bi][dst_ci];
> > if (src_t != dst_t) {
> > // 2 threads broken. Fix
> > uint8_t v2bi[N_BOXES];
> > for (int bi = 0; bi < N_BOXES; ++bi)
> > v2bi[boxes.b[bi][threads[src_t].b[bi]]] = bi;
> > boxes.b[src_bi][src_ci] = dst_bi;
> > boxes.b[dst_bi][dst_ci] = src_v;
> > for (uint8_t v = dst_bi; v != src_v;) {
> > uint8_t bi = v2bi[v];
> > uint8_t c0 = threads[src_t].b[bi];
> > uint8_t c1 = threads[dst_t].b[bi];
> > threads[src_t].b[bi] = c1;
> > threads[dst_t].b[bi] = c0;
> > tx[bi][c1] = src_t;
> > tx[bi][c0] = dst_t;
> > v = boxes.b[bi][c1];
> > }
> > } else {
> > boxes.b[src_bi][src_ci] = dst_bi;
> > boxes.b[dst_bi][dst_ci] = src_v;
> > }
> > }
> > }
> > }
> >
> > return threads[0];
> > }
>
> 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.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar
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