Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #397429
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-08 23:45 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260408234507.00002dd6@yahoo.com> (permalink) |
| References | <20260401163447.000052de@yahoo.com> |
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."
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];
}
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 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-29 06:55 -0700
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