Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #397628
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-17 17:04 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260417170444.000020da@yahoo.com> (permalink) |
| References | <20260401163447.000052de@yahoo.com> <86tstlwjak.fsf@linuxsc.com> <20260415021526.000047e2@yahoo.com> <86mrz36xdf.fsf@linuxsc.com> |
On Thu, 16 Apr 2026 02:57:32 -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:
> >
> >> 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.
>
> I confess I didn't look closely at the algorithm but relied
> on comments about how the code worked. I tried to express
> this in my earlier posting when I said "the same sort of
> approach" rather than "the same approach". Sorry for any
> confusion.
>
> > 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. [...code...]
>
> I'm happy to hear the posting provided an opportunity to more deeply
> explore the problem. Also it's interesting to learn the results of
> your investigations; thank you for those.
I was aware of possibility of taking advantage of the fact that value
of N_BOXES specified in the challenge is <= than dominant width of
machine word.
I intentionally avoided it until this point, for two reasons, one
abstract (A) and one practical (P).
A. the challenge was meant to be algorithmic with lesser emphasis on
implementation
P. I planned (and still plan) experimental testing of BigO
But I couldn't resist the appeal of fast :(
The achieved 3x speed up was actually disappointing. I expected more.
It seems, by now building helper indices takes more time than solver
itself, which makes further progress in this part pointless.
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