Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397495
| Path | csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail |
|---|---|
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | Sat, 11 Apr 2026 15:57:23 -0700 |
| Organization | A noiseless patient Spider |
| Lines | 169 |
| Message-ID | <865x5x9kbw.fsf@linuxsc.com> (permalink) |
| References | <20260401163447.000052de@yahoo.com> <86tstlwjak.fsf@linuxsc.com> <20260408222330.00005cf8@yahoo.com> <865x5zbg10.fsf@linuxsc.com> <20260411225637.0000632e@yahoo.com> |
| MIME-Version | 1.0 |
| Content-Type | text/plain; charset=us-ascii |
| Injection-Date | Sat, 11 Apr 2026 22:57:26 +0000 (UTC) |
| Injection-Info | dont-email.me; posting-host="21f9f6d525ecd04de8977c5f6117a238"; logging-data="2279808"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/E2I6vT9hEwm82sG6gO1AxF3ZTg9AGl3E=" |
| User-Agent | Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) |
| Cancel-Lock | sha1:u4F2BroBs7bEpRHswVwddr3p8yw= sha1:7TALY0Ag3hU5Gw8pprpvYEJ79+k= |
| Xref | csiph.com comp.lang.c:397495 |
Show key headers only | View raw
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.
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