Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397621
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-16 23:52 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <86a4v26pup.fsf@linuxsc.com> (permalink) |
| References | (2 earlier) <20260408222330.00005cf8@yahoo.com> <865x5zbg10.fsf@linuxsc.com> <20260411225637.0000632e@yahoo.com> <865x5x9kbw.fsf@linuxsc.com> <20260413171129.0000003d@yahoo.com> |
Michael S <already5chosen@yahoo.com> writes:
> On Sat, 11 Apr 2026 15:57:23 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
[..some earlier back and forth..]
> Just now I paid attention that when posting last night I made a
> mistake in cut&past. It result in the post that contained the
> source code but missed text that explains what it's all about.
> So, second try.
>
> Could the code below be considered an implementation of your
> algorithm?
I'm not sure. I think it's close, but I'm having trouble being
more definite than that.
> It uses different programming technique:
> - iteration, goto and explicit stack instead of recursion
I got that.
> - loop instead of longjmp
I got that too.
> - popcount instead of maintaining 'count of boxes' field
I see that. Interesting choice.
> - free_sorts bit mask instead of list of sorts of cookies
> indexed by levels (later on I realized that this modification
> was unnecessary)
I see that you did this but I was confused about how it worked.
> I coded it in such manner because as the next step I am planning
> to add instrumentation that would be easier in iterative code than
> in the recursive one.
Yes, and surely there are other reasons to want an iterative version
rather than a recursive one.
> It seems to me that resulting search order is either exactly or at
> least approximately the same as in your description.
Exactly or at least approximately -- I'll go for that. :)
> #include <stdint.h>
> #include <string.h>
> #include <stdbool.h>
> #include <limits.h>
>
> #include "solver.h"
>
> peek_t solver(boxes_t boxes)
> {
> uint64_t boxes_of_sorts[N_BOXES] = {0};
> uint64_t sorts_of_boxes[N_BOXES];
> uint8_t b_idx[N_BOXES][N_BOXES];
> // build indices
> for (int bi = 0; bi < N_BOXES; ++bi) {
> uint64_t sorts = 0;
> for (int ci = 0; ci < BOX_SIZE; ++ci) {
> uint8_t sort = boxes.b[bi][ci];
> sorts |= (uint64_t)1 << sort;
> b_idx[bi][sort] = ci;
> boxes_of_sorts[sort] |= (uint64_t)1 << bi;
> }
> sorts_of_boxes[bi] = sorts;
> }
>
> peek_t result={0};
> uint64_t free_boxes = (uint64_t)-1 >> (64-N_BOXES);
> uint64_t free_sorts = (uint64_t)-1 >> (64-N_BOXES);
> struct stack_node {
> uint64_t free_boxes, free_sorts, boxes;
> int sel_sort;
> } stack[N_BOXES];
> int level = 0;
> do {
> // find free sort that remains in the smallest # of free boxes
> uint64_t msk = free_sorts;
> int nb_min = INT_MAX;
> int sel_sort = N_BOXES;
> while (msk) {
> int sort = __builtin_ctzll(msk);
> uint64_t boxes = boxes_of_sorts[sort] & free_boxes;
> if (boxes) {
> int nb = __builtin_popcountll(boxes);
> if (nb_min > nb) {
> nb_min = nb;
> sel_sort = sort;
> if (nb == 1)
> break;
> }
> }
> msk ^= (uint64_t)1 << sort;
> }
>
> if (sel_sort == N_BOXES)
> goto pop;
>
> // candidate sort found
> uint64_t boxes = boxes_of_sorts[sel_sort] & free_boxes;
> back:;
> int bi = __builtin_ctzll(boxes);
> result.b[bi] = b_idx[bi][sel_sort];
> boxes ^= (uint64_t)1 << bi;
> // preserve state
> stack[level] = (struct stack_node){
> .free_boxes=free_boxes, .free_sorts=free_sorts,
> .boxes=boxes, .sel_sort = sel_sort};
> // go to the next level
> free_boxes ^= (uint64_t)1 << bi;
> free_sorts ^= (uint64_t)1 << sel_sort;
> ++level;
> continue;
>
> // return to previous level
> pop:
> while (level > 0) {
> --level;
> boxes = stack[level].boxes;
> if (boxes) {
> free_boxes = stack[level].free_boxes;
> free_sorts = stack[level].free_sorts;
> sel_sort = stack[level].sel_sort;
> goto back;
> }
> }
> // should never come here
> break;
> } while (level < N_BOXES);
> return result;
> }
I'm leaving the code in even though I don't have a lot to say
about it. Trying to understand it I kept getting an internal
"complexity threshold exceeded" exception. Finally I decided I
would just try to rewrite it, preserving the spirit although not
all of the details. My code ended up being more lines of source
than yours although the core routine is shorter. There are three
parts that I broke out into separate functions (not shown). Those
parts are, one, a function 'bsets_from_boxes()' to turn a boxes_t
into a collection of bitsets holding the boxes corresponding to
each cookie type; two, a function 'best_next_ctype()' that
chooses which cookie type to consider next; and three, a final
function 'answer()' to turn the 'box_chosen[]' bitset array into
the representation needed by the interface. Here is the central
routine:
peek_t
solver( boxes_t box_contents ){
Bset boxes_free[ COOKIE_LIMIT + 1 ];
Ctype ctypes[ COOKIE_LIMIT ];
Bset boxes_to_try[ COOKIE_LIMIT ];
Bset box_chosen[ COOKIE_LIMIT ];
Bsets bsets = bsets_from_boxes( &box_contents );
Index depth = 0;
Bset free = boxes_free[0] = ~((Bset){-1} << COOKIE_LIMIT-1 << 1);
for( Index i = 0; i < LIMIT_OF( ctypes ); i++ ) ctypes[i] = i;
do {
Ctype ctype = best_next_ctype( depth, free, &bsets, ctypes );
Bset chosen;
boxes_to_try[depth] = bsets.bset_of_ctype[ ctype ] & free;
while(
chosen = boxes_to_try[depth],
boxes_to_try[depth] ^= chosen ^= chosen & chosen-1,
!chosen
){
assert( depth > 0 ), --depth;
free = boxes_free[ depth ];
ctype = ctypes[ depth ];
}
box_chosen[ ctype ] = chosen;
assert( free & chosen );
boxes_free[ depth+1 ] = free = free ^ chosen;
} while( ++depth < COOKIE_LIMIT );
return answer( box_chosen, ctypes, &box_contents );
}
Two further comments.
One, by keeping the box_chosen[] array as bit masks, the use of
the __builtin bit function gets deferred and so is done only once
for each output slot, at the end (in the 'answer()' function).
Two, the function 'best_next_ctype()' manipulates the ctypes[]
array as well as returning the cookie type at the appropriate
depth in the array. I tried different policies for when to
select the "best" cookie type, including "always", "never", and
"only for the first N levels", with several choices of N.
Different policies produced different timing values but there
wasn't any obvious relation between them. Something that
occurred to me only later is a policy "choose the best out of the
next K cookie types", for different values of K.
The main thing is I hope the above routine does a better job of
conveying my thoughts and understandings.
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