Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397513
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-13 02:03 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260413020328.0000615b@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.
#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