Groups | Search | Server Info | Keyboard shortcuts | Login | Register
Groups > comp.lang.c > #397427
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-08 22:23 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260408222330.00005cf8@yahoo.com> (permalink) |
| References | <20260401163447.000052de@yahoo.com> <86tstlwjak.fsf@linuxsc.com> |
On Wed, 08 Apr 2026 08:42:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> [...]
>
> Here I am again, ready now to write a more substantive response.
>
> > So, here is the challenge:
> > There are 20 sorts of cookies, 10 of each sort. They are placed in
> > 20 boxes, again, 10 cookies in each boxes. You have to take exactly
> > one cookie from each box, all 20 of different sorts.
> > Smart math heads proved that for any distribution a solution exists.
> > I don't ask you to repeat the proof. Just peek cookies!
>
> I think the problem is interesting. I thought I would try coding
> something up.
>
> > It's obvious that one can find the solution by exhausting. Don't do
> > it. Indeed, the number of possible peek orders is finite, but ii is
> > large - 2.4e18.
> > Be smarter.
> > On modern PC I want to get a solution in less than 1 msec, bonus for
> > less than 50usec.
>
> [.. C code to drive an exercise a proposed solution ..]
>
> > You have to implement function solver() in module solver.c
>
> I ran into trouble when I tried to work within the posted framework
> to drive a solver. The difficulties were of several kinds. The
> code didn't compile in my standard compilation environment, which
> is roughly this (the c99 might be c11 but that made no difference):
>
> gcc -x c -std=c99 -pedantic ...
>
What were the problems?
My gcc 14.2.0 on msys2 produces no warnings or errors with above flags.
> I was able to work through that problem but it was irksome. The
> second difficulty is the interface to solver() seems rather clunky
> to me, maybe not for the input but for the output, and it wasn't
> clear to me what the specification is for the output (I did manage
> to figure this out but only much later). I was having to put more
> effort into figuring out the interface than solving the problem.
>
Yes, I should have explained it, at least briefly.
I'd guess that you expected that values in result vector correspond to
sorts of cookies, when in fact they are indices to position of the
cookie in the box.
I am sorry.
> Finally I abandoned the idea of working within the structure of the
> posted driver code and wrote a solver to my own specification.
> Doing that was fairly straightforward and took half an hour or so
> (disclaimer: after I had spent a good amount of time just thinking
> about the problem). After writing the solver I reimplemented a
> driver framework to drive it, conforming to the interface I was
> using. Some debugging was needed to get everything working. I did
> some rudimentary time measurements for the solver. Results were
> good (more about the specifics later).
>
> After doing the new solver I went back to the posted driver code,
> and grafted together the new solver with the orginal driver. Some
> glue code was needed to reconcile the differences in interface
> between the new solver and the original driver. Then I needed to
> figure out the semantics of the output, which were different than
> what I expected and originally understood. I figured all that out
> and got things working. Sadly the code was uglier than I would have
> liked.
>
> After that, I talked to a friend to try a different approach to
> producing a solution. After some light editing by myself -- mostly
> just formatting and some name changes -- the code below was put into
> the hopper. (Note: I claim no credit for code below. I did some
> editing to make it more readable but beyond that none of it is a
> result of my efforts.)
>
> #include <stdint.h>
> #include "solver.h"
>
> static uint32_t adjacent[ N_BOXES ];
> static int cookie_of_box[ N_BOXES ];
> static int box_of_cookie[ N_BOXES ];
> static uint32_t seen;
>
> static int
> search( int b ){
> uint32_t m = adjacent[b];
> while( m ){
> uint32_t bit = m & -m;
> m ^= bit;
> int c = __builtin_ctz( bit );
> if( seen & 1u<<c ) continue;
> seen |= 1u<<c;
> if( box_of_cookie[c] == -1 || search( box_of_cookie[c]
> ) ){ box_of_cookie[c] = b;
> cookie_of_box[b] = c;
> return 1;
> }
> }
> return 0;
> }
>
> peek_t
> solver( boxes_t boxes ){
> peek_t res;
>
> for( int i = 0; i < N_BOXES; i++ ){
> uint32_t m = 0;
> for( int k = 0; k < BOX_SIZE; k++ ){
> m |= 1u << boxes.b[i][k];
> }
> adjacent[i] = m;
> cookie_of_box[i] = -1;
> box_of_cookie[i] = -1;
> }
>
> for( int i = 0; i < N_BOXES; i++ ){
> seen = 0;
> search( i );
> }
>
> for( int i = 0; i < N_BOXES; i++ ){
> int c = cookie_of_box[i];
> for( int k = 0; k < BOX_SIZE; k++ ){
> if( boxes.b[i][k] == c ){
> res.b[i] = k;
> break;
> }
> }
> }
> return res;
> }
>
> Despite being derived independently, this code uses the same sort of
> approach that I had used, except my code was recursive rather than
> iterative.
>
> Running the above code with default settings (128 11) produced this
> output
>
> o.k.
> med=0.003542 msec, min=0.003487 msec, max=0.003911 msec
>
> The timing results for my second code effort were similar, except
> that the value for max was about 0.3 msec.
>
My defaults were chosen for much slower solutions.
For fast solutions like yours or mine with default parameters an
overhead of clock_gettime() call is too significant.
In such case it's better to use rep1 of at least 10000.
> Informal timing measurements on my original solver -- in particular
> using a different interface, and done simply by using 'time' in the
> shell to measure a million calls to the solver -- gave per-call
> times that were better by about a factor of five. I need to be
> clear that this solver does not conform to the original interface,
> and probably most of speedup is due to choosing an interface that
> gives an easier fit to the solver.
>
It's not something I'd expect.
I used "by value" type of interface both for input and for output in
order to reduce a chance of buggy solutions to mess with the test bench.
I fully expect that "by reference" type of interface could be somewhat
faster. May be, 1.5x faster for very fast solutions. But I certainly
don't expect a factor of five.
> Sorry not to have something better for you. It was a fair amount of
> work to produce the results above.
I read your code briefly, but didn't try to understand it yet.
I plugged it into my test bench and measured speed on very old home PC
(Intel i5-3450). With big values of rep1 it was ~3.3 times faster
than my original solution and ~1.9 times slower than my 2nd solution.
So, speed-wise your solution is good.
One thing that I don't particularly like after taking a glance - it
does not appear to be thread-safe. But it is probably very easy to make
it thread safe.
Another thing that I don't particularly like - if we want N_BOXES > 32
then it requires modifications; if we want N_BOXES > 64 then it
requires more serious modifications.
Now few words about my own solutions.
1. Original solution:
This solution is based on the proof that was given to me by somebody
with abstract math mind.
2. It is solution that I found independently, for which I hopefully
have a proof in the head, but I didn't write it out yet and didn't show
yet to said mathematician. It would not surprise me if idea of these
solution is the same as yours.
Later today (tonight) I plan to post both solutions here.
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