Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397751
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-21 20:37 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20260421203728.00003035@yahoo.com> (permalink) |
| References | (6 earlier) <20260413171129.0000003d@yahoo.com> <86a4v26pup.fsf@linuxsc.com> <20260417144410.00006d46@yahoo.com> <865x5p7ir6.fsf@linuxsc.com> <20260420004318.000007dd@yahoo.com> |
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;
}
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar
Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 16:34 +0300
Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 10:02 -0400
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:15 +0300
Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 10:28 -0400
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:58 +0300
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 15:20 +0100
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:56 +0300
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 19:50 +0100
Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 15:56 -0400
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 23:33 +0100
Re: Cookies in boxes - algorithmic challenge Richard Harnden <richard.nospam@gmail.invalid> - 2026-04-04 07:43 +0100
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-04 11:54 +0100
Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 15:24 -0400
Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 17:24 -0400
Re: Cookies in boxes - algorithmic challenge Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-04-02 16:25 +0100
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-02 17:10 +0100
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:19 +0300
Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-02 13:03 -0400
Re: Cookies in boxes - algorithmic challenge Richard Harnden <richard.nospam@gmail.invalid> - 2026-04-02 18:52 +0100
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-02 19:50 +0100
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:24 +0300
Re: Cookies in boxes - algorithmic challenge Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-04-02 20:13 +0100
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:36 +0300
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:14 +0300
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:10 +0300
Re: Cookies in boxes - algorithmic challenge Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-04-06 22:36 +0100
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 15:42 -0700
Re: Cookies in boxes - algorithmic challenge Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-04-06 15:44 -0700
Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-04 13:33 -0400
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-04 21:03 +0300
Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-04 14:19 -0400
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-04 20:22 +0100
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-04 22:40 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-04 17:08 -0700
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-08 08:42 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 22:23 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 21:22 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 12:23 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-10 22:41 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 16:16 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:27 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-11 22:56 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 15:57 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-12 02:15 +0300
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-13 02:03 +0300
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-13 17:11 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 23:52 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 14:44 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-17 07:40 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 18:30 +0300
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-20 00:43 +0300
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-21 20:37 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-21 18:22 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-22 12:05 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-29 06:55 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-15 02:15 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 02:57 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 17:04 +0300
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 23:45 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 16:37 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 17:02 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 03:45 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-09 00:01 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 17:07 -0700
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 18:06 +0300
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:31 -0700
Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 03:22 -0700
Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 17:58 +0200
Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 18:08 +0200
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-17 17:47 +0100
Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:24 +0200
Re: Cookies in boxes - algorithmic challenge scott@slp53.sl.home (Scott Lurndal) - 2026-04-17 19:58 +0000
Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-18 05:52 +0200
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 11:53 +0100
Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 12:04 +0100
Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-18 20:35 +0300
Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:52 +0200
Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 20:17 +0200
csiph-web