Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #397345 > unrolled thread
| Started by | Michael S <already5chosen@yahoo.com> |
|---|---|
| First post | 2026-04-01 16:34 +0300 |
| Last post | 2026-04-17 20:17 +0200 |
| Articles | 20 on this page of 78 — 10 participants |
Back to article view | Back to comp.lang.c
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
Page 3 of 4 — ← Prev page 1 2 [3] 4 Next page →
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-11 04:27 -0700 |
| Message-ID | <86mrz9ag91.fsf@linuxsc.com> |
| In reply to | #397468 |
Michael S <already5chosen@yahoo.com> writes: > On Thu, 09 Apr 2026 21:22:51 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: (just a few short replies) >> [...] >> >> 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. > > Is it proven that this step helps? > To me it sounds unnecessary. My experience with backtracking algorithms tells me that selecting a path where the number of possible choices is smallest usually does a better job of finding a solution quickly. >> [...] >> >> I think that's it. I hope it makes sense. > > It makes sense, but it looks to me as solution by exhausting, augmented > by "smallest number of boxes" heuristic. > It's not obvious [to me] without further thinking that the worst case is > not very slow. Several short responses. I think "by exhaustion" is usually taken to mean an unguided exploration of all alternatives, even ones that aren't plausible. Backtracking isn't that. Backtracking is recognized as a viable search strategy in lots of different kinds of problems, including problems that are known to be NP complete. It has a good pedigree. My goals in writing the program were to write a program that is understandable, that does find solutions, and that has reasonable performance. Since the program did find answers and also met your stated performance goals, I have no reason to be dissatisfied.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-11 22:56 +0300 |
| Message-ID | <20260411225637.0000632e@yahoo.com> |
| In reply to | #397461 |
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. What exactly do we do after our fist guess failed? 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? If yes, does it apply in case when cookies that we tried before had just one box?
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-11 15:57 -0700 |
| Message-ID | <865x5x9kbw.fsf@linuxsc.com> |
| In reply to | #397492 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-12 02:15 +0300 |
| Message-ID | <20260412021543.00001186@yahoo.com> |
| In reply to | #397495 |
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.
It iterates differently from what I thought it does.
I should digest a new information. Not tonight.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-13 02:03 +0300 |
| Message-ID | <20260413020328.0000615b@yahoo.com> |
| In reply to | #397495 |
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;
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-13 17:11 +0300 |
| Message-ID | <20260413171129.0000003d@yahoo.com> |
| In reply to | #397495 |
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;
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-16 23:52 -0700 |
| Message-ID | <86a4v26pup.fsf@linuxsc.com> |
| In reply to | #397517 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-17 14:44 +0300 |
| Message-ID | <20260417144410.00006d46@yahoo.com> |
| In reply to | #397621 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-17 07:40 -0700 |
| Message-ID | <865x5p7ir6.fsf@linuxsc.com> |
| In reply to | #397623 |
Michael S <already5chosen@yahoo.com> writes:
> On Thu, 16 Apr 2026 23:52:14 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
[...]
> 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.
I posted what I did because I wanted the focus to be on reading the
code and not on running the code. I was hoping that understanding
would be feasible without needing any guessing.
> It's pretty easy to guess that the code above preceded by:
>
> [...]
Looks reasonable.
> 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.
Here is one implementation of best_next_ctype():
Ctype
best_next_ctype( Index depth, Bset free, Bsets *bsets, Ctype ctypes[] ){
// permute?
return ctypes[depth];
}
At the "permute?" comment an implementation could perform any
permutation of the elements of the ctypes[] array, within the range
of ctypes[depth] and ctypes[COOKIE_LIMIT-1], and the result should
still be a working solution. Or just leave it as a comment. The
correctness of the code doesn't depend on what permutation is done
or how the choice is made.
>> 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!
The way the code is written it allows the value of COOKIE_LIMIT to
be chosen independently of the value of N_BOXES (or at least I hope
it does). I didn't explore any such cases but it might be
interesting to do that.
> 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.
Of course for the code posted the value of N_BOXES must be no more
than the number of bits in the bitset type Bset (which is meant to
be short for "Box set", or a set of box values).
> But, then again, without source code of best_next_ctype() I can not be
> sure about it.
My questions are these. One, could you understand what the code is
doing and how it works? And two, if given an appropriate choice of
what permutation is done in best_next_ctype(), does this code do the
same thing as your code? I was trying to match the behavior of your
code but I wasn't able to figure out how it decided where to go
next.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-17 18:30 +0300 |
| Message-ID | <20260417183017.000011ba@yahoo.com> |
| In reply to | #397630 |
On Fri, 17 Apr 2026 07:40:13 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Thu, 16 Apr 2026 23:52:14 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
> [...]
>
> > 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.
>
> I posted what I did because I wanted the focus to be on reading the
> code and not on running the code. I was hoping that understanding
> would be feasible without needing any guessing.
>
> > It's pretty easy to guess that the code above preceded by:
> >
> > [...]
>
> Looks reasonable.
>
> > 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.
>
> Here is one implementation of best_next_ctype():
>
> Ctype
> best_next_ctype( Index depth, Bset free, Bsets *bsets, Ctype ctypes[]
> ){ // permute?
> return ctypes[depth];
> }
>
> At the "permute?" comment an implementation could perform any
> permutation of the elements of the ctypes[] array, within the range
> of ctypes[depth] and ctypes[COOKIE_LIMIT-1], and the result should
> still be a working solution. Or just leave it as a comment. The
> correctness of the code doesn't depend on what permutation is done
> or how the choice is made.
>
> >> 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!
>
> The way the code is written it allows the value of COOKIE_LIMIT to
> be chosen independently of the value of N_BOXES (or at least I hope
> it does). I didn't explore any such cases but it might be
> interesting to do that.
>
> > 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.
>
> Of course for the code posted the value of N_BOXES must be no more
> than the number of bits in the bitset type Bset (which is meant to
> be short for "Box set", or a set of box values).
>
> > But, then again, without source code of best_next_ctype() I can not
> > be sure about it.
>
> My questions are these. One, could you understand what the code is
> doing and how it works? And two, if given an appropriate choice of
> what permutation is done in best_next_ctype(), does this code do the
> same thing as your code? I was trying to match the behavior of your
> code but I wasn't able to figure out how it decided where to go
> next.
No, as it is, it does not match the behavior of my code or of code of
your friend. One very simple, but very important element of search state
is missing.
I am reasonably sure that it can not be emulated by permutation of
ctypes array within best_next_ctype() routine.
As to observed timing, if your code is run for big number of cases, e.g.
rep1=128, rep2=9999 (small modification of test bench required to enable
bigger rep2), it sometimes ends up very slow. My test bench is not well
suited to find exactly how slow, but my guess is above 0.1 sec. That's
very different from mine or your friends, where difference between
median and worst case is small, likeley less than 3x.
More convenient test bench that reports PRNG and can take PRNG seed as
input:
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
#include "solver.h"
static int test(boxes_t* boxes, peek_t* results, int rep1, int rep2,
uint64_t* prngs, uint64_t seed);
int main(int argz, char** argv)
{
int rep1=128, rep2=11;
unsigned long long seed = 1;
if (argz > 1) {
if (strcmp(argv[1], "?")== 0 ||
strcmp(argv[1], "-?")== 0) {
fprintf(stderr,
"Usage:\n"
"greg_solver_tb [rep1 [rep2]] -s=seed\n"
"where\n"
"rep1 - number of solver calls in one time measurement set.
Default 128\n"
"rep2 - number of repetitions of time measurement. Default 11\n"
"seed - PRNG seed\n"
);
return 0;
}
static const int mx[2] = { 1e7, 10000 };
for (int arg_i = 1, val_i = 0; arg_i < 4 && arg_i < argz; ++arg_i) {
char* arg = argv[arg_i];
if (strncmp(arg, "-s=", 3)== 0) {
char* seedstr = arg+3;
char* endp;
seed = strtoull(seedstr, &endp, 0);
if (endp == seedstr) {
fprintf(stderr, "seed argument '%s' is not a number\n",
seedstr);
return 1;
}
} else {
char* endp;
long long n = strtoll(arg, &endp, 0);
if (endp == arg) {
fprintf(stderr, "argument '%s' is not a number\n", arg);
return 1;
}
int n_mx = mx[val_i];
if (n < 1 || n > n_mx) {
fprintf(stderr, "argument '%s' out of range. Please specify
value in range[1:%d]\n"
, arg, n_mx);
return 1;
}
if (val_i==0)
rep1 = n;
else
rep2 = n;
++val_i;
}
}
}
void* mem =
malloc((sizeof(boxes_t)+sizeof(peek_t)+sizeof(uint64_t))*rep1);
if (!mem) {
perror("malloc()");
return 1;
}
uint64_t* prngs = mem;
boxes_t* boxes = (boxes_t*)&prngs[rep1];
peek_t* results = (peek_t*)&boxes[rep1];
int ret = test(boxes, results, rep1, rep2, prngs, seed);
free(mem);
return ret;
}
static uint32_t my_prng(uint64_t* pState)
{
// we don't need very good PRNG,
// but it has to repeatable cross-platform,
// so C RTL rand() is not suitable
const uint64_t PRNG_A = 2862933555777941757ull;
const uint64_t PRNG_C = 20260329ull;
uint64_t s = *pState*PRNG_A + PRNG_C;
*pState = s;
return s >> 32;
}
static void make_random_boxes(boxes_t* dst, uint64_t* prng)
{
uint8_t pool[N_BOXES*BOX_SIZE];
for (int i = 0; i < N_BOXES; ++i)
for (int k = 0; k < BOX_SIZE; ++k)
pool[i*BOX_SIZE+k] = i;
for (int i = 0; i < N_BOXES; ++i) {
for (int k = 0; k < BOX_SIZE; ++k) {
uint32_t rnd = my_prng(prng);
int idx0 = i*BOX_SIZE+k;
int idx1 = ((N_BOXES*BOX_SIZE-idx0)*(uint64_t)rnd >> 32)+idx0;
uint8_t v0 = pool[idx0];
uint8_t v1 = pool[idx1];
dst->b[i][k] = v1;
pool[idx1] = v0;
}
}
}
static bool validate(const boxes_t* bx, const peek_t* res)
{
bool cookies[N_BOXES]={0};
for (int i = 0; i < N_BOXES; ++i) {
unsigned v = res->b[i];
if (v >= BOX_SIZE) {
fprintf(stderr, "res[%d] = %d. Out of range!\n", i, v);
return false;
}
unsigned c = bx->b[i][v];
if (cookies[c]) {
fprintf(stderr, "res[%d] = %d. bx[%d][%d]=%d repeated.\n"
, i, v
, i, v, c);
return false;
}
cookies[c] = true;
}
return true;
}
static int cmp_ll(const void* pa, const void* pb) {
long long a = *(const long long*)pa;
long long b = *(const long long*)pb;
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
static int test(boxes_t* boxes, peek_t* results, int rep1, int rep2,
uint64_t* prngs, uint64_t seed)
{
uint64_t prng = seed;
long long dt[rep2];
long long mn, mx;
uint64_t mn_prng, mx_prng;
for (int it = 0; it < rep2; ++it) {
for (int i = 0; i < rep1; ++i) {
prngs[i] = prng;
make_random_boxes(&boxes[i], &prng);
}
struct timespec t0;
clock_gettime(CLOCK_MONOTONIC, &t0);
for (int i = 0; i < rep1; ++i)
results[i] = solver(boxes[i]);
struct timespec t1;
clock_gettime(CLOCK_MONOTONIC, &t1);
long long delta_t = (t1.tv_sec-t0.tv_sec)*(long long)1e9+
t1.tv_nsec-t0.tv_nsec;
dt[it] = delta_t;
if (it == 0 || mn > delta_t) {
mn = delta_t;
mn_prng = prngs[0];
}
if (it == 0 || mx < delta_t) {
mx = delta_t;
mx_prng = prngs[0];
}
for (int i = 0; i < rep1; ++i) {
if (!validate(&boxes[i], &results[i])) {
fprintf(stderr,
"Test fail at iteration %d,%d. prng %llu\n"
,it, i, prngs[i]);
fprintf(stderr, "boxes:\n");
for (int bi = 0; bi < N_BOXES; ++bi) {
for (int k = 0; k < BOX_SIZE; ++k)
fprintf(stderr, " %2d", boxes[i].b[bi][k]);
fprintf(stderr, " : %d => %2d\n"
, results[i].b[bi]
, boxes[i].b[bi][results[i].b[bi]]);
}
return 1;
}
}
}
qsort(dt, rep2, sizeof(*dt), cmp_ll);
long long med = dt[rep2/2];
double scale = 1e-6/rep1;
printf("o.k.\nmed=%.6f msec. min=%.6f msec, prng %llu. max=%.6f msec,
prng %llu.\n"
, med*scale
, mn*scale, mn_prng
, mx*scale, mx_prng
);
return 0;
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-20 00:43 +0300 |
| Message-ID | <20260420004318.000007dd@yahoo.com> |
| In reply to | #397630 |
On Fri, 17 Apr 2026 07:40:13 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
> My questions are these. One, could you understand what the code is
> doing and how it works? And two, if given an appropriate choice of
> what permutation is done in best_next_ctype(), does this code do the
> same thing as your code? I was trying to match the behavior of your
> code but I wasn't able to figure out how it decided where to go
> next.
Here is the simplest form of the algorithm that I can come with.
Essentially, it is a serial non-recursive variant of the code of your
friend with no algorithmic or technical enhancements.
Even in this form it is not slow and hopefully makes the key idea more
obvious.
#include <stdint.h>
#include <stdbool.h>
#include "solver.h"
peek_t
solver( boxes_t boxes ){
uint8_t box_of_cookie[N_BOXES]; // valid for selected sorts
for (int i = 0; i < N_BOXES; i++)
box_of_cookie[i] = N_BOXES; // value N_BOXES marks unselected sort
// Selection proceeds in progressive steps.
// At each step we select one new box and one new sort.
// A box and a sort selected at step i are never unselected later
// although association between selected boxes and sorts
// can be changed
for (int step = 0; step < N_BOXES; ++step) {
typedef struct {
uint8_t box, sort;
} trace_t;
trace_t levels[N_BOXES];
bool seen[N_BOXES] = {0};
for (int lvl = 0, box = step; ;) {
// look for unseen sort in box
int sort;
for (int ci = 0; ci < BOX_SIZE; ++ci) {
sort = boxes.b[box][ci];
if (!seen[sort])
break;
}
if (seen[sort]) { // no unseen sorts in box
box = levels[--lvl].box; // return to previous level
continue;
}
// Unseen sort found
// It will become a new selection for box
int selected_box = box_of_cookie[sort];
if (selected_box == N_BOXES) {
// sort unselected.
// it means that search at step i succeed
// commit preserved assignments
for (int k = 0; k < lvl; ++k)
box_of_cookie[levels[k].sort] = levels[k].box;
// assign new sort
box_of_cookie[sort] = box;
break;
}
// sort already selected
// Save new assignment for sort.
// Saved box also serves us if we return
// to the current level from above
levels[lvl++] = (trace_t){ .sort=sort, .box=box};
// Mark sort as seen.
// That mark guarantees forward progress of the search
seen[sort] = true;
// Continue search.
// At the next level we will look for new selection
// for old box of sort
box = selected_box;
}
}
// translate result from box_of_cookie[] to index of cookie in box
peek_t res;
for (int c = 0; c < N_BOXES; ++c) {
int b = box_of_cookie[c];
for (int k = 0; k < BOX_SIZE; ++k) {
if (boxes.b[b][k] == c) {
res.b[b] = k;
break;
}
}
}
return res;
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-21 20:37 +0300 |
| Message-ID | <20260421203728.00003035@yahoo.com> |
| In reply to | #397683 |
On Mon, 20 Apr 2026 00:43:18 +0300
Michael S <already5chosen@yahoo.com> wrote:
> On Fri, 17 Apr 2026 07:40:13 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
> >
> > My questions are these. One, could you understand what the code is
> > doing and how it works? And two, if given an appropriate choice of
> > what permutation is done in best_next_ctype(), does this code do the
> > same thing as your code? I was trying to match the behavior of your
> > code but I wasn't able to figure out how it decided where to go
> > next.
>
> Here is the simplest form of the algorithm that I can come with.
> Essentially, it is a serial non-recursive variant of the code of your
> friend with no algorithmic or technical enhancements.
> Even in this form it is not slow and hopefully makes the key idea more
> obvious.
>
>
> #include <stdint.h>
> #include <stdbool.h>
> #include "solver.h"
>
> peek_t
> solver( boxes_t boxes ){
> uint8_t box_of_cookie[N_BOXES]; // valid for selected sorts
> for (int i = 0; i < N_BOXES; i++)
> box_of_cookie[i] = N_BOXES; // value N_BOXES marks unselected sort
>
> // Selection proceeds in progressive steps.
> // At each step we select one new box and one new sort.
> // A box and a sort selected at step i are never unselected later
> // although association between selected boxes and sorts
> // can be changed
> for (int step = 0; step < N_BOXES; ++step) {
> typedef struct {
> uint8_t box, sort;
> } trace_t;
> trace_t levels[N_BOXES];
> bool seen[N_BOXES] = {0};
> for (int lvl = 0, box = step; ;) {
> // look for unseen sort in box
> int sort;
> for (int ci = 0; ci < BOX_SIZE; ++ci) {
> sort = boxes.b[box][ci];
> if (!seen[sort])
> break;
> }
> if (seen[sort]) { // no unseen sorts in box
> box = levels[--lvl].box; // return to previous level
> continue;
> }
> // Unseen sort found
> // It will become a new selection for box
> int selected_box = box_of_cookie[sort];
> if (selected_box == N_BOXES) {
> // sort unselected.
> // it means that search at step i succeed
> // commit preserved assignments
> for (int k = 0; k < lvl; ++k)
> box_of_cookie[levels[k].sort] = levels[k].box;
> // assign new sort
> box_of_cookie[sort] = box;
> break;
> }
>
> // sort already selected
> // Save new assignment for sort.
> // Saved box also serves us if we return
> // to the current level from above
> levels[lvl++] = (trace_t){ .sort=sort, .box=box};
> // Mark sort as seen.
> // That mark guarantees forward progress of the search
> seen[sort] = true;
> // Continue search.
> // At the next level we will look for new selection
> // for old box of sort
> box = selected_box;
> }
> }
>
> // translate result from box_of_cookie[] to index of cookie in box
> peek_t res;
> for (int c = 0; c < N_BOXES; ++c) {
> int b = box_of_cookie[c];
> for (int k = 0; k < BOX_SIZE; ++k) {
> if (boxes.b[b][k] == c) {
> res.b[b] = k;
> break;
> }
> }
> }
> return res;
> }
>
>
>
And here is somewhat less simple variant. It is not necessarily easy to
follow by itself, but if one studied the code above then enhancements
made here are rather obvious.
What is interesting about it is that despite absence of 'parallel'
tricks this variant is the fastest that I measured so far!
#include <stdint.h>
#include <stdbool.h>
#include "solver.h"
peek_t
solver( boxes_t boxes ){
uint8_t box_of_cookie[N_BOXES]; // valid for selected sorts
for (int i = 0; i < N_BOXES; i++)
box_of_cookie[i]=N_BOXES;// value N_BOXES marks unselected sort
uint8_t ci_min[N_BOXES];
// all cookies [0:ci_min[i]-] in box i are selected
peek_t res;
for(int i = 0; i < N_BOXES; ++i) {
typedef struct {
uint8_t box, ci;
} trace_t;
trace_t levels[N_BOXES];
bool sort_seen[N_BOXES] = {0};
ci_min[i] = 0;
for (int lvl = 0, box = i; ;) {
if (ci_min[box] != BOX_SIZE) {
// look for unselected sort in the box
bool done = false;
for (int ci = ci_min[box]; ci < BOX_SIZE; ++ci) {
int sort = boxes.b[box][ci];
if (box_of_cookie[sort] == N_BOXES) {
// sort unselected.
// It means that search at step i succeed
// Assign new sort
res.b[box] = ci;
box_of_cookie[sort] = box;
// set new high water mark
ci_min[box] = ci + 1;
// commit preserved assignments
for (int k = 0; k < lvl; ++k) {
int box = levels[k].box;
int ci = levels[k].ci;
res.b[box] = ci;
box_of_cookie[boxes.b[box][ci]] = box;
}
done = true;
break;
}
}
if (done)
break;
ci_min[box] = BOX_SIZE;
}
// all cookies in the box belong to selected sorts
// look for unseen sort in box
bool back = true;
for (int ci = 0; ci < BOX_SIZE; ++ci) {
int sort = boxes.b[box][ci];
if (!sort_seen[sort]) {
// Unseen sort found
// If current branch of search succeed then
// it will become a new selection for box
// Save new selection for sort.
// Saved box also serves us
// if we return to the current level from above
levels[lvl++] = (trace_t){ .ci=ci, .box=box};
// Mark sort as seen.
// That mark guarantees forward progress of the search
sort_seen[sort] = true;
// Continue the search.
// Look for new selection for the old box of sort
box = box_of_cookie[sort];
back = false;
break;
}
}
if (back) // no unseen sorts in box
box = levels[--lvl].box; // return to previous level
}
}
return res;
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-21 18:22 -0700 |
| Message-ID | <86tst36b6t.fsf@linuxsc.com> |
| In reply to | #397683 |
Michael S <already5chosen@yahoo.com> writes:
> On Fri, 17 Apr 2026 07:40:13 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> My questions are these. One, could you understand what the code is
>> doing and how it works? And two, if given an appropriate choice of
>> what permutation is done in best_next_ctype(), does this code do the
>> same thing as your code? I was trying to match the behavior of your
>> code but I wasn't able to figure out how it decided where to go
>> next.
>
> Here is the simplest form of the algorithm that I can come with.
> Essentially, it is a serial non-recursive variant of the code of your
> friend with no algorithmic or technical enhancements.
> Even in this form it is not slow and hopefully makes the key idea more
> obvious.
I have difficulty reading code written in the style used below. I
might describe it broadly as too many trees and not enough forest.
That comment is not meant as criticism but given just for
informational value.
My hope has been that my explanations, given first in prose and then
in code, would let you understand how I approached the problem, so
you could see how your approach differs from mine and then explain
what the differences are. As things stand I don't know what are the
common points of reference, or even whether there are any important
ones.
Having said that, let me ask this. What is your goal? I find
myself wondering if we are talking past each other.
> #include <stdint.h>
> #include <stdbool.h>
> #include "solver.h"
>
> peek_t
> solver( boxes_t boxes ){
> uint8_t box_of_cookie[N_BOXES]; // valid for selected sorts
> for (int i = 0; i < N_BOXES; i++)
> box_of_cookie[i] = N_BOXES; // value N_BOXES marks unselected sort
>
> // Selection proceeds in progressive steps.
> // At each step we select one new box and one new sort.
> // A box and a sort selected at step i are never unselected later
> // although association between selected boxes and sorts
> // can be changed
> for (int step = 0; step < N_BOXES; ++step) {
> typedef struct {
> uint8_t box, sort;
> } trace_t;
> trace_t levels[N_BOXES];
> bool seen[N_BOXES] = {0};
> for (int lvl = 0, box = step; ;) {
> // look for unseen sort in box
> int sort;
> for (int ci = 0; ci < BOX_SIZE; ++ci) {
> sort = boxes.b[box][ci];
> if (!seen[sort])
> break;
> }
> if (seen[sort]) { // no unseen sorts in box
> box = levels[--lvl].box; // return to previous level
> continue;
> }
> // Unseen sort found
> // It will become a new selection for box
> int selected_box = box_of_cookie[sort];
> if (selected_box == N_BOXES) {
> // sort unselected.
> // it means that search at step i succeed
> // commit preserved assignments
> for (int k = 0; k < lvl; ++k)
> box_of_cookie[levels[k].sort] = levels[k].box;
> // assign new sort
> box_of_cookie[sort] = box;
> break;
> }
>
> // sort already selected
> // Save new assignment for sort.
> // Saved box also serves us if we return
> // to the current level from above
> levels[lvl++] = (trace_t){ .sort=sort, .box=box};
> // Mark sort as seen.
> // That mark guarantees forward progress of the search
> seen[sort] = true;
> // Continue search.
> // At the next level we will look for new selection
> // for old box of sort
> box = selected_box;
> }
> }
>
> // translate result from box_of_cookie[] to index of cookie in box
> peek_t res;
> for (int c = 0; c < N_BOXES; ++c) {
> int b = box_of_cookie[c];
> for (int k = 0; k < BOX_SIZE; ++k) {
> if (boxes.b[b][k] == c) {
> res.b[b] = k;
> break;
> }
> }
> }
> return res;
> }
Another question: is the above typical of how you usually write
code, or are you writing it like that for my benefit?
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-22 12:05 +0300 |
| Message-ID | <20260422120530.00002e04@yahoo.com> |
| In reply to | #397768 |
On Tue, 21 Apr 2026 18:22:34 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Fri, 17 Apr 2026 07:40:13 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> My questions are these. One, could you understand what the code is
> >> doing and how it works? And two, if given an appropriate choice of
> >> what permutation is done in best_next_ctype(), does this code do
> >> the same thing as your code? I was trying to match the behavior
> >> of your code but I wasn't able to figure out how it decided where
> >> to go next.
> >
> > Here is the simplest form of the algorithm that I can come with.
> > Essentially, it is a serial non-recursive variant of the code of
> > your friend with no algorithmic or technical enhancements.
> > Even in this form it is not slow and hopefully makes the key idea
> > more obvious.
>
> I have difficulty reading code written in the style used below. I
> might describe it broadly as too many trees and not enough forest.
> That comment is not meant as criticism but given just for
> informational value.
>
> My hope has been that my explanations, given first in prose and then
> in code, would let you understand how I approached the problem, so
> you could see how your approach differs from mine and then explain
> what the differences are. As things stand I don't know what are the
> common points of reference, or even whether there are any important
> ones.
>
> Having said that, let me ask this. What is your goal? I find
> myself wondering if we are talking past each other.
>
My general goal is to show that while this challenge may look like
variant of travelling salesman problem, it actually is not.
It is not NP complete and has many solutions with mean complexity of
little above M*N and worst case complexity still below M*N*N.
My 2nd goal is to outline common characteristics of various robust
solutions ignoring as much as possible technical details:
- N progressive steps
- within each step, forward progress due to recording of failed
attempts ('seen' bit array).
>
> > #include <stdint.h>
> > #include <stdbool.h>
> > #include "solver.h"
> >
> > peek_t
> > solver( boxes_t boxes ){
> > uint8_t box_of_cookie[N_BOXES]; // valid for selected sorts
> > for (int i = 0; i < N_BOXES; i++)
> > box_of_cookie[i] = N_BOXES; // value N_BOXES marks unselected
> > sort
> >
> > // Selection proceeds in progressive steps.
> > // At each step we select one new box and one new sort.
> > // A box and a sort selected at step i are never unselected later
> > // although association between selected boxes and sorts
> > // can be changed
> > for (int step = 0; step < N_BOXES; ++step) {
> > typedef struct {
> > uint8_t box, sort;
> > } trace_t;
> > trace_t levels[N_BOXES];
> > bool seen[N_BOXES] = {0};
> > for (int lvl = 0, box = step; ;) {
> > // look for unseen sort in box
> > int sort;
> > for (int ci = 0; ci < BOX_SIZE; ++ci) {
> > sort = boxes.b[box][ci];
> > if (!seen[sort])
> > break;
> > }
> > if (seen[sort]) { // no unseen sorts in box
> > box = levels[--lvl].box; // return to previous level
> > continue;
> > }
> > // Unseen sort found
> > // It will become a new selection for box
> > int selected_box = box_of_cookie[sort];
> > if (selected_box == N_BOXES) {
> > // sort unselected.
> > // it means that search at step i succeed
> > // commit preserved assignments
> > for (int k = 0; k < lvl; ++k)
> > box_of_cookie[levels[k].sort] = levels[k].box;
> > // assign new sort
> > box_of_cookie[sort] = box;
> > break;
> > }
> >
> > // sort already selected
> > // Save new assignment for sort.
> > // Saved box also serves us if we return
> > // to the current level from above
> > levels[lvl++] = (trace_t){ .sort=sort, .box=box};
> > // Mark sort as seen.
> > // That mark guarantees forward progress of the search
> > seen[sort] = true;
> > // Continue search.
> > // At the next level we will look for new selection
> > // for old box of sort
> > box = selected_box;
> > }
> > }
> >
> > // translate result from box_of_cookie[] to index of cookie in box
> > peek_t res;
> > for (int c = 0; c < N_BOXES; ++c) {
> > int b = box_of_cookie[c];
> > for (int k = 0; k < BOX_SIZE; ++k) {
> > if (boxes.b[b][k] == c) {
> > res.b[b] = k;
> > break;
> > }
> > }
> > }
> > return res;
> > }
>
> Another question: is the above typical of how you usually write
> code, or are you writing it like that for my benefit?
Do you mean, relatively long comments distributed through the code vs
concentrated at the beginning?
I don't know, because I don't try to remember such things. I'd have to
read a sizable corpus of my own production code in order to give an
answer.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-29 06:55 -0700 |
| Message-ID | <86fr4d27nr.fsf@linuxsc.com> |
| In reply to | #397783 |
Michael S <already5chosen@yahoo.com> writes:
> On Tue, 21 Apr 2026 18:22:34 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>> On Fri, 17 Apr 2026 07:40:13 -0700
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> My questions are these. One, could you understand what the code is
>>>> doing and how it works? And two, if given an appropriate choice of
>>>> what permutation is done in best_next_ctype(), does this code do
>>>> the same thing as your code? I was trying to match the behavior
>>>> of your code but I wasn't able to figure out how it decided where
>>>> to go next.
>>>
>>> Here is the simplest form of the algorithm that I can come with.
>>> Essentially, it is a serial non-recursive variant of the code of
>>> your friend with no algorithmic or technical enhancements.
>>> Even in this form it is not slow and hopefully makes the key idea
>>> more obvious.
>>
>> I have difficulty reading code written in the style used below. I
>> might describe it broadly as too many trees and not enough forest.
>> That comment is not meant as criticism but given just for
>> informational value.
>>
>> My hope has been that my explanations, given first in prose and then
>> in code, would let you understand how I approached the problem, so
>> you could see how your approach differs from mine and then explain
>> what the differences are. As things stand I don't know what are the
>> common points of reference, or even whether there are any important
>> ones.
>>
>> Having said that, let me ask this. What is your goal? I find
>> myself wondering if we are talking past each other.
>
> My general goal is to show that while this challenge may look like
> variant of travelling salesman problem, it actually is not.
> It is not NP complete and has many solutions with mean complexity of
> little above M*N and worst case complexity still below M*N*N.
For me, neither the "mathematical" outlines nor the various code
solutions are helpful in showing the problem isn't NP complete.
On the other hand, I don't worry about whether the problem might
be NP complete. For me the nature of the problem is enough to
show that this isn't an NP-complete kind of problem. It doesn't
have the right feel.
> My 2nd goal is to outline common characteristics of various robust
> solutions ignoring as much as possible technical details:
> - N progressive steps
> - within each step, forward progress due to recording of failed
> attempts ('seen' bit array).
>
>>> #include <stdint.h>
>>> #include <stdbool.h>
>>> #include "solver.h"
>>>
>>> peek_t
>>> solver( boxes_t boxes ){
>>> uint8_t box_of_cookie[N_BOXES]; // valid for selected sorts
>>> for (int i = 0; i < N_BOXES; i++)
>>> box_of_cookie[i] = N_BOXES; // value N_BOXES marks unselected
>>> sort
>>>
>>> // Selection proceeds in progressive steps.
>>> // At each step we select one new box and one new sort.
>>> // A box and a sort selected at step i are never unselected later
>>> // although association between selected boxes and sorts
>>> // can be changed
>>> for (int step = 0; step < N_BOXES; ++step) {
>>> typedef struct {
>>> uint8_t box, sort;
>>> } trace_t;
>>> trace_t levels[N_BOXES];
>>> bool seen[N_BOXES] = {0};
>>> for (int lvl = 0, box = step; ;) {
>>> // look for unseen sort in box
>>> int sort;
>>> for (int ci = 0; ci < BOX_SIZE; ++ci) {
>>> sort = boxes.b[box][ci];
>>> if (!seen[sort])
>>> break;
>>> }
>>> if (seen[sort]) { // no unseen sorts in box
>>> box = levels[--lvl].box; // return to previous level
>>> continue;
>>> }
>>> // Unseen sort found
>>> // It will become a new selection for box
>>> int selected_box = box_of_cookie[sort];
>>> if (selected_box == N_BOXES) {
>>> // sort unselected.
>>> // it means that search at step i succeed
>>> // commit preserved assignments
>>> for (int k = 0; k < lvl; ++k)
>>> box_of_cookie[levels[k].sort] = levels[k].box;
>>> // assign new sort
>>> box_of_cookie[sort] = box;
>>> break;
>>> }
>>>
>>> // sort already selected
>>> // Save new assignment for sort.
>>> // Saved box also serves us if we return
>>> // to the current level from above
>>> levels[lvl++] = (trace_t){ .sort=sort, .box=box};
>>> // Mark sort as seen.
>>> // That mark guarantees forward progress of the search
>>> seen[sort] = true;
>>> // Continue search.
>>> // At the next level we will look for new selection
>>> // for old box of sort
>>> box = selected_box;
>>> }
>>> }
>>>
>>> // translate result from box_of_cookie[] to index of cookie in box
>>> peek_t res;
>>> for (int c = 0; c < N_BOXES; ++c) {
>>> int b = box_of_cookie[c];
>>> for (int k = 0; k < BOX_SIZE; ++k) {
>>> if (boxes.b[b][k] == c) {
>>> res.b[b] = k;
>>> break;
>>> }
>>> }
>>> }
>>> return res;
>>> }
>>
>> Another question: is the above typical of how you usually write
>> code, or are you writing it like that for my benefit?
>
> Do you mean, relatively long comments distributed through the code vs
> concentrated at the beginning?
I didn't mean that specifically. There are several aspects I might
ask about. If you're interested I can try to be be more specific.
And if you're not interested, no worries. :)
> I don't know, because I don't try to remember such things. I'd have to
> read a sizable corpus of my own production code in order to give an
> answer.
I'm willing to trust your memory and your judgment. If you wanted
to look at a small sample (or several samples) that you think is
representative, I think that would be fine; no need to be
exhaustive, especially since what I'm asking is about your thoughts
and preferences rather than what code you may happen to have written
in the past.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-15 02:15 +0300 |
| Message-ID | <20260415021526.000047e2@yahoo.com> |
| In reply to | #397424 |
On Wed, 08 Apr 2026 08:42:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
> After that, I talked to a friend to try a different approach to
> producing a solution. After some light editing by myself -- mostly
> just formatting and some name changes -- the code below was put into
> the hopper. (Note: I claim no credit for code below. I did some
> editing to make it more readable but beyond that none of it is a
> result of my efforts.)
>
> #include <stdint.h>
> #include "solver.h"
>
> static uint32_t adjacent[ N_BOXES ];
> static int cookie_of_box[ N_BOXES ];
> static int box_of_cookie[ N_BOXES ];
> static uint32_t seen;
>
> static int
> search( int b ){
> uint32_t m = adjacent[b];
> while( m ){
> uint32_t bit = m & -m;
> m ^= bit;
> int c = __builtin_ctz( bit );
> if( seen & 1u<<c ) continue;
> seen |= 1u<<c;
> if( box_of_cookie[c] == -1 || search( box_of_cookie[c]
> ) ){ box_of_cookie[c] = b;
> cookie_of_box[b] = c;
> return 1;
> }
> }
> return 0;
> }
>
> peek_t
> solver( boxes_t boxes ){
> peek_t res;
>
> for( int i = 0; i < N_BOXES; i++ ){
> uint32_t m = 0;
> for( int k = 0; k < BOX_SIZE; k++ ){
> m |= 1u << boxes.b[i][k];
> }
> adjacent[i] = m;
> cookie_of_box[i] = -1;
> box_of_cookie[i] = -1;
> }
>
> for( int i = 0; i < N_BOXES; i++ ){
> seen = 0;
> search( i );
> }
>
> for( int i = 0; i < N_BOXES; i++ ){
> int c = cookie_of_box[i];
> for( int k = 0; k < BOX_SIZE; k++ ){
> if( boxes.b[i][k] == c ){
> res.b[i] = k;
> break;
> }
> }
> }
> return res;
> }
>
> Despite being derived independently, this code uses the same sort of
> approach that I had used, except my code was recursive rather than
> iterative.
>
I finally looked closer to the code of your friend.
To me, it does not look at all similar to description of "your"
algorithm in your other post.
It appears more similar to my 2nd algorithm, but sort of orthogonal to
it - my outermost loop iterate through sorts of cookies; in the code of
your friend outermost loop iterate through boxes.
Another difference, less important for robustness, more important for
measured speed, esp. on avearge, is when search decides to revert
previous selection. I am doing it only after all possibilities to
select at the top level failed. Your friend makes no such effort and
easily dives deep. In principle, both approaches are equivalent, but in
physical world recursive call is significantly slower than iteration of
simple loop and excessive updates of state variables are also slower
then lookups without updates.
And, of course, apart from difference in algorithm there is a
significant difference in implementation technique. Your friend took
advantage of the fact that the challenge was specified for relatively
small number of boxes and intensely used bit masks. I [didn't took
similar advantage [except for using byte variables instead of short or
int] and used arrays. Of course, the technique applied by your friend
is faster. His solution ended up ~2 times slower then mine not because
of technique, but because of algorithmic difference mentioned in
previous paragraph.
Today I modified his code, applying variant of the same algorithmic
change. At the same opportunity I removed use of static data and
increased size of bit masks to 64 bits. As expected, resulting code was
very fast, ~3 times faster than my own.
Here is a code:
// Modification of code of friend of Tim Rentsch
#include <stdint.h>
#include "solver.h"
typedef struct {
uint64_t cookies_in_box[ N_BOXES ]; // helper index, constant after
init uint64_t selected;
uint8_t box_of_cookie [ N_BOXES ]; // valid for selected sorts
} state_t;
// return 0 on success, seen mask on failure
static uint64_t search(state_t* s, int b, uint64_t seen)
{
uint64_t m = s->cookies_in_box[b] & ~seen;
if (m & ~s->selected) {
int c = __builtin_ctzll(m & ~s->selected);
s->box_of_cookie[c] = b;
s->selected |= 1ull << c;
return 0; // success
}
while( m ){
int c = __builtin_ctz(m);
seen = search(s, s->box_of_cookie[c], seen | (1ull << c));
if (seen == 0) {
s->box_of_cookie[c] = b;
return 0; // success
}
m &= ~seen;
}
return seen;
}
peek_t
solver( boxes_t boxes ){
state_t s;
for (int i = 0; i < N_BOXES; i++) {
uint64_t m = 0;
for (int k = 0; k < BOX_SIZE; k++)
m |= 1ull << boxes.b[i][k];
s.cookies_in_box[i] = m;
}
s.selected = 0;
for( int i = 0; i < N_BOXES; i++ )
search(&s, i, 0);
// translate result from box_of_cookie[] to index of cookie in box
peek_t res;
for (int c = 0; c < N_BOXES; ++c) {
int b = s.box_of_cookie[c];
for( int k = 0; k < BOX_SIZE; k++ ){
if (boxes.b[b][k] == c) {
res.b[b] = k;
break;
}
}
}
return res;
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-16 02:57 -0700 |
| Message-ID | <86mrz36xdf.fsf@linuxsc.com> |
| In reply to | #397532 |
Michael S <already5chosen@yahoo.com> writes:
> On Wed, 08 Apr 2026 08:42:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> After that, I talked to a friend to try a different approach to
>> producing a solution. After some light editing by myself -- mostly
>> just formatting and some name changes -- the code below was put into
>> the hopper. (Note: I claim no credit for code below. I did some
>> editing to make it more readable but beyond that none of it is a
>> result of my efforts.)
>>
>> #include <stdint.h>
>> #include "solver.h"
>>
>> static uint32_t adjacent[ N_BOXES ];
>> static int cookie_of_box[ N_BOXES ];
>> static int box_of_cookie[ N_BOXES ];
>> static uint32_t seen;
>>
>> static int
>> search( int b ){
>> uint32_t m = adjacent[b];
>> while( m ){
>> uint32_t bit = m & -m;
>> m ^= bit;
>> int c = __builtin_ctz( bit );
>> if( seen & 1u<<c ) continue;
>> seen |= 1u<<c;
>> if( box_of_cookie[c] == -1 || search( box_of_cookie[c]
>> ) ){ box_of_cookie[c] = b;
>> cookie_of_box[b] = c;
>> return 1;
>> }
>> }
>> return 0;
>> }
>>
>> peek_t
>> solver( boxes_t boxes ){
>> peek_t res;
>>
>> for( int i = 0; i < N_BOXES; i++ ){
>> uint32_t m = 0;
>> for( int k = 0; k < BOX_SIZE; k++ ){
>> m |= 1u << boxes.b[i][k];
>> }
>> adjacent[i] = m;
>> cookie_of_box[i] = -1;
>> box_of_cookie[i] = -1;
>> }
>>
>> for( int i = 0; i < N_BOXES; i++ ){
>> seen = 0;
>> search( i );
>> }
>>
>> for( int i = 0; i < N_BOXES; i++ ){
>> int c = cookie_of_box[i];
>> for( int k = 0; k < BOX_SIZE; k++ ){
>> if( boxes.b[i][k] == c ){
>> res.b[i] = k;
>> break;
>> }
>> }
>> }
>> return res;
>> }
>>
>> Despite being derived independently, this code uses the same sort of
>> approach that I had used, except my code was recursive rather than
>> iterative.
>
> I finally looked closer to the code of your friend.
> To me, it does not look at all similar to description of "your"
> algorithm in your other post.
> It appears more similar to my 2nd algorithm, but sort of orthogonal to
> it - my outermost loop iterate through sorts of cookies; in the code of
> your friend outermost loop iterate through boxes.
I confess I didn't look closely at the algorithm but relied
on comments about how the code worked. I tried to express
this in my earlier posting when I said "the same sort of
approach" rather than "the same approach". Sorry for any
confusion.
> Another difference, less important for robustness, more important for
> measured speed, esp. on avearge, is when search decides to revert
> previous selection. I am doing it only after all possibilities to
> select at the top level failed. Your friend makes no such effort and
> easily dives deep. In principle, both approaches are equivalent, but
> in physical world recursive call is significantly slower than
> iteration of simple loop and excessive updates of state variables are
> also slower then lookups without updates.
>
> And, of course, apart from difference in algorithm there is a
> significant difference in implementation technique. Your friend took
> advantage of the fact that the challenge was specified for relatively
> small number of boxes and intensely used bit masks. I [didn't took
> similar advantage [except for using byte variables instead of short
> or int] and used arrays. Of course, the technique applied by your
> friend is faster. His solution ended up ~2 times slower then mine
> not because of technique, but because of algorithmic difference
> mentioned in previous paragraph.
>
> Today I modified his code, applying variant of the same algorithmic
> change. At the same opportunity I removed use of static data and
> increased size of bit masks to 64 bits. As expected, resulting code
> was very fast, ~3 times faster than my own. [...code...]
I'm happy to hear the posting provided an opportunity to more deeply
explore the problem. Also it's interesting to learn the results of
your investigations; thank you for those.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-17 17:04 +0300 |
| Message-ID | <20260417170444.000020da@yahoo.com> |
| In reply to | #397590 |
On Thu, 16 Apr 2026 02:57:32 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 08 Apr 2026 08:42:11 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> After that, I talked to a friend to try a different approach to
> >> producing a solution. After some light editing by myself -- mostly
> >> just formatting and some name changes -- the code below was put
> >> into the hopper. (Note: I claim no credit for code below. I did
> >> some editing to make it more readable but beyond that none of it
> >> is a result of my efforts.)
> >>
> >> #include <stdint.h>
> >> #include "solver.h"
> >>
> >> static uint32_t adjacent[ N_BOXES ];
> >> static int cookie_of_box[ N_BOXES ];
> >> static int box_of_cookie[ N_BOXES ];
> >> static uint32_t seen;
> >>
> >> static int
> >> search( int b ){
> >> uint32_t m = adjacent[b];
> >> while( m ){
> >> uint32_t bit = m & -m;
> >> m ^= bit;
> >> int c = __builtin_ctz( bit );
> >> if( seen & 1u<<c ) continue;
> >> seen |= 1u<<c;
> >> if( box_of_cookie[c] == -1 || search(
> >> box_of_cookie[c] ) ){ box_of_cookie[c] = b;
> >> cookie_of_box[b] = c;
> >> return 1;
> >> }
> >> }
> >> return 0;
> >> }
> >>
> >> peek_t
> >> solver( boxes_t boxes ){
> >> peek_t res;
> >>
> >> for( int i = 0; i < N_BOXES; i++ ){
> >> uint32_t m = 0;
> >> for( int k = 0; k < BOX_SIZE; k++ ){
> >> m |= 1u << boxes.b[i][k];
> >> }
> >> adjacent[i] = m;
> >> cookie_of_box[i] = -1;
> >> box_of_cookie[i] = -1;
> >> }
> >>
> >> for( int i = 0; i < N_BOXES; i++ ){
> >> seen = 0;
> >> search( i );
> >> }
> >>
> >> for( int i = 0; i < N_BOXES; i++ ){
> >> int c = cookie_of_box[i];
> >> for( int k = 0; k < BOX_SIZE; k++ ){
> >> if( boxes.b[i][k] == c ){
> >> res.b[i] = k;
> >> break;
> >> }
> >> }
> >> }
> >> return res;
> >> }
> >>
> >> Despite being derived independently, this code uses the same sort
> >> of approach that I had used, except my code was recursive rather
> >> than iterative.
> >
> > I finally looked closer to the code of your friend.
> > To me, it does not look at all similar to description of "your"
> > algorithm in your other post.
> > It appears more similar to my 2nd algorithm, but sort of orthogonal
> > to it - my outermost loop iterate through sorts of cookies; in the
> > code of your friend outermost loop iterate through boxes.
>
> I confess I didn't look closely at the algorithm but relied
> on comments about how the code worked. I tried to express
> this in my earlier posting when I said "the same sort of
> approach" rather than "the same approach". Sorry for any
> confusion.
>
> > Another difference, less important for robustness, more important
> > for measured speed, esp. on avearge, is when search decides to
> > revert previous selection. I am doing it only after all
> > possibilities to select at the top level failed. Your friend makes
> > no such effort and easily dives deep. In principle, both
> > approaches are equivalent, but in physical world recursive call is
> > significantly slower than iteration of simple loop and excessive
> > updates of state variables are also slower then lookups without
> > updates.
> >
> > And, of course, apart from difference in algorithm there is a
> > significant difference in implementation technique. Your friend
> > took advantage of the fact that the challenge was specified for
> > relatively small number of boxes and intensely used bit masks. I
> > [didn't took similar advantage [except for using byte variables
> > instead of short or int] and used arrays. Of course, the technique
> > applied by your friend is faster. His solution ended up ~2 times
> > slower then mine not because of technique, but because of
> > algorithmic difference mentioned in previous paragraph.
> >
> > Today I modified his code, applying variant of the same algorithmic
> > change. At the same opportunity I removed use of static data and
> > increased size of bit masks to 64 bits. As expected, resulting code
> > was very fast, ~3 times faster than my own. [...code...]
>
> I'm happy to hear the posting provided an opportunity to more deeply
> explore the problem. Also it's interesting to learn the results of
> your investigations; thank you for those.
I was aware of possibility of taking advantage of the fact that value
of N_BOXES specified in the challenge is <= than dominant width of
machine word.
I intentionally avoided it until this point, for two reasons, one
abstract (A) and one practical (P).
A. the challenge was meant to be algorithmic with lesser emphasis on
implementation
P. I planned (and still plan) experimental testing of BigO
But I couldn't resist the appeal of fast :(
The achieved 3x speed up was actually disappointing. I expected more.
It seems, by now building helper indices takes more time than solver
itself, which makes further progress in this part pointless.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-08 23:45 +0300 |
| Message-ID | <20260408234507.00002dd6@yahoo.com> |
| In reply to | #397345 |
On Wed, 1 Apr 2026 16:34:47 +0300
Michael S <already5chosen@yahoo.com> wrote:
<snip>
My implementation #1.
It is based on the proof provided by somebody with abstract math
attitude.
He said that his proof is something that the 5th grade schoolchildren
could find with in 5 minutes.
I am no 5th pupil any longer. Even understanding of his proof took
me significantly longer than 5 minutes :(
Here is my attempt of translation (original proof was not in English):
"Solution would be done by induction by number of cookies of each sort
(the same for all sorts).
For K=2 the solution is simple. Please figure it out yourself.
Now let's take K > 2 and postulate that for numbers of cookies per box
that are smaller than K the assertion already proven.
Let's take some disposition for which the assertion is correct and
remove the corresponding "thread" (i.e. one cookie from each box, all
of different sorts). Then supposition of induction is correct for
remaining disposition, which means that we can remove yet another
thread, then yet another etc.. for a total of K threads. That is,
for K>2 there are more than 2 threads.
Now let's exchange places between any 2 two cookies from different
boxes. Since by doing so we are touching 1 or 2 threads then there
still be at least one thread untouched (at least k-2 threads, actually
[M.S.]). It means that the property "we can remove a thread" is
not disturbed by our action (i.e. by exchange of two cookies).
What is left it is to realize that by means of such exchanges any
disposition can be mutated from any other disposition.
That's all."
And here is a code. It is not very fast. But the speed is almost the
same on average and in the worst case.
#include <stdint.h>
#include <stdbool.h>
#include "solver.h"
peek_t solver(boxes_t boxes)
{
uint8_t na[N_BOXES] = {0};
typedef struct { uint8_t s,d; } xch_t;
xch_t xch[N_BOXES*BOX_SIZE];
int i = 0;
for (int src_bi = 0; src_bi < N_BOXES; ++src_bi) {
for (int src_ci = na[src_bi]; src_ci < BOX_SIZE; ++src_ci) {
uint8_t dst_bi = boxes.b[src_bi][src_ci];
while (dst_bi != src_bi) {
uint8_t dst_ci = na[dst_bi];
uint8_t dst_v = boxes.b[dst_bi][dst_ci];
na[dst_bi] = dst_ci+1;
xch[i++] = (xch_t){ .s=src_bi, .d=dst_bi};
dst_bi = dst_v;
}
xch[i++] = (xch_t){ .s=src_bi, .d=dst_bi};
}
na[src_bi] = BOX_SIZE;
}
for (int bi = 0; bi < N_BOXES; ++bi)
for (int ci = 0; ci < BOX_SIZE; ++ci)
boxes.b[bi][ci] = bi;
uint8_t tx[N_BOXES][BOX_SIZE];
for (int bi = 0; bi < N_BOXES; ++bi)
for (int ci = 0; ci < BOX_SIZE; ++ci)
tx[bi][ci] = ci;
peek_t threads[BOX_SIZE];
for (int ci = 0; ci < BOX_SIZE; ++ci)
for (int bi = 0; bi < N_BOXES; ++bi)
threads[ci].b[bi] = ci;
for (int i = N_BOXES*BOX_SIZE-1; i >= 0; --i) {
uint8_t src_bi = xch[i].s;
uint8_t dst_bi = xch[i].d;
uint8_t dst_ci = na[dst_bi] - 1;
na[dst_bi] = dst_ci;
if (src_bi != dst_bi) {
uint8_t src_ci = na[src_bi];
uint8_t src_v = boxes.b[src_bi][src_ci];
if (src_v != dst_bi) {
uint8_t src_t = tx[src_bi][src_ci];
uint8_t dst_t = tx[dst_bi][dst_ci];
if (src_t != dst_t) {
// 2 threads broken. Fix
uint8_t v2bi[N_BOXES];
for (int bi = 0; bi < N_BOXES; ++bi)
v2bi[boxes.b[bi][threads[src_t].b[bi]]] = bi;
boxes.b[src_bi][src_ci] = dst_bi;
boxes.b[dst_bi][dst_ci] = src_v;
for (uint8_t v = dst_bi; v != src_v;) {
uint8_t bi = v2bi[v];
uint8_t c0 = threads[src_t].b[bi];
uint8_t c1 = threads[dst_t].b[bi];
threads[src_t].b[bi] = c1;
threads[dst_t].b[bi] = c0;
tx[bi][c1] = src_t;
tx[bi][c0] = dst_t;
v = boxes.b[bi][c1];
}
} else {
boxes.b[src_bi][src_ci] = dst_bi;
boxes.b[dst_bi][dst_ci] = src_v;
}
}
}
}
return threads[0];
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-09 16:37 -0700 |
| Message-ID | <86ecknbt8l.fsf@linuxsc.com> |
| In reply to | #397429 |
Michael S <already5chosen@yahoo.com> writes:
> On Wed, 1 Apr 2026 16:34:47 +0300
> Michael S <already5chosen@yahoo.com> wrote:
>
> <snip>
>
> My implementation #1.
> It is based on the proof provided by somebody with abstract math
> attitude.
> He said that his proof is something that the 5th grade schoolchildren
> could find with in 5 minutes.
> I am no 5th pupil any longer. Even understanding of his proof took
> me significantly longer than 5 minutes :(
> Here is my attempt of translation (original proof was not in English):
>
> "Solution would be done by induction by number of cookies of each sort
> (the same for all sorts).
> For K=2 the solution is simple. Please figure it out yourself.
> Now let's take K > 2 and postulate that for numbers of cookies per box
> that are smaller than K the assertion already proven.
> Let's take some disposition for which the assertion is correct and
> remove the corresponding "thread" (i.e. one cookie from each box, all
> of different sorts). Then supposition of induction is correct for
> remaining disposition, which means that we can remove yet another
> thread, then yet another etc.. for a total of K threads. That is,
> for K>2 there are more than 2 threads.
> Now let's exchange places between any 2 two cookies from different
> boxes. Since by doing so we are touching 1 or 2 threads then there
> still be at least one thread untouched (at least k-2 threads, actually
> [M.S.]). It means that the property "we can remove a thread" is
> not disturbed by our action (i.e. by exchange of two cookies).
> What is left it is to realize that by means of such exchanges any
> disposition can be mutated from any other disposition.
> That's all."
I am confident that my understanding of this description, if indeed
it ever occurs, would take a good deal longer than five minutes.
Sadly I think it is representative of many of the explanations
offered by mathematical types.
> And here is a code. It is not very fast. But the speed is almost the
> same on average and in the worst case.
>
> #include <stdint.h>
> #include <stdbool.h>
>
> #include "solver.h"
>
> peek_t solver(boxes_t boxes)
> {
> uint8_t na[N_BOXES] = {0};
> typedef struct { uint8_t s,d; } xch_t;
> xch_t xch[N_BOXES*BOX_SIZE];
> int i = 0;
> for (int src_bi = 0; src_bi < N_BOXES; ++src_bi) {
> for (int src_ci = na[src_bi]; src_ci < BOX_SIZE; ++src_ci) {
> uint8_t dst_bi = boxes.b[src_bi][src_ci];
> while (dst_bi != src_bi) {
> uint8_t dst_ci = na[dst_bi];
> uint8_t dst_v = boxes.b[dst_bi][dst_ci];
> na[dst_bi] = dst_ci+1;
> xch[i++] = (xch_t){ .s=src_bi, .d=dst_bi};
> dst_bi = dst_v;
> }
> xch[i++] = (xch_t){ .s=src_bi, .d=dst_bi};
> }
> na[src_bi] = BOX_SIZE;
> }
>
> for (int bi = 0; bi < N_BOXES; ++bi)
> for (int ci = 0; ci < BOX_SIZE; ++ci)
> boxes.b[bi][ci] = bi;
>
> uint8_t tx[N_BOXES][BOX_SIZE];
> for (int bi = 0; bi < N_BOXES; ++bi)
> for (int ci = 0; ci < BOX_SIZE; ++ci)
> tx[bi][ci] = ci;
>
> peek_t threads[BOX_SIZE];
> for (int ci = 0; ci < BOX_SIZE; ++ci)
> for (int bi = 0; bi < N_BOXES; ++bi)
> threads[ci].b[bi] = ci;
>
> for (int i = N_BOXES*BOX_SIZE-1; i >= 0; --i) {
> uint8_t src_bi = xch[i].s;
> uint8_t dst_bi = xch[i].d;
> uint8_t dst_ci = na[dst_bi] - 1;
> na[dst_bi] = dst_ci;
> if (src_bi != dst_bi) {
> uint8_t src_ci = na[src_bi];
> uint8_t src_v = boxes.b[src_bi][src_ci];
> if (src_v != dst_bi) {
> uint8_t src_t = tx[src_bi][src_ci];
> uint8_t dst_t = tx[dst_bi][dst_ci];
> if (src_t != dst_t) {
> // 2 threads broken. Fix
> uint8_t v2bi[N_BOXES];
> for (int bi = 0; bi < N_BOXES; ++bi)
> v2bi[boxes.b[bi][threads[src_t].b[bi]]] = bi;
> boxes.b[src_bi][src_ci] = dst_bi;
> boxes.b[dst_bi][dst_ci] = src_v;
> for (uint8_t v = dst_bi; v != src_v;) {
> uint8_t bi = v2bi[v];
> uint8_t c0 = threads[src_t].b[bi];
> uint8_t c1 = threads[dst_t].b[bi];
> threads[src_t].b[bi] = c1;
> threads[dst_t].b[bi] = c0;
> tx[bi][c1] = src_t;
> tx[bi][c0] = dst_t;
> v = boxes.b[bi][c1];
> }
> } else {
> boxes.b[src_bi][src_ci] = dst_bi;
> boxes.b[dst_bi][dst_ci] = src_v;
> }
> }
> }
> }
>
> return threads[0];
> }
In most cases I'm not a big fan of interactive debugging, but
trying to understand how this works might merit an exception.
[toc] | [prev] | [next] | [standalone]
Page 3 of 4 — ← Prev page 1 2 [3] 4 Next page →
Back to top | Article view | comp.lang.c
csiph-web