Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397623
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-17 14:44 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260417144410.00006d46@yahoo.com> (permalink) |
| References | (3 earlier) <865x5zbg10.fsf@linuxsc.com> <20260411225637.0000632e@yahoo.com> <865x5x9kbw.fsf@linuxsc.com> <20260413171129.0000003d@yahoo.com> <86a4v26pup.fsf@linuxsc.com> |
On Thu, 16 Apr 2026 23:52:14 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> 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.
>
I'd guess that every regular c.l.c reader knows that you like guessing
games. Even if I don't think that it is appropriate here, up to the
certain limit, I am willing to participate.
It's pretty easy to guess that the code above preceded by:
#include <assert.h>
#include "solver.h"
typedef uint64_t Bset;
typedef uint8_t Ctype;
typedef size_t Index;
enum { COOKIE_LIMIT = N_BOXES };
typedef struct {
Bset bset_of_ctype[COOKIE_LIMIT];
// more fields? I can't tell
} Bsets;
#define LIMIT_OF(x) (sizeof(x)/sizeof(x[0]))
static Bsets bsets_from_boxes(const boxes_t* );
static Ctype best_next_ctype(Index, Bset, Bsets*, Ctype* );
static peek_t answer(const Bset box_chosen[], const Ctype ctypes[],
const boxes_t* boxes);
It's also easy to guess that bsets_from_boxes contains following code:
static Bsets bsets_from_boxes(const boxes_t* boxes)
{
Bsets ret={0};
for (Index bi = 0; bi < N_BOXES; ++bi) {
for (int ci = 0; ci < BOX_SIZE; ++ci)
ret.bset_of_ctype[boxes->b[bi][ci]] |= (Bset)1 << bi;
}
return ret;
}
But quite possibly there is more code.
I am far less certain about answer(). In particular, I have no idea why
it needs its 2nd parameter. My guess is that it's something like that:
static
peek_t answer(const Bset box_chosen[], const Ctype unused[],
const boxes_t* boxes)
{
peek_t ret;
for (int i = 0; i < COOKIE_LIMIT; ++i) {
int bi = __builtin_ctzll(box_chosen[i]);
for (int ci = 0; ; ++ci)
if (boxes->b[bi][ci] == i) {
ret.b[bi] = ci;
break;
}
}
return ret;
}
However I both can not and don't want to guess the content of your
cores routine best_next_ctype(). And without it I don't have much to
say about you solution.
> The main thing is I hope the above routine does a better job of
> conveying my thoughts and understandings.
It looks like unlike your friend you missed the key - equity of number
of boxes and number of sorts of cookies is not accidental! It's the
most important thing in the whole exercise. It's what make solution
feasible for much bigger values of N_BOXES, probably up to several K
in less than 1 sec.
But, then again, without source code of best_next_ctype() I can not be
sure about it.
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