Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397461
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-09 21:22 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <865x5zbg10.fsf@linuxsc.com> (permalink) |
| References | <20260401163447.000052de@yahoo.com> <86tstlwjak.fsf@linuxsc.com> <20260408222330.00005cf8@yahoo.com> |
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.
>> 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.
>> 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.
> 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
> 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.
I don't really understand that code yet, but it looks like your
code is a bit fancier than mine (the code that wasn't posted
because it uses a different interface).
> Later today (tonight) I plan to post both solutions here.
Here is an outline of the first (non-interface-compatible) code that
I wrote.
Use a straightforward backtracking scheme. Make a choice at the
current level, and do a recursive call to try the next level. If
the next level returns, it failed, so go on to the next choice at
this level and call again.
The output value is an array (passed recursively via pointer) with
either a cookie type for each box or a box number for each cookie
type (I don't remember which). This array is filled in as the
recursive backtrack progresses.
The whole search is started by doing a setjmp() before the call to
the top level. If the search succeeds, a longjmp() is done to
deliver an answer. That means that if the call to the top level
returns then the search was a failure. The central recursive
function has four parameters:
an Answer *'out', to hold the solution
a jmp_buf 'found', for a longjmp() when a full answer is found
a counter/index to reflect search depth (starting 0, 20 means done)
a "solution state" to direct the search (conceptually by value)
The "solution state" is at the heart of the algorithm. It's a
structure holding an array of 20 "cookie values", where a cookie
value is represented by an unsigned 64-bit int. The bits are
used as follows:
low six bits: the cookie type
next 52 bits: a "box mask", indicating at least one cookie of
this type in the corresponding box (so up to 52
boxes)
upper bits: count of boxes (ie, number of ones in the box mask)
The cookie type is important when storing a partial result in the
answer, not at any other time.
The box mask is important to know which boxes to try during the
backtracking.
The count of boxes is important to help guide the backtracking, in a
way that we hope will get an answer faster.
At each level of recursion, do the following:
If the search depth is the number of boxes, longjmp()
Next find the cookie of cookies in the solution state at or
above this level that has the smallest number of boxes. Because
the box count is held in the uppermost bits the 64-bit values can
simply be directly compared, without any masking. Move that
cookie to the array location corresponding to the current depth
(and put the cookie that was there in the hole left by doing the
move).
For each box in the box mask of that cookie, try selecting that
box for this cookie, which means:
copy the state of cookies above this level to a new solution
state, so the changed solution state described above can be
left alone
for each of those cookies, if the cookie has the "selected box"
set in its box mask, clear the bit and reduce the box count
by one. (again since the box count is held in high order bits
this count can be reduced by just subtracting a scaled one
value.)
recurse to continue searching at the next level
If we run out of boxes to check, just return; continue trying
alternatives at the next level up, if there is one.
I think that's it. I hope it makes sense.
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