Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397463
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-10 12:23 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260410122314.000063c5@yahoo.com> (permalink) |
| References | <20260401163447.000052de@yahoo.com> <86tstlwjak.fsf@linuxsc.com> <20260408222330.00005cf8@yahoo.com> <865x5zbg10.fsf@linuxsc.com> |
On Thu, 09 Apr 2026 21:22:51 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > 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.
>
> These source lines
>
> struct timespec t0;
> clock_gettime(CLOCK_MONOTONIC, &t0);
>
> produced these diagnostics
>
> tb.c:134:21: error: storage size of 't0' isn't known
> tb.c:135:5: warning: implicit declaration of function
> 'clock_gettime' [...] tb.c:135:19: error: 'CLOCK_MONOTONIC'
> undeclared (first use in this function)
>
> under -std=c99. Apparently the first diagnostic, about
> struct timespec, is fixed under -std=c11. It wasn't hard
> to fix these, but it was irksome.
>
Sounds like under Linux and with -std=c99 flag function clock_gettime()
and related structures and constants are not declared/defined by default
in time.h.
Man page suggests magic pixie dust:
#define _XOPEN_SOURCE 600
#include <time.h>
#include <unistd.h>
If you ask why I used clock_gettime() instead of C standard
timespec_get() then the answer is that on Windows, eps. on older
versions like Win7 and WS2008 (which I prefer over newer stuff for
reasons unrelated to quality of C RTL), precision of timespec_get() is
poor. clock_gettime(CLOCK_MONOTONIC,) is much better.
> >> 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.
>
> Yes, that is in fact what I was thinking. Fortunately the difficulty
> was resolved when the checker reported a value out of range.
>
> >> 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.
>
> It turns out that running with a larger number of trials didn't
> change the results much. I think my averages got a bit worse and my
> worst case got a bit better, but as I recall the difference wasn't
> anything dramatic.
>
After testing on another (Windows) systems I have to admit that my
objections about default value of rep1 applies only to Win7. Even on
Ws2008, which is almost the same kernel, overhead of clock_gettime() is
sufficiently low for rep1=128 to give fair measurements.
> >> 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.
>
> I will try to explain below.
>
> >> 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 need to say again that the code I posted was not code that I wrote.
> The approach used is similar to code I did write, but the actual code
> is quite a bit different.
>
> > 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.
>
> Do you mean because it is using (and changing) global objects? Yes
> that is a drawback.
>
Yes.
> > 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.
>
> As it turns out my code handles N_BOXES up to 52. You may laugh
> when you see why.
>
> > 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.
>
> Yes, I posted a comment about that
>
<snip the rest, will respond later >
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