Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397457
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-09 16:37 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <86ecknbt8l.fsf@linuxsc.com> (permalink) |
| References | <20260401163447.000052de@yahoo.com> <20260408234507.00002dd6@yahoo.com> |
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.
> 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.
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