Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397517
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-13 17:11 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260413171129.0000003d@yahoo.com> (permalink) |
| References | (1 earlier) <86tstlwjak.fsf@linuxsc.com> <20260408222330.00005cf8@yahoo.com> <865x5zbg10.fsf@linuxsc.com> <20260411225637.0000632e@yahoo.com> <865x5x9kbw.fsf@linuxsc.com> |
On Sat, 11 Apr 2026 15:57:23 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Thu, 09 Apr 2026 21:22:51 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> 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.
> >
> > I need clarification for the last step.
>
> Here is a mixture of C code and pseudocode. A SolveState is an
> array, one element for each cookie type.
>
>
> Answer
> solve( SolveState *problem ){
> Answer answer;
> jmp_buf found;
> if( seek( &answer, found, problem ) ) return answer;
>
> printf( "No joy\n" );
> exit(0);
> }
> /* Note that seek() returns true if and only if a longjmp() was done.
> */
>
>
> _Bool
> seek( Answer *answer, jmp_buf found, SolveState *problem ){
> if( setjmp( found ) ) return true;
> return look( answer, found, 0, problem );
> }
> /* The call to look() after the if() starts the search going. */
> /* If an answer is found, a longjmp() will go back to the 'return
> true;' */
>
>
> _Bool
> look( Answer *answer, jmp_buf found, Index level, SolveState *in ){
> SolveState work;
> ...
>
> if( level == COOKIE_LIMIT ) longjmp( found, 1 );
>
> ... ignoring the "optimization" step of choosing the best cookie
> ...
>
> for each box B in in->cookies[level] {
> remember box B for the cookie in->cookies[level], in *answer
> copy in->cookies[ level+1 .. COOKIE_LEVEL ) to work
> remove B from each work.cookies[ level+1 .. COOKIE_LEVEL )
> look( out, found, level+1, &work );
> }
>
> return false;
> }
> /* Note that 'true' is never returned by this function. */
> /* If there are more boxes to try for the current cookie, recurse. */
> /* When there are no more boxes to try, return false. */
> /* If/when all of the cookies have been assigned, longjmp() */
> /* Doing a longjmp() will cause seek() to return true. */
>
>
> The notation ...cookies[ level+1 .. COOKIE_LEVEL ) is an implied
> for() loop.
>
> Now for your questions...
>
> > What exactly do we do after our fist guess failed?
>
> If you mean the first box for the current cookie, go on to the
> next box for that cookie.
>
> If you mean all the boxes for the current cookie failed, simply
> return.
>
> If you mean all the boxes for the cookie on the first level, simply
> return, which will cause an outer call to fail irrevocably. Under
> the conditions of the problem, this never happens, if the code has
> been written correctly.
>
> > Supposedly continue to the next sort of cookies that has the same #
> > of boxes as the one we just tried.
> > But what we do after that? Do we have to try cookies with higher
> > number of boxes?
>
> No. At each level there is exactly one cookie to try, and we try
> each of the boxes that cookie might be taken from (at this point in
> the search); if none of those boxes work, backtrack -- which is to
> say, return to the next outer level.
>
> > If yes, does it apply in case when cookies that we tried before had
> > just one box?
>
> At each level, we are never concerned with the cookie choices that
> were made at previous levels (which means a smaller level index)
> as those choices are "frozen" for this part of the search.
>
> I hope these answers clear up what you're looking for.
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?
It uses different programming technique:
- iteration, goto and explicit stack instead of recursion
- loop instead of longjmp
- popcount instead of maintaining 'count of boxes' field
- free_sorts bit mask instead of list of sorts of cookies indexed by
levels (later on I realized that this modification was unnecessary)
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.
It seems to me that resulting search order is either exactly or at
least approximately the same as in your description.
#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;
}
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