Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397532
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-15 02:15 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260415021526.000047e2@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:
>
> 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.
>
I finally looked closer to the code of your friend.
To me, it does not look at all similar to description of "your"
algorithm in your other post.
It appears more similar to my 2nd algorithm, but sort of orthogonal to
it - my outermost loop iterate through sorts of cookies; in the code of
your friend outermost loop iterate through boxes.
Another difference, less important for robustness, more important for
measured speed, esp. on avearge, is when search decides to revert
previous selection. I am doing it only after all possibilities to
select at the top level failed. Your friend makes no such effort and
easily dives deep. In principle, both approaches are equivalent, but in
physical world recursive call is significantly slower than iteration of
simple loop and excessive updates of state variables are also slower
then lookups without updates.
And, of course, apart from difference in algorithm there is a
significant difference in implementation technique. Your friend took
advantage of the fact that the challenge was specified for relatively
small number of boxes and intensely used bit masks. I [didn't took
similar advantage [except for using byte variables instead of short or
int] and used arrays. Of course, the technique applied by your friend
is faster. His solution ended up ~2 times slower then mine not because
of technique, but because of algorithmic difference mentioned in
previous paragraph.
Today I modified his code, applying variant of the same algorithmic
change. At the same opportunity I removed use of static data and
increased size of bit masks to 64 bits. As expected, resulting code was
very fast, ~3 times faster than my own.
Here is a code:
// Modification of code of friend of Tim Rentsch
#include <stdint.h>
#include "solver.h"
typedef struct {
uint64_t cookies_in_box[ N_BOXES ]; // helper index, constant after
init uint64_t selected;
uint8_t box_of_cookie [ N_BOXES ]; // valid for selected sorts
} state_t;
// return 0 on success, seen mask on failure
static uint64_t search(state_t* s, int b, uint64_t seen)
{
uint64_t m = s->cookies_in_box[b] & ~seen;
if (m & ~s->selected) {
int c = __builtin_ctzll(m & ~s->selected);
s->box_of_cookie[c] = b;
s->selected |= 1ull << c;
return 0; // success
}
while( m ){
int c = __builtin_ctz(m);
seen = search(s, s->box_of_cookie[c], seen | (1ull << c));
if (seen == 0) {
s->box_of_cookie[c] = b;
return 0; // success
}
m &= ~seen;
}
return seen;
}
peek_t
solver( boxes_t boxes ){
state_t s;
for (int i = 0; i < N_BOXES; i++) {
uint64_t m = 0;
for (int k = 0; k < BOX_SIZE; k++)
m |= 1ull << boxes.b[i][k];
s.cookies_in_box[i] = m;
}
s.selected = 0;
for( int i = 0; i < N_BOXES; i++ )
search(&s, i, 0);
// translate result from box_of_cookie[] to index of cookie in box
peek_t res;
for (int c = 0; c < N_BOXES; ++c) {
int b = s.box_of_cookie[c];
for( int k = 0; k < BOX_SIZE; k++ ){
if (boxes.b[b][k] == c) {
res.b[b] = k;
break;
}
}
}
return res;
}
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