My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench that
I prepared is in C. The solution does not have to be in C, but it would
be significantly simpler for everybody, esp. for those that are
interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution exists. I
don't ask you to repeat the proof. Just peek cookies!

It's obvious that one can find the solution by exhausting. Don't do
it. Indeed, the number of possible peek orders is finite, but ii is
large - 2.4e18.
Be smarter.
On modern PC I want to get a solution in less than 1 msec, bonus for
less than 50usec.

Test bench.

// solver.h
#include <stdint.h>

enum {
N_BOXES = 20,
BOX_SIZE = 10,
};

typedef struct {
uint8_t b[N_BOXES][BOX_SIZE];
} boxes_t;

typedef struct {
uint8_t b[N_BOXES];
} peek_t;

peek_t solver(boxes_t boxes);
// end of solver.h


// tb.c
#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);
int main(int argz, char** argv)
{
int rep1=128, rep2=11;
if (argz > 1) {
if (strcmp(argv[1], "?")== 0 ||
strcmp(argv[1], "-?")== 0) {
fprintf(stderr,
"Usage:\n"
"solver_tb [rep1 [rep2]]\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"
);
return 0;
}

static const int mx[2] = { 1e7, 1000 };
for (int arg_i = 1; arg_i < 3 && arg_i < argz; ++arg_i) {
char* arg = argv[arg_i];
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[arg_i-1];
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 (arg_i==1)
rep1 = n;
else
rep2 = n;
}
}

void* mem = malloc((sizeof(boxes_t)+sizeof(peek_t))*rep1);
if (!mem) {
perror("malloc()");
return 1;
}

boxes_t* boxes = mem;
peek_t* results = (peek_t*)&boxes[rep1];
int ret = test(boxes, results, rep1, rep2);
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 prng = 1;
long long dt[rep2];
for (int it = 0; it < rep2; ++it) {
for (int i = 0; i < rep1; ++i)
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);
dt[it] = (t1.tv_sec-t0.tv_sec)*(long long)1e9+
t1.tv_nsec-t0.tv_nsec;

for (int i = 0; i < rep1; ++i) {
if (!validate(&boxes[i], &results[i])) {
fprintf(stderr,
"Test fail at iteration %d,%d\n"
,it, 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 mn = dt[0], mx = dt[rep2-1], med = dt[rep2/2];
double scale = 1e-6/rep1;
printf("o.k.\nmed=%.6f msec, min=%.6f msec, max=%.6f msec\n"
,med*scale, mn*scale, mx*scale);

return 0;
}
// end of tb.c

You have to implement function solver() in module solver.c





--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.

Is this what you're trying to do:

There are 20 flavors of cookie.
You have 20 boxes of 10 cookies per box.
Each box of 20 contains a random selection of 10 cookie flavors.
Your goal is to - as quickly as possible - choose 1 cookie from each box
so you end up with all 20 flavors.

?



<snip unread code>



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Wed, 1 Apr 2026 10:02:45 -0400
DFS <nospam@dfs.com> wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.

Is this what you're trying to do:

There are 20 flavors of cookie.
You have 20 boxes of 10 cookies per box.
Each box of 20 contains a random selection of 10 cookie flavors.
Your goal is to - as quickly as possible - choose 1 cookie from each
box so you end up with all 20 flavors.

?

<snip unread code>

Yes. You just forgot to mention that there are exactly 10 cookies of
each flavor.



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 01/04/2026 14:34, Michael S wrote:

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench that
I prepared is in C. The solution does not have to be in C, but it would
be significantly simpler for everybody, esp. for those that are
interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution exists.

A solution to what? You haven't stated the problem!

If there are 20 boxes full of random sorts of cookies, and you take one
from each box (I assume blindly), then you're going to have 20 random
cookies.

I expect there's more to it than that.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 4/1/2026 10:15 AM, Michael S wrote:

On Wed, 1 Apr 2026 10:02:45 -0400
DFS <nospam@dfs.com> wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.

Is this what you're trying to do:

There are 20 flavors of cookie.
You have 20 boxes of 10 cookies per box.
Each box of 20 contains a random selection of 10 cookie flavors.
Your goal is to - as quickly as possible - choose 1 cookie from each
box so you end up with all 20 flavors.

?



<snip unread code>

Yes. You just forgot to mention that there are exactly 10 cookies of
each flavor.

Can there be duplicate flavors in each box of 10?


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Wed, 1 Apr 2026 15:20:09 +0100
Bart <bc@freeuk.com> wrote:

On 01/04/2026 14:34, Michael S wrote:

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench
that I prepared is in C. The solution does not have to be in C, but
it would be significantly simpler for everybody, esp. for those
that are interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution
exists.

A solution to what? You haven't stated the problem!

If there are 20 boxes full of random sorts of cookies, and you take
one from each box (I assume blindly),

No, not blindly.

then you're going to have 20
random cookies.

I expect there's more to it than that.

"You have to take exactly one cookie from each box, all 20 of different
sorts."




--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Wed, 1 Apr 2026 10:28:41 -0400
DFS <nospam@dfs.com> wrote:

On 4/1/2026 10:15 AM, Michael S wrote:

On Wed, 1 Apr 2026 10:02:45 -0400
DFS <nospam@dfs.com> wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take
exactly one cookie from each box, all 20 of different sorts.

Is this what you're trying to do:

There are 20 flavors of cookie.
You have 20 boxes of 10 cookies per box.
Each box of 20 contains a random selection of 10 cookie flavors.
Your goal is to - as quickly as possible - choose 1 cookie from
each box so you end up with all 20 flavors.

?



<snip unread code>

Yes. You just forgot to mention that there are exactly 10 cookies of
each flavor.

Can there be duplicate flavors in each box of 10?

Of course. Any permutation possible, including all 10 of the same sort.





--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 01/04/2026 15:56, Michael S wrote:

On Wed, 1 Apr 2026 15:20:09 +0100
Bart <bc@freeuk.com> wrote:

On 01/04/2026 14:34, Michael S wrote:

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench
that I prepared is in C. The solution does not have to be in C, but
it would be significantly simpler for everybody, esp. for those
that are interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution
exists.

A solution to what? You haven't stated the problem!

If there are 20 boxes full of random sorts of cookies, and you take
one from each box (I assume blindly),

No, not blindly.

then you're going to have 20
random cookies.

I expect there's more to it than that.

"You have to take exactly one cookie from each box, all 20 of different sorts."

So, there are 20 sorts of cookies, which I've designated A, B, C, ... T.

There are 10 of each sort, so 200 cookies in all:

AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJ
KKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTT

But they're in a random order:

NMFHDPOGJOQHCGLNBARLFFDGCRKEPNGGFLKEKLLEEKATJLHHDTRLJKBSSJDFREJCBROFCEIDBRIISNQISHNHTPKLTFROSKFQBNLO
MIATPPCOJCOGGHCAHSAGTMIIMOEGSFNABPQRQNDMARPDQIPKTMQNQACLMRBOTJTIDFGMJKDEPHSEJSDSIMHCBNQEPTKBBJCQAAOM

These are used to fill 20 boxes with 10 cookies each:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 N Q F G E R R I S R M O T N A Q T D I K
2 M H F G K L E D H O I G M A R N J E M B
3 F C D F A J J B N S A G I B P Q T P H B
4 H G G L T K C R H K T H I P D A I H C J
5 D L C K J B B I T F P C M Q Q C D S B C
6 P N R E L S R I P Q P A O R I L F E N Q
7 O B K K H S O S K B C H E Q P M G J Q A
8 G A E L H J F N L N O S G N K R M S E A
9 J R P L D D C Q T L J A S D T B J D P O
10 O L N E T F E I F O C G F M M O K S T M

20 boxes horizontally, each holding 10 cookies numbered 1 to 10.

So, with full knowledge of the contents, I have to choose exactly one of
the cookies numbered 1 to 10 from each box, so that I end up with 20
cookies, all different, so one of each of the 20 sorts.

And this is guaranteed to be possible? I guess it's a bit harder than it seemed then.






--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution exists. I
don't ask you to repeat the proof. Just peek cookies!

============================================================================ //public domain code

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>


int main(void) {

//monotonic clock timing
struct timespec started, stopped;
void begintimer() {clock_gettime(CLOCK_MONOTONIC_RAW, &started);}
double elapsedMR(struct timespec started) {
const double B = 1e9;
clock_gettime(CLOCK_MONOTONIC_RAW, &stopped);
return (stopped.tv_sec-started.tv_sec) + ((stopped.tv_nsec-started.tv_nsec) / B);
}

//CPU timing
clock_t starttime;
starttime = clock();

//monotonic (elapsed) timing
begintimer();

//----------------------------------------------------------------------------
//fill a box of 20 sections with 10 cookies each, from 20 random
//cookie flavors - duplicate flavors allowed in each section
//----------------------------------------------------------------------------

//big beautiful box
int *box = malloc(200 * sizeof(int));

//the first cookie placed in each section of the box is one of the 20 flavors - this ensures all flavors are used at least once
//if Michael S challenge doesn't allow this non-random assignment, do something else.
int j = 0;
for (int i = 0; i < 200; i += 10) {box[i] = j++;}

//now randomly fill in the remaining 19 cookies in each section
srand(time(NULL));
for (int i = 1; i < 200; i += 10) {
for (int j = 0; j < 9; j++) {
int r = (rand() % 19) + 1;
box[i+j] = r;
}
}


//print contents of box column by row
printf("----------------------------------------------------------------------------------------------------------\n");
printf(" Random flavors in each box - duplicate flavors allowed\n ");
for (int i = 1; i <= 9; i++) {printf("%d ", i);}
for (int i = 10; i <= 20; i++) {printf("%d ", i);}
printf("\n----------------------------------------------------------------------------------------------------------\n");
int rows = 10, cols = 20, colwidth = 5;
for (int r = 1; r <= rows; r++) {
if (r <= 200) {
int nbr = r-1;
printf("%3d %-*c", r, colwidth, box[nbr] + 65);
for (int i = 0; i < cols-1; i++) {
nbr += rows;
if (nbr <= 200) {
printf("%-*c", colwidth, box[nbr] + 65);
}
}
printf("\n");
}
}
printf("----------------------------------------------------------------------------------------------------------\n");


//now randomly choose from each section until we have a flavor not in the used list
//this will require more than one pass thru the 20 sections
//result must be flavors A..T (1..20), not necessarily in order
//little fail somewhere - sometimes the 20th flavor isn't chosen
int chosencnt = 0;
char usedlist[2500] = {0}, chosen[150] = {0};
char theflavor[6];
for (int loop = 1; loop <= 2; loop++) {
for (int i = 0; i < 200; i+=10) {
int start = i; int end = i + 9;
for (int j = 1; j <= 20; j++) {
int r = (rand() % (end - start + 1)) + start;
sprintf(theflavor," %c ", box[r] + 65);
if (strstr(chosen, theflavor) == NULL) {
strncat(chosen, theflavor, strlen(theflavor));
chosencnt++;
if (chosencnt == 20) {break;}
break;
}
else
{
strncat(usedlist, theflavor, strlen(theflavor));
}
}
memset(usedlist,0,sizeof(usedlist));
}
if (chosencnt == 20) {break;}
}
printf("Chosen: %s\n",chosen);


//timing
printf("\nCPU time = %.5fs\n", ((double)(clock() - starttime)) / CLOCKS_PER_SEC);
printf("Elapsed time = %.5fs\n\n", elapsedMR(started));

free(box);
return 0;
} ============================================================================


77 SLOC

typically runs in 0.00018s on my system

But it's not perfect - it sometimes fails to get the 20th unique cookie flavor. Still looking at it.



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 4/1/2026 2:50 PM, Bart wrote:

On 01/04/2026 15:56, Michael S wrote:

On Wed, 1 Apr 2026 15:20:09 +0100
Bart <bc@freeuk.com> wrote:

On 01/04/2026 14:34, Michael S wrote:

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench
that I prepared is in C. The solution does not have to be in C, but
it would be significantly simpler for everybody, esp. for those
that are interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution
exists.

A solution to what? You haven't stated the problem!

If there are 20 boxes full of random sorts of cookies, and you take
one from each box (I assume blindly),

No, not blindly.

then you're going to have 20
random cookies.

I expect there's more to it than that.

"You have to take exactly one cookie from each box, all 20 of different
sorts."

So, there are 20 sorts of cookies, which I've designated A, B, C, ... T.

There are 10 of each sort, so 200 cookies in all:

AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJ
KKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTT

But they're in a random order:

NMFHDPOGJOQHCGLNBARLFFDGCRKEPNGGFLKEKLLEEKATJLHHDTRLJKBSSJDFREJCBROFCEIDBRIISNQISHNHTPKLTFROSKFQBNLO
MIATPPCOJCOGGHCAHSAGTMIIMOEGSFNABPQRQNDMARPDQIPKTMQNQACLMRBOTJTIDFGMJKDEPHSEJSDSIMHCBNQEPTKBBJCQAAOM

These are used to fill 20 boxes with 10 cookies each:

ÿÿÿ 1ÿ 2ÿ 3ÿ 4ÿ 5ÿ 6ÿ 7ÿ 8ÿ 9 10 11 12 13 14 15 16 17 18 19 20
ÿ1ÿ Nÿ Qÿ Fÿ Gÿ Eÿ Rÿ Rÿ Iÿ Sÿ Rÿ Mÿ Oÿ Tÿ Nÿ Aÿ Qÿ Tÿ Dÿ Iÿ K
ÿ2ÿ Mÿ Hÿ Fÿ Gÿ Kÿ Lÿ Eÿ Dÿ Hÿ Oÿ Iÿ Gÿ Mÿ Aÿ Rÿ Nÿ Jÿ Eÿ Mÿ B
ÿ3ÿ Fÿ Cÿ Dÿ Fÿ Aÿ Jÿ Jÿ Bÿ Nÿ Sÿ Aÿ Gÿ Iÿ Bÿ Pÿ Qÿ Tÿ Pÿ Hÿ B
ÿ4ÿ Hÿ Gÿ Gÿ Lÿ Tÿ Kÿ Cÿ Rÿ Hÿ Kÿ Tÿ Hÿ Iÿ Pÿ Dÿ Aÿ Iÿ Hÿ Cÿ J
ÿ5ÿ Dÿ Lÿ Cÿ Kÿ Jÿ Bÿ Bÿ Iÿ Tÿ Fÿ Pÿ Cÿ Mÿ Qÿ Qÿ Cÿ Dÿ Sÿ Bÿ C
ÿ6ÿ Pÿ Nÿ Rÿ Eÿ Lÿ Sÿ Rÿ Iÿ Pÿ Qÿ Pÿ Aÿ Oÿ Rÿ Iÿ Lÿ Fÿ Eÿ Nÿ Q
ÿ7ÿ Oÿ Bÿ Kÿ Kÿ Hÿ Sÿ Oÿ Sÿ Kÿ Bÿ Cÿ Hÿ Eÿ Qÿ Pÿ Mÿ Gÿ Jÿ Qÿ A
ÿ8ÿ Gÿ Aÿ Eÿ Lÿ Hÿ Jÿ Fÿ Nÿ Lÿ Nÿ Oÿ Sÿ Gÿ Nÿ Kÿ Rÿ Mÿ Sÿ Eÿ A
ÿ9ÿ Jÿ Rÿ Pÿ Lÿ Dÿ Dÿ Cÿ Qÿ Tÿ Lÿ Jÿ Aÿ Sÿ Dÿ Tÿ Bÿ Jÿ Dÿ Pÿ O
10ÿ Oÿ Lÿ Nÿ Eÿ Tÿ Fÿ Eÿ Iÿ Fÿ Oÿ Cÿ Gÿ Fÿ Mÿ Mÿ Oÿ Kÿ Sÿ Tÿ M

20 boxes horizontally, each holding 10 cookies numbered 1 to 10.

So, with full knowledge of the contents, I have to choose exactly one of
the cookies numbered 1 to 10 from each box, so that I end up with 20 cookies, all different, so one of each of the 20 sorts.

And this is guaranteed to be possible? I guess it's a bit harder than it seemed then.

It's only possible if all cookie flavors (or types, or sorts) are used
when filling the 20 boxes. In my submission I 'hacked' that by manually
assigning the first flavor in each box to be A..T (1..20). If that
hack isn't allowed I'll use some other method to make sure all flavors
are used at least once.

I filled the remaining 9 cookies in each box randomly.

Note: your grid looks exactly like a printout in my code - but to be
clear I didn't see your post until well after I finished my program.




--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish that
if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box


I can't understand your code, but it seems like you do a LOT more than
just 1 and 2.


Given those 2 constraints and using rand(), I saw a range of 9 to 16
(out of 20), with a typical score of 11-12.

Score = 1 point for each unique flavor you randomly choose. If you
choose a flavor from box 2 that you already chose from box 1, you get 0 points.

Here's that code:


//public domain code

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>


int main(void) {

//----------------------------------------------------------------------------
//fill a box of 20 sections with 10 cookies each, from 20 random
//cookie flavors - duplicate flavors allowed in each section
//----------------------------------------------------------------------------

//big beautiful box
int *box = malloc(200 * sizeof(int));

//randomly fill the box - this means all flavors might not be used
srand(time(NULL));
for (int i = 0; i < 200; i += 10) {
for (int j = 0; j <= 9; j++) {
int r = (rand() % 19) + 1;
box[i+j] = r;
}
}


//print contents of box column by row
printf("----------------------------------------------------------------------------------------------------------\n");
printf(" Random flavors in each box - duplicate flavors allowed\n ");
for (int i = 1; i <= 9; i++) {printf("%d ", i);}
for (int i = 10; i <= 20; i++) {printf("%d ", i);}
printf("\n----------------------------------------------------------------------------------------------------------\n");
int rows = 10, cols = 20, colwidth = 5;
for (int r = 1; r <= rows; r++) {
if (r <= 200) {
int nbr = r-1;
printf("%3d %-*c", r, colwidth, box[nbr] + 65);
for (int i = 0; i < cols-1; i++) {
nbr += rows;
if (nbr <= 200) {
printf("%-*c", colwidth, box[nbr] + 65);
}
}
printf("\n");
}
}
printf("----------------------------------------------------------------------------------------------------------\n");


//chose a random flavor, if it hasn't been used add it to the chosen array
char chosen[150] = {0};
char randoms[150] = {0};
char theflavor[8], therandom[8];
int chosencnt = 0;
for (int i = 0; i < 200; i+=10) {
int start = i; int end = i + 9;
int r = (rand() % (end - start + 1)) + start;
sprintf(theflavor," %c ", box[r] + 65);
strncat(randoms , theflavor, strlen(theflavor));
if (strstr(chosen, theflavor) == NULL) {
strncat(chosen , theflavor, strlen(theflavor));
chosencnt++;
}
}

printf("Random: %s\n", randoms);
printf("Chosen: %s\n", chosen);
printf("Score : %d\n", chosencnt);

free(box);
return 0;
}



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 01/04/2026 20:56, DFS wrote:

On 4/1/2026 2:50 PM, Bart wrote:

On 01/04/2026 15:56, Michael S wrote:

On Wed, 1 Apr 2026 15:20:09 +0100
Bart <bc@freeuk.com> wrote:

On 01/04/2026 14:34, Michael S wrote:

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench
that I prepared is in C. The solution does not have to be in C, but
it would be significantly simpler for everybody, esp. for those
that are interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution
exists.

A solution to what? You haven't stated the problem!

If there are 20 boxes full of random sorts of cookies, and you take
one from each box (I assume blindly),

No, not blindly.

then you're going to have 20
random cookies.

I expect there's more to it than that.

"You have to take exactly one cookie from each box, all 20 of different
sorts."

So, there are 20 sorts of cookies, which I've designated A, B, C, ... T.

There are 10 of each sort, so 200 cookies in all:

AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJ
KKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTT

But they're in a random order:

NMFHDPOGJOQHCGLNBARLFFDGCRKEPNGGFLKEKLLEEKATJLHHDTRLJKBSSJDFREJCBROFCEIDBRIISNQISHNHTPKLTFROSKFQBNLO
MIATPPCOJCOGGHCAHSAGTMIIMOEGSFNABPQRQNDMARPDQIPKTMQNQACLMRBOTJTIDFGMJKDEPHSEJSDSIMHCBNQEPTKBBJCQAAOM

These are used to fill 20 boxes with 10 cookies each:

ÿÿÿÿ 1ÿ 2ÿ 3ÿ 4ÿ 5ÿ 6ÿ 7ÿ 8ÿ 9 10 11 12 13 14 15 16 17 18 19 20
ÿÿ1ÿ Nÿ Qÿ Fÿ Gÿ Eÿ Rÿ Rÿ Iÿ Sÿ Rÿ Mÿ Oÿ Tÿ Nÿ Aÿ Qÿ Tÿ Dÿ Iÿ K
ÿÿ2ÿ Mÿ Hÿ Fÿ Gÿ Kÿ Lÿ Eÿ Dÿ Hÿ Oÿ Iÿ Gÿ Mÿ Aÿ Rÿ Nÿ Jÿ Eÿ Mÿ B
ÿÿ3ÿ Fÿ Cÿ Dÿ Fÿ Aÿ Jÿ Jÿ Bÿ Nÿ Sÿ Aÿ Gÿ Iÿ Bÿ Pÿ Qÿ Tÿ Pÿ Hÿ B
ÿÿ4ÿ Hÿ Gÿ Gÿ Lÿ Tÿ Kÿ Cÿ Rÿ Hÿ Kÿ Tÿ Hÿ Iÿ Pÿ Dÿ Aÿ Iÿ Hÿ Cÿ J
ÿÿ5ÿ Dÿ Lÿ Cÿ Kÿ Jÿ Bÿ Bÿ Iÿ Tÿ Fÿ Pÿ Cÿ Mÿ Qÿ Qÿ Cÿ Dÿ Sÿ Bÿ C
ÿÿ6ÿ Pÿ Nÿ Rÿ Eÿ Lÿ Sÿ Rÿ Iÿ Pÿ Qÿ Pÿ Aÿ Oÿ Rÿ Iÿ Lÿ Fÿ Eÿ Nÿ Q
ÿÿ7ÿ Oÿ Bÿ Kÿ Kÿ Hÿ Sÿ Oÿ Sÿ Kÿ Bÿ Cÿ Hÿ Eÿ Qÿ Pÿ Mÿ Gÿ Jÿ Qÿ A
ÿÿ8ÿ Gÿ Aÿ Eÿ Lÿ Hÿ Jÿ Fÿ Nÿ Lÿ Nÿ Oÿ Sÿ Gÿ Nÿ Kÿ Rÿ Mÿ Sÿ Eÿ A
ÿÿ9ÿ Jÿ Rÿ Pÿ Lÿ Dÿ Dÿ Cÿ Qÿ Tÿ Lÿ Jÿ Aÿ Sÿ Dÿ Tÿ Bÿ Jÿ Dÿ Pÿ O
10ÿ Oÿ Lÿ Nÿ Eÿ Tÿ Fÿ Eÿ Iÿ Fÿ Oÿ Cÿ Gÿ Fÿ Mÿ Mÿ Oÿ Kÿ Sÿ Tÿ M

20 boxes horizontally, each holding 10 cookies numbered 1 to 10.

So, with full knowledge of the contents, I have to choose exactly one
of the cookies numbered 1 to 10 from each box, so that I end up with
20 cookies, all different, so one of each of the 20 sorts.

And this is guaranteed to be possible? I guess it's a bit harder than
it seemed then.

ÿIt's only possible if all cookie flavors (or types, or sorts) are used when filling the 20 boxes.ÿ In my submission I 'hacked' that by manually
ÿassigning the first flavor in each box to be A..Tÿ (1..20).ÿ If that
hack isn't allowed I'll use some other method to make sure all flavors
are used at least once.

I did it by populating an array with 'AAA....TTT' then randomly
shuffling as shown above. After that, copying sequentially into the
boxes boxes.

I filled the remaining 9 cookies in each box randomly.

Note: your grid looks exactly like a printout in my code - but to be
clear I didn't see your post until well after I finished my program.

(I tried your code, but it only ran under WSL, I think due to timing functions. It would have needed those local functions moved anyway to
use with my favoured compiler.)

I did also try a solution of my own, just a bunch of nested loops which
would select and unselect boxes until 20 cookies are chosen. But with
some selections it would get stuck in a loop.

Probably the next attempt would use trial and error, maybe some random selections like yours.

But I won't be submitting a solution as I wouldn't have enough
confidence it. Besides I still have to write it all in C.)



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or otherwise) and your challenge is to
provide an algorithm to select 1 cookie from each box, such that one of each cookie type is selected.

The supplied code is some kind of test bench to check your solution. Your job is to supply the
missing solver() function so that the test bench program is successful. You do not need to fill the
boxes at all (they are supplied to you to solve), and you do not need to choose the cookies you
select randomly! (If you select randomly, you are highly likely to select two cookies of the same
type at some point, so you will fail...)


Mike.


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 02/04/2026 16:25, Mike Terry wrote:

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish
that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or
otherwise) and your challenge is to provide an algorithm to select 1
cookie from each box, such that one of each cookie type is selected.

The supplied code is some kind of test bench to check your solution.
Your job is to supply the missing solver() function so that the test
bench program is successful.ÿ You do not need to fill the boxes at all
(they are supplied to you to solve), and you do not need to choose the cookies you select randomly!ÿ (If you select randomly, you are highly
likely to select two cookies of the same type at some point, so you will fail...)

I didn't notice the test bench code! I thought that was some reference implementation that it would be better not to peek at.

Looking at it now, it is quite daunting to write a solver function
without first knowing how everythings works. The poor coding style
doesn't help (actually, that might just because it's in C).

To start with, I got rid of all the argz/v processing and set rep1/2 to
1; I won't care about timing to start with, only to get something working.

Then I added a dummy solver() routine in the same module. Now when it
runs, it fails, but it also prints the contents of the boxes which is
helpful.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 4/2/2026 11:25 AM, Mike Terry wrote:

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish
that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or
otherwise) and your challenge is to provide an algorithm to select 1
cookie from each box, such that one of each cookie type is selected.

The supplied code is some kind of test bench to check your solution.
Your job is to supply the missing solver() function so that the test
bench program is successful.ÿ You do not need to fill the boxes at all
(they are supplied to you to solve), and you do not need to choose the cookies you select randomly!ÿ (If you select randomly, you are highly
likely to select two cookies of the same type at some point, so you will fail...)

This is a far better explanation than the original, but it's still
confusing.

Let me talk/think it through:

Per Michael's original you have to choose exactly one cookie from each
box, and end up with 20 different types of cookie. That means each box contains at least one of the 20 cookie types (also could be 2+ of the
same type). If I can't choose randomly, I would naively just evaluate
each cookie in the box against what I've already chosen, grab one that
hasn't been chosen, and move on to the next box.

But I bet that by the 12th to 15th box, it won't have a cookie type that hasn't been chosen. So there's no way I could get to 20 cookie types
with one selection from each box. I would have to start over, maybe
begin with a different cookie type than I started with the first time,
then hit the wall again, etc.

Does that jibe with your understanding?

The code I wrote initially made sure each box contained at least one of
the 20 types, then filled the rest randomly. But then I made random
choices. So I can go back and redo the code and NOT make random choices
and see what happens.

I see some sorting in my future.

Thanks for the analysis.

Did you try it?





--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 02/04/2026 18:03, DFS wrote:

NOT make random choices

So ... just don't mix up the cookies in the first place.

You buy 20 packets of cookies and you empty the entire packet into each jar.

Then when you want one of each flavour, you simply open each jar in turn
and take one cookie.


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 02/04/2026 18:03, DFS wrote:

On 4/2/2026 11:25 AM, Mike Terry wrote:

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish
that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or
otherwise) and your challenge is to provide an algorithm to select 1
cookie from each box, such that one of each cookie type is selected.

The supplied code is some kind of test bench to check your solution.
Your job is to supply the missing solver() function so that the test
bench program is successful.ÿ You do not need to fill the boxes at all
(they are supplied to you to solve), and you do not need to choose the
cookies you select randomly!ÿ (If you select randomly, you are highly
likely to select two cookies of the same type at some point, so you
will fail...)

This is a far better explanation than the original, but it's still confusing.

Let me talk/think it through:

Per Michael's original you have to choose exactly one cookie from each
box, and end up with 20 different types of cookie.ÿ That means each box contains at least one of the 20 cookie types (also could be 2+ of the
same type).ÿ If I can't choose randomly, I would naively just evaluate
each cookie in the box against what I've already chosen, grab one that hasn't been chosen, and move on to the next box.

But I bet that by the 12th to 15th box, it won't have a cookie type that hasn't been chosen.ÿ So there's no way I could get to 20 cookie types
with one selection from each box.ÿ I would have to start over, maybe
begin with a different cookie type than I started with the first time,
then hit the wall again, etc.

Does that jibe with your understanding?

The code I wrote initially made sure each box contained at least one of
the 20 types, then filled the rest randomly.

Hang on, if each box is guaranteed to contain at least one of any cookie you're looking for, then it can make it trivial.

At least, with my poor algorithm, it would always work, since it starts
by looking for a type A in box 1, box B in box 2, and so on.

It would go wrong if it got to type F say, and that is only present in
boxes already picked. Here I start redoing some earlier choices, which
is where it can go wrong.



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Wed, 1 Apr 2026 17:24:19 -0400
DFS <nospam@dfs.com> wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish
that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I can't understand your code, but it seems like you do a LOT more
than just 1 and 2.

Given those 2 constraints and using rand(), I saw a range of 9 to 16
(out of 20), with a typical score of 11-12.

Score = 1 point for each unique flavor you randomly choose. If you
choose a flavor from box 2 that you already chose from box 1, you get
0 points.

Here's that code:

//public domain code

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

int main(void) {

//----------------------------------------------------------------------------
//fill a box of 20 sections with 10 cookies each, from 20
random //cookie flavors - duplicate flavors allowed in each section
//----------------------------------------------------------------------------

//big beautiful box
int *box = malloc(200 * sizeof(int));

//randomly fill the box - this means all flavors might not be
used srand(time(NULL));
for (int i = 0; i < 200; i += 10) {
for (int j = 0; j <= 9; j++) {
int r = (rand() % 19) + 1;
box[i+j] = r;
}
}


//print contents of box column by row
printf("----------------------------------------------------------------------------------------------------------\n");
printf(" Random flavors in each box -
duplicate flavors allowed\n ");
for (int i = 1; i <= 9; i++) {printf("%d ", i);}
for (int i = 10; i <= 20; i++) {printf("%d ", i);}
printf("\n----------------------------------------------------------------------------------------------------------\n");
int rows = 10, cols = 20, colwidth = 5;
for (int r = 1; r <= rows; r++) {
if (r <= 200) {
int nbr = r-1;
printf("%3d %-*c", r, colwidth, box[nbr]
+ 65); for (int i = 0; i < cols-1; i++) {
nbr += rows;
if (nbr <= 200) {
printf("%-*c", colwidth,
box[nbr] + 65); }
}
printf("\n");
}
}
printf("----------------------------------------------------------------------------------------------------------\n");


//chose a random flavor, if it hasn't been used add it to the
chosen array char chosen[150] = {0};
char randoms[150] = {0};
char theflavor[8], therandom[8];
int chosencnt = 0;
for (int i = 0; i < 200; i+=10) {
int start = i; int end = i + 9;
int r = (rand() % (end - start + 1)) + start;
sprintf(theflavor," %c ", box[r] + 65);
strncat(randoms , theflavor, strlen(theflavor));
if (strstr(chosen, theflavor) == NULL) {
strncat(chosen , theflavor,
strlen(theflavor)); chosencnt++;
}
}

printf("Random: %s\n", randoms);
printf("Chosen: %s\n", chosen);
printf("Score : %d\n", chosencnt);

free(box);
return 0;
}

I'l look at your solution not before it is implemented according to
my spec: as a module solver.c that implements function solver() as
declared in solver.h and linkable with tb.c.

tb.c is provided for you to use for testing your solution. Don't waste
time writing your own main().





--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 02/04/2026 18:03, DFS wrote:

On 4/2/2026 11:25 AM, Mike Terry wrote:

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or otherwise) and your challenge is
to provide an algorithm to select 1 cookie from each box, such that one of each cookie type is
selected.

The supplied code is some kind of test bench to check your solution. Your job is to supply the
missing solver() function so that the test bench program is successful.? You do not need to fill
the boxes at all (they are supplied to you to solve), and you do not need to choose the cookies
you select randomly!? (If you select randomly, you are highly likely to select two cookies of the
same type at some point, so you will fail...)

This is a far better explanation than the original, but it's still confusing.

Let me talk/think it through:

Per Michael's original you have to choose exactly one cookie from each box, and end up with 20
different types of cookie.? That means each box contains at least one of the 20 cookie types (also
could be 2+ of the same type).? If I can't choose randomly, I would naively just evaluate each
cookie in the box against what I've already chosen, grab one that hasn't been chosen, and move on to
the next box.

But I bet that by the 12th to 15th box, it won't have a cookie type that hasn't been chosen.? So
there's no way I could get to 20 cookie types with one selection from each box.? I would have to
start over, maybe begin with a different cookie type than I started with the first time, then hit
the wall again, etc.

Does that jibe with your understanding?

Yes, that's exactly the problem. You need to /search/ for a solution, which requires some kind of
search strategy. You won't be able to make a definitively correct choice at each decision point,
because that choice can affect the effective constraints way down the line as you explain. It might
turn out that the 1st choice you made seemed reasonable right at the start, but when you get to the
15th choice, nothing works. So you will need to back-track and try a different choice at one of
your decision points, and if that doesn't work maybe back-track even further, and so on.

(These types of problems are common - e.g. we have to fit various tiles or blocks to make a
particular shape, or a jigsaw where many pieces might match any particular edge pattern, but only a
small number of fully completed solutions exist. A typical approach is to make "guesses" that match
all constraints at the time the guess is made, and continue until it becomes clear no further
guesses can work, at which point go back a bit and try a different choice and so on...)

Some kind of recursive logic would be natural to give structure to the back-tracking, but the
devil's in the details to make the solver efficient. An alternative approach might be to just
choose randomly and see if it works, and if it doesn't, throw everything away and start from scratch
again - that's going to work /eventually/, but isn't going to satisfy the performance requirements!

The code I wrote initially made sure each box contained at least one of the 20 types, then filled
the rest randomly.

I think I know what you are trying to say, but your words have come out wrong - each box can /only/
contain cookies of the given types, so must obviously contains "at least one of the 20 types"! Hmm,
maybe you're thinking all boxes must contain one of /each/ of the 20 types? That's not right - it's
possible box1 contains only type1 cookies, box2 contains only type2 cookies and so on...

Anyhow, Michael says someone has proved that every possible assignment of the 400 given cookies to
boxes has a solution, so to create a starting puzzle you can just assign the 400 given cookies
randomly to boxes. (Perhaps start with the 400 cookies in a single line, then "shuffle" them, then
deal the first 20 to box1, the next 20 to box2, etc..)

But then I made random choices.? So I can go back and redo the code and NOT make
random choices and see what happens.

I see some sorting in my future.

Thanks for the analysis.

Did you try it?

I haven't tried to code a solution, but to be honest I probably have a dozen or so "similar type"
problems approached with C/C++ code, so I could maybe start with one of them to save some time that
way. (But I'm busy with other stuff at the moment.)

Here are some off the cuff thoughts:

1. Illustrations have showed a grid of cookie types, 20 columns (boxes) and 10 rows,
but lots of that data is redundant - we only really need to consider:
a) which boxes contain cookies for each cookie type (not how many of each type)
b) which cookie types appear in each box (again not how many of each type)
Also, there is no cookie order within any box...
So the first thing I'd do with a presented input is extract (a) and (b) and just
work with that.

2. There's a pleasing "symmetry" between boxes and cookie types.
E.g. you could decide to make "guesses" successively for each cookie-type
(guessing which box to take it from), or you could decide to guess successively
for the various box numbers (guessing which cookie type to take from it).

3. Both the cookie types AND the boxes, can become more or less "constrained"
as successive guesses are made. Probably a good strategy is to guess for
the most constrained cookie type /or/ box at each decision point. It's
not easy for me to explain exactly why I think that is best, but it seems
natural to me... E.g. if cookie-type-7 can be taken from 5 boxes, and
box4 contains only 3 cookie-types, then box4 is "more constrained" and
so my thinking would be to investigate what to take from box4 rather
than which box will I take a type-7 cookie from...
But... code working like that will probably be more fiddly to get right
and test etc.. (Normally I start with simple code, then start trying
to improve it if it's not "good enough" as it stands.)

Mike.


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Thu, 2 Apr 2026 16:25:49 +0100
Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take
exactly one cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish
that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or
otherwise) and your challenge is to provide an algorithm to select 1
cookie from each box, such that one of each cookie type is selected.

The supplied code is some kind of test bench to check your solution.
Your job is to supply the missing solver() function so that the test
bench program is successful. You do not need to fill the boxes at
all (they are supplied to you to solve), and you do not need to
choose the cookies you select randomly! (If you select randomly, you
are highly likely to select two cookies of the same type at some
point, so you will fail...)

Mike.

Correct.
I hoped that it was very clear, but some people are much better at misunderstanding than I can imagine.



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Thu, 2 Apr 2026 17:10:07 +0100
Bart <bc@freeuk.com> wrote:

On 02/04/2026 16:25, Mike Terry wrote:

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed
in 20 boxes, again, 10 cookies in each boxes. You have to take
exactly one cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to accomplish
that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or otherwise) and your challenge is to provide an algorithm to select
1 cookie from each box, such that one of each cookie type is
selected.

The supplied code is some kind of test bench to check your
solution. Your job is to supply the missing solver() function so
that the test bench program is successful.? You do not need to fill
the boxes at all (they are supplied to you to solve), and you do
not need to choose the cookies you select randomly!? (If you select randomly, you are highly likely to select two cookies of the same
type at some point, so you will fail...)

I didn't notice the test bench code! I thought that was some
reference implementation that it would be better not to peek at.

Looking at it now, it is quite daunting to write a solver function
without first knowing how everythings works. The poor coding style
doesn't help (actually, that might just because it's in C).

The coding style is excellent.
After all, it's mine!

To start with, I got rid of all the argz/v processing and set rep1/2
to 1; I won't care about timing to start with, only to get something
working.

You wasted your time.
Instead, you could get the same effect by running your exe as
tb 1 1

Then I added a dummy solver() routine in the same module.

solver in the same moodule with test bench is bad coding style.
Much cleaner to keep it in the separate module.

Now when it
runs, it fails, but it also prints the contents of the boxes which is helpful.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Thu, 2 Apr 2026 19:50:06 +0100
Bart <bc@freeuk.com> wrote:

On 02/04/2026 18:03, DFS wrote:

On 4/2/2026 11:25 AM, Mike Terry wrote:

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed
in 20 boxes, again, 10 cookies in each boxes. You have to take
exactly one cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to
accomplish that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or
otherwise) and your challenge is to provide an algorithm to select
1 cookie from each box, such that one of each cookie type is
selected.

The supplied code is some kind of test bench to check your
solution. Your job is to supply the missing solver() function so
that the test bench program is successful.? You do not need to
fill the boxes at all (they are supplied to you to solve), and you
do not need to choose the cookies you select randomly!? (If you
select randomly, you are highly likely to select two cookies of
the same type at some point, so you will fail...)

This is a far better explanation than the original, but it's still confusing.

Let me talk/think it through:

Per Michael's original you have to choose exactly one cookie from
each box, and end up with 20 different types of cookie.? That means
each box contains at least one of the 20 cookie types (also could
be 2+ of the same type).? If I can't choose randomly, I would
naively just evaluate each cookie in the box against what I've
already chosen, grab one that hasn't been chosen, and move on to
the next box.

But I bet that by the 12th to 15th box, it won't have a cookie type
that hasn't been chosen.? So there's no way I could get to 20
cookie types with one selection from each box.? I would have to
start over, maybe begin with a different cookie type than I started
with the first time, then hit the wall again, etc.

Does that jibe with your understanding?

The code I wrote initially made sure each box contained at least
one of the 20 types, then filled the rest randomly.

Hang on, if each box is guaranteed to contain at least one of any
cookie you're looking for, then it can make it trivial.

At least, with my poor algorithm, it would always work, since it
starts by looking for a type A in box 1, box B in box 2, and so on.

It would go wrong if it got to type F say, and that is only present
in boxes already picked. Here I start redoing some earlier choices,
which is where it can go wrong.

Seems like you are trying to solve by exhausting.
If you read my original post, you'd see that I suggest against it and
give an explanation why it is not a good idea.


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Thu, 2 Apr 2026 20:13:50 +0100
Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:

On 02/04/2026 18:03, DFS wrote:

On 4/2/2026 11:25 AM, Mike Terry wrote:

On 01/04/2026 22:24, DFS wrote:

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed
in 20 boxes, again, 10 cookies in each boxes. You have to take
exactly one cookie from each box, all 20 of different sorts.

I say it's impossible (or extremely, extremely rare) to
accomplish that if you have to:

1) fill the boxes randomly, and
2) make only one random choice from each box

I think you're misunderstanding the challenge.

AIUI, you're /given/ the boxes, filled with cookies (randomly or
otherwise) and your challenge is to provide an algorithm to select
1 cookie from each box, such that one of each cookie type is
selected.

The supplied code is some kind of test bench to check your
solution. Your job is to supply the missing solver() function so
that the test bench program is successful.? You do not need to
fill the boxes at all (they are supplied to you to solve), and you
do not need to choose the cookies you select randomly!? (If you
select randomly, you are highly likely to select two cookies of
the same type at some point, so you will fail...)

This is a far better explanation than the original, but it's still confusing.

Let me talk/think it through:

Per Michael's original you have to choose exactly one cookie from
each box, and end up with 20 different types of cookie.? That means
each box contains at least one of the 20 cookie types (also could
be 2+ of the same type).? If I can't choose randomly, I would
naively just evaluate each cookie in the box against what I've
already chosen, grab one that hasn't been chosen, and move on to
the next box.

But I bet that by the 12th to 15th box, it won't have a cookie type
that hasn't been chosen.? So there's no way I could get to 20
cookie types with one selection from each box.? I would have to
start over, maybe begin with a different cookie type than I started
with the first time, then hit the wall again, etc.

Does that jibe with your understanding?

Yes, that's exactly the problem. You need to /search/ for a
solution, which requires some kind of search strategy. You won't be
able to make a definitively correct choice at each decision point,
because that choice can affect the effective constraints way down the
line as you explain. It might turn out that the 1st choice you made
seemed reasonable right at the start, but when you get to the 15th
choice, nothing works. So you will need to back-track and try a
different choice at one of your decision points, and if that doesn't
work maybe back-track even further, and so on.

(These types of problems are common - e.g. we have to fit various
tiles or blocks to make a particular shape, or a jigsaw where many
pieces might match any particular edge pattern, but only a small
number of fully completed solutions exist. A typical approach is to
make "guesses" that match all constraints at the time the guess is
made, and continue until it becomes clear no further guesses can
work, at which point go back a bit and try a different choice and so
on...)

Some kind of recursive logic would be natural to give structure to
the back-tracking, but the devil's in the details to make the solver efficient. An alternative approach might be to just choose randomly
and see if it works, and if it doesn't, throw everything away and
start from scratch again - that's going to work /eventually/, but
isn't going to satisfy the performance requirements!

The code I wrote initially made sure each box contained at least
one of the 20 types, then filled the rest randomly.

I think I know what you are trying to say, but your words have come
out wrong - each box can /only/ contain cookies of the given types,
so must obviously contains "at least one of the 20 types"! Hmm,
maybe you're thinking all boxes must contain one of /each/ of the 20
types? That's not right - it's possible box1 contains only type1
cookies, box2 contains only type2 cookies and so on...

Anyhow, Michael says someone has proved that every possible
assignment of the 400 given cookies to boxes has a solution, so to
create a starting puzzle you can just assign the 400 given cookies
randomly to boxes. (Perhaps start with the 400 cookies in a single
line, then "shuffle" them, then deal the first 20 to box1, the next
20 to box2, etc..)

But then I made random choices.? So I can go back and redo the code
and NOT make random choices and see what happens.

I see some sorting in my future.

Thanks for the analysis.

Did you try it?

I haven't tried to code a solution, but to be honest I probably have
a dozen or so "similar type" problems approached with C/C++ code, so
I could maybe start with one of them to save some time that way.
(But I'm busy with other stuff at the moment.)

Here are some off the cuff thoughts:

1. Illustrations have showed a grid of cookie types, 20 columns
(boxes) and 10 rows, but lots of that data is redundant - we only
really need to consider: a) which boxes contain cookies for each
cookie type (not how many of each type) b) which cookie types appear
in each box (again not how many of each type) Also, there is no
cookie order within any box... So the first thing I'd do with a
presented input is extract (a) and (b) and just work with that.

2. There's a pleasing "symmetry" between boxes and cookie types.
E.g. you could decide to make "guesses" successively for each cookie-type (guessing which box to take it from), or you could decide
to guess successively for the various box numbers (guessing which
cookie type to take from it).

3. Both the cookie types AND the boxes, can become more or less "constrained" as successive guesses are made. Probably a good
strategy is to guess for the most constrained cookie type /or/ box at
each decision point. It's not easy for me to explain exactly why I
think that is best, but it seems natural to me... E.g. if
cookie-type-7 can be taken from 5 boxes, and box4 contains only 3 cookie-types, then box4 is "more constrained" and so my thinking
would be to investigate what to take from box4 rather than which box
will I take a type-7 cookie from... But... code working like that
will probably be more fiddly to get right and test etc.. (Normally I
start with simple code, then start trying to improve it if it's not
"good enough" as it stands.)

Mike.

Interesting thing about that problem is that while it looks NP-complete
at the 1st glance, it turns out dramatically simpler than that.
My current solution is O(N*N*M). I would not be surprised if there
exist solutions with even lower computational complexity than that.


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 01/04/2026 19:50, Bart wrote:

On 01/04/2026 15:56, Michael S wrote:

On Wed, 1 Apr 2026 15:20:09 +0100
Bart <bc@freeuk.com> wrote:

On 01/04/2026 14:34, Michael S wrote:

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench
that I prepared is in C. The solution does not have to be in C, but
it would be significantly simpler for everybody, esp. for those
that are interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution
exists.

A solution to what? You haven't stated the problem!

If there are 20 boxes full of random sorts of cookies, and you take
one from each box (I assume blindly),

No, not blindly.

then you're going to have 20
random cookies.

I expect there's more to it than that.

"You have to take exactly one cookie from each box, all 20 of different
sorts."

So, there are 20 sorts of cookies, which I've designated A, B, C, ... T.

There are 10 of each sort, so 200 cookies in all:

AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJ
KKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTT

But they're in a random order:

NMFHDPOGJOQHCGLNBARLFFDGCRKEPNGGFLKEKLLEEKATJLHHDTRLJKBSSJDFREJCBROFCEIDBRIISNQISHNHTPKLTFROSKFQBNLO
MIATPPCOJCOGGHCAHSAGTMIIMOEGSFNABPQRQNDMARPDQIPKTMQNQACLMRBOTJTIDFGMJKDEPHSEJSDSIMHCBNQEPTKBBJCQAAOM

These are used to fill 20 boxes with 10 cookies each:

ÿÿÿ 1ÿ 2ÿ 3ÿ 4ÿ 5ÿ 6ÿ 7ÿ 8ÿ 9 10 11 12 13 14 15 16 17 18 19 20
ÿ1ÿ Nÿ Qÿ Fÿ Gÿ Eÿ Rÿ Rÿ Iÿ Sÿ Rÿ Mÿ Oÿ Tÿ Nÿ Aÿ Qÿ Tÿ Dÿ Iÿ K
ÿ2ÿ Mÿ Hÿ Fÿ Gÿ Kÿ Lÿ Eÿ Dÿ Hÿ Oÿ Iÿ Gÿ Mÿ Aÿ Rÿ Nÿ Jÿ Eÿ Mÿ B
ÿ3ÿ Fÿ Cÿ Dÿ Fÿ Aÿ Jÿ Jÿ Bÿ Nÿ Sÿ Aÿ Gÿ Iÿ Bÿ Pÿ Qÿ Tÿ Pÿ Hÿ B
ÿ4ÿ Hÿ Gÿ Gÿ Lÿ Tÿ Kÿ Cÿ Rÿ Hÿ Kÿ Tÿ Hÿ Iÿ Pÿ Dÿ Aÿ Iÿ Hÿ Cÿ J
ÿ5ÿ Dÿ Lÿ Cÿ Kÿ Jÿ Bÿ Bÿ Iÿ Tÿ Fÿ Pÿ Cÿ Mÿ Qÿ Qÿ Cÿ Dÿ Sÿ Bÿ C
ÿ6ÿ Pÿ Nÿ Rÿ Eÿ Lÿ Sÿ Rÿ Iÿ Pÿ Qÿ Pÿ Aÿ Oÿ Rÿ Iÿ Lÿ Fÿ Eÿ Nÿ Q
ÿ7ÿ Oÿ Bÿ Kÿ Kÿ Hÿ Sÿ Oÿ Sÿ Kÿ Bÿ Cÿ Hÿ Eÿ Qÿ Pÿ Mÿ Gÿ Jÿ Qÿ A
ÿ8ÿ Gÿ Aÿ Eÿ Lÿ Hÿ Jÿ Fÿ Nÿ Lÿ Nÿ Oÿ Sÿ Gÿ Nÿ Kÿ Rÿ Mÿ Sÿ Eÿ A
ÿ9ÿ Jÿ Rÿ Pÿ Lÿ Dÿ Dÿ Cÿ Qÿ Tÿ Lÿ Jÿ Aÿ Sÿ Dÿ Tÿ Bÿ Jÿ Dÿ Pÿ O
10ÿ Oÿ Lÿ Nÿ Eÿ Tÿ Fÿ Eÿ Iÿ Fÿ Oÿ Cÿ Gÿ Fÿ Mÿ Mÿ Oÿ Kÿ Sÿ Tÿ M

20 boxes horizontally, each holding 10 cookies numbered 1 to 10.

So, with full knowledge of the contents, I have to choose exactly one of
the cookies numbered 1 to 10 from each box, so that I end up with 20 cookies, all different, so one of each of the 20 sorts.

And this is guaranteed to be possible? I guess it's a bit harder than it seemed then.

This is only ever swapping out cookies that come from the same jar.

Which means that a solution is not always possible - there is no jar
that contains one of the duplicated flavours and one of the missing
flavours.

eg, when it works:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 : T T B Q L A O R Q M S B B E M P E J C L
1 : I D B O E L I N S T H F D I O A F K D H
2 : R O F P Q L J D K O A D L L N N I L I G
3 : H R J K K C T B T F Q T H S J C F S I F
4 : K P P A I E F S L B G C G Q P P A F R S
5 : G H C C H C A N N M O G F O C G E F H K
6 : M K Q N E J G E B Q J O A N I A G E M R
7 : D D R J M N S H N P N T R D A G C G E H
8 : Q L R P A P R T M J O T S R Q D M P J K
9 : O K Q I C I B S B K E S D M L B J M H T

Choosing one cookie from each jar ...
choosen: T T B Q L A O R Q M S B B E M P E J C L

Swapping B for F in jar 2
Swapping B for D in jar 11
Swapping E for I in jar 13
Swapping L for H in jar 4
Swapping M for K in jar 9
Swapping Q for N in jar 3
Swapping T for G in jar 0
Solved!

choosen: G T F N H A O R Q K S D B I M P E J C L

When it doesn't work, then you'd have start swapping cookies between
different jars. I guess that is the hard part.





--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 04/04/2026 07:43, Richard Harnden wrote:

On 01/04/2026 19:50, Bart wrote:

On 01/04/2026 15:56, Michael S wrote:

On Wed, 1 Apr 2026 15:20:09 +0100
Bart <bc@freeuk.com> wrote:

On 01/04/2026 14:34, Michael S wrote:

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench
that I prepared is in C. The solution does not have to be in C, but
it would be significantly simpler for everybody, esp. for those
that are interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution
exists.

A solution to what? You haven't stated the problem!

If there are 20 boxes full of random sorts of cookies, and you take
one from each box (I assume blindly),

No, not blindly.

then you're going to have 20
random cookies.

I expect there's more to it than that.

"You have to take exactly one cookie from each box, all 20 of different
sorts."

So, there are 20 sorts of cookies, which I've designated A, B, C, ... T.

There are 10 of each sort, so 200 cookies in all:

AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDDEEEEEEEEEEFFFFFFFFFFGGGGGGGGGGHHHHHHHHHHIIIIIIIIIIJJJJJJJJJJ
KKKKKKKKKKLLLLLLLLLLMMMMMMMMMMNNNNNNNNNNOOOOOOOOOOPPPPPPPPPPQQQQQQQQQQRRRRRRRRRRSSSSSSSSSSTTTTTTTTTT

But they're in a random order:

NMFHDPOGJOQHCGLNBARLFFDGCRKEPNGGFLKEKLLEEKATJLHHDTRLJKBSSJDFREJCBROFCEIDBRIISNQISHNHTPKLTFROSKFQBNLO
MIATPPCOJCOGGHCAHSAGTMIIMOEGSFNABPQRQNDMARPDQIPKTMQNQACLMRBOTJTIDFGMJKDEPHSEJSDSIMHCBNQEPTKBBJCQAAOM

These are used to fill 20 boxes with 10 cookies each:

ÿÿÿÿ 1ÿ 2ÿ 3ÿ 4ÿ 5ÿ 6ÿ 7ÿ 8ÿ 9 10 11 12 13 14 15 16 17 18 19 20
ÿÿ1ÿ Nÿ Qÿ Fÿ Gÿ Eÿ Rÿ Rÿ Iÿ Sÿ Rÿ Mÿ Oÿ Tÿ Nÿ Aÿ Qÿ Tÿ Dÿ Iÿ K
ÿÿ2ÿ Mÿ Hÿ Fÿ Gÿ Kÿ Lÿ Eÿ Dÿ Hÿ Oÿ Iÿ Gÿ Mÿ Aÿ Rÿ Nÿ Jÿ Eÿ Mÿ B
ÿÿ3ÿ Fÿ Cÿ Dÿ Fÿ Aÿ Jÿ Jÿ Bÿ Nÿ Sÿ Aÿ Gÿ Iÿ Bÿ Pÿ Qÿ Tÿ Pÿ Hÿ B
ÿÿ4ÿ Hÿ Gÿ Gÿ Lÿ Tÿ Kÿ Cÿ Rÿ Hÿ Kÿ Tÿ Hÿ Iÿ Pÿ Dÿ Aÿ Iÿ Hÿ Cÿ J
ÿÿ5ÿ Dÿ Lÿ Cÿ Kÿ Jÿ Bÿ Bÿ Iÿ Tÿ Fÿ Pÿ Cÿ Mÿ Qÿ Qÿ Cÿ Dÿ Sÿ Bÿ C
ÿÿ6ÿ Pÿ Nÿ Rÿ Eÿ Lÿ Sÿ Rÿ Iÿ Pÿ Qÿ Pÿ Aÿ Oÿ Rÿ Iÿ Lÿ Fÿ Eÿ Nÿ Q
ÿÿ7ÿ Oÿ Bÿ Kÿ Kÿ Hÿ Sÿ Oÿ Sÿ Kÿ Bÿ Cÿ Hÿ Eÿ Qÿ Pÿ Mÿ Gÿ Jÿ Qÿ A
ÿÿ8ÿ Gÿ Aÿ Eÿ Lÿ Hÿ Jÿ Fÿ Nÿ Lÿ Nÿ Oÿ Sÿ Gÿ Nÿ Kÿ Rÿ Mÿ Sÿ Eÿ A
ÿÿ9ÿ Jÿ Rÿ Pÿ Lÿ Dÿ Dÿ Cÿ Qÿ Tÿ Lÿ Jÿ Aÿ Sÿ Dÿ Tÿ Bÿ Jÿ Dÿ Pÿ O
10ÿ Oÿ Lÿ Nÿ Eÿ Tÿ Fÿ Eÿ Iÿ Fÿ Oÿ Cÿ Gÿ Fÿ Mÿ Mÿ Oÿ Kÿ Sÿ Tÿ M

20 boxes horizontally, each holding 10 cookies numbered 1 to 10.

So, with full knowledge of the contents, I have to choose exactly one
of the cookies numbered 1 to 10 from each box, so that I end up with
20 cookies, all different, so one of each of the 20 sorts.

And this is guaranteed to be possible? I guess it's a bit harder than
it seemed then.

This is only ever swapping out cookies that come from the same jar.

Which means that a solution is not always possible - there is no jar
that contains one of the duplicated flavours and one of the missing flavours.

The OP said it's always possible. You'd need one counter-example to
prove that it isn't.

eg, when it works:

ÿÿÿ 0ÿ 1ÿ 2ÿ 3ÿ 4ÿ 5ÿ 6ÿ 7ÿ 8ÿ 9ÿ 10 11 12 13 14 15 16 17 18 19
0 : Tÿ Tÿ Bÿ Qÿ Lÿ Aÿ Oÿ Rÿ Qÿ Mÿ Sÿ Bÿ Bÿ Eÿ Mÿ Pÿ Eÿ Jÿ Cÿ L
1 : Iÿ Dÿ Bÿ Oÿ Eÿ Lÿ Iÿ Nÿ Sÿ Tÿ Hÿ Fÿ Dÿ Iÿ Oÿ Aÿ Fÿ Kÿ Dÿ H
2 : Rÿ Oÿ Fÿ Pÿ Qÿ Lÿ Jÿ Dÿ Kÿ Oÿ Aÿ Dÿ Lÿ Lÿ Nÿ Nÿ Iÿ Lÿ Iÿ G
3 : Hÿ Rÿ Jÿ Kÿ Kÿ Cÿ Tÿ Bÿ Tÿ Fÿ Qÿ Tÿ Hÿ Sÿ Jÿ Cÿ Fÿ Sÿ Iÿ F
4 : Kÿ Pÿ Pÿ Aÿ Iÿ Eÿ Fÿ Sÿ Lÿ Bÿ Gÿ Cÿ Gÿ Qÿ Pÿ Pÿ Aÿ Fÿ Rÿ S
5 : Gÿ Hÿ Cÿ Cÿ Hÿ Cÿ Aÿ Nÿ Nÿ Mÿ Oÿ Gÿ Fÿ Oÿ Cÿ Gÿ Eÿ Fÿ Hÿ K
6 : Mÿ Kÿ Qÿ Nÿ Eÿ Jÿ Gÿ Eÿ Bÿ Qÿ Jÿ Oÿ Aÿ Nÿ Iÿ Aÿ Gÿ Eÿ Mÿ R
7 : Dÿ Dÿ Rÿ Jÿ Mÿ Nÿ Sÿ Hÿ Nÿ Pÿ Nÿ Tÿ Rÿ Dÿ Aÿ Gÿ Cÿ Gÿ Eÿ H
8 : Qÿ Lÿ Rÿ Pÿ Aÿ Pÿ Rÿ Tÿ Mÿ Jÿ Oÿ Tÿ Sÿ Rÿ Qÿ Dÿ Mÿ Pÿ Jÿ K
9 : Oÿ Kÿ Qÿ Iÿ Cÿ Iÿ Bÿ Sÿ Bÿ Kÿ Eÿ Sÿ Dÿ Mÿ Lÿ Bÿ Jÿ Mÿ Hÿ T

Choosing one cookie from each jar ...
choosen:ÿÿÿ T T B Q L A O R Q M S B B E M P E J C L

Swapping B for F in jar 2

Why choose B and F in jar 2 first? Those two T's at the beginning of the selection look like a more pressing case, as we only want one of each kind.

Swapping B for D in jar 11
Swapping E for I in jar 13
Swapping L for H in jar 4
Swapping M for K in jar 9
Swapping Q for N in jar 3
Swapping T for G in jar 0
Solved!

choosen:ÿÿÿ G T F N H A O R Q K S D B I M P E J C L

When it doesn't work, then you'd have start swapping cookies between different jars.ÿ I guess that is the hard part.

That's not allowed. You can notionally mix up the cookies in the same
jar, as the order is not relevant, but not exchange between jars.

The only thing you can do, AIUI, is put back a cookie into its original
jar, and choose another.






--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 4/1/2026 9:34 AM, Michael S wrote:

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution exists.

//public domain code
//this 'brute force' algorithm tries to choose 20 unique types of
cookies from 20 boxes of 10 cookies each
//almost always get 18 19 or 20

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

//print contents of box - by row then column
void print_row_by_col(int box[]) {
int b = 1;
for (int i = 0; i < 200; i += 10) {
for (int j = 0; j < 10; j++) {
printf("%2d %c\n",b, box[i+j] +65);
}
b++;
}
}

//print contents of box column by row
void print_col_by_row(int box[], char *hdr) {

printf(" Boxes (%s)\n",hdr);
printf("Cookie --------------------------------------------------------------------------------------------------\n");
printf(" Nbr ");
for (int i = 1; i <= 9; i++) {printf("%d ", i);}
for (int i = 10; i <= 20; i++) {printf("%d ", i);}
printf("\n----------------------------------------------------------------------------------------------------------\n");
int rows = 10, cols = 20, colwidth = 5;
for (int r = 1; r <= rows; r++) {
if (r <= 200) {
int nbr = r-1;
printf("%3d %-*c", r, colwidth, box[nbr] + 65);
for (int i = 0; i < cols-1; i++) {
nbr += rows;
if (nbr <= 200) {
printf("%-*c", colwidth, box[nbr] + 65);
}
}
printf("\n");
}
}
printf("----------------------------------------------------------------------------------------------------------\n\n");
}

//sort box by section then cookie type (not used)
//for (int i = 0; i < 200; i += 10) {
// qsort(box + i, 10, sizeof(box[0]), compare2ints);
//}
int compare2ints(const void *a, const void *b) {
const int *intA = (const int *)a;
const int *intB = (const int *)b;
if (intA[0] != intB[0]) {
return intA[0] - intB[0];
}
return intA[1] - intB[1];
}


int main(void) {

//----------------------------------------------------------------------------
//fill a box of 20 sections with 10 cookies each, from 20 random
//cookie flavors - duplicate flavors allowed in each section
//----------------------------------------------------------------------------

//big beautiful box
int *box = malloc(200 * sizeof(int));

//assign -33 to show blanks later
for (int i = 0; i < 200; i++) {box[i] = -33;} //to show blank later

//ensure all types are used at least once
//assign one of each cookie type to a unique random box, and to a
//random position within the box
srand(time(NULL));
char usedlist[75] = {0};
char therandom[5];
int j = 0;
for (int i = 0; i < 200; i ++) {
int r = rand() % 20; //random box
sprintf(therandom," %d ", r);
if (strstr(usedlist, therandom) == NULL) {
if (j < 20) {
int s = rand() % 10; //random position in the box
box[(r * 10) + s] = j++;
strncat(usedlist, therandom, strlen(therandom));
}
if (j == 20) {break;}
}
}

//print contents of box column by row
//note: at this point in the code this will blanks and one cookie type per box
print_col_by_row(box,"random successful path");


//randomly fill in the remaining 9 cookie types in each section
for (int i = 0; i < 200; i += 10) {
for (int j = 0; j < 10; j++) {
int r = rand() % 20;
if (box[i+j] == -33) {
box[i+j] = r;
}
}
}

//print contents of filled box - column by row
print_col_by_row(box,"random fill");

//search algorithm
char usedcookies[600] = {0};
char usedboxes[62] = {0};
char solution[62] = {0};
int *usedboxesarr = malloc(20 * sizeof(int));
int *solutionarr = malloc(10 * sizeof(int));
char thecookie[4], thebox[4];
int matches = 0;

clock_t starttime, endtime;
starttime = clock(); //CPU timing
for (int j = 0; j < 10; j++) {

matches = 0;
sprintf(thecookie, " %c ", box[j] + 65);
sprintf(thebox , " %d ", (j/10) + 1);
strcat(usedcookies, thecookie);
strcat(solution, thecookie);
strcat(usedboxes, thebox);
solutionarr[matches] = box[j];
usedboxesarr[matches] = (j/10) + 1;
matches++;

for (int i = 10; i < 200; i++) {
sprintf(thecookie, " %c ", box[i] + 65);
sprintf(thebox , " %d ", (i/10) + 1);
if (strstr(usedcookies, thecookie) == NULL && strstr(usedboxes,
thebox) == NULL) {
strcat(usedcookies, thecookie);
strcat(solution, thecookie);
strcat(usedboxes, thebox);
solutionarr[matches] = box[i];
usedboxesarr[matches] = (i/10) + 1;
matches++;
}
}

if (matches == 20) {break;}
memset(usedcookies, 0, sizeof(usedcookies));
memset(usedboxes, 0, sizeof(usedboxes));
memset(solution, 0, sizeof(solution));
memset(solutionarr, 0, sizeof(solutionarr));
memset(usedboxesarr, 0, sizeof(usedboxesarr));

}
endtime = clock();

//# of choices (20 = success = a different type from 20 boxes)
printf("Matches: %d\n", matches);

//print boxes used
printf("Box :");
for (int i = 0; i < matches; i++) {printf("%3d ",usedboxesarr[i]);}

//print cookie types used
printf("\nType:");
for (int i = 0; i < matches; i++) {printf("%3c ",solutionarr[i] + 65);}
printf("\nCPU time = %.5fs\n\n",((double)(endtime - starttime)) / CLOCKS_PER_SEC);


free(box);
return 0;
}



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Sat, 4 Apr 2026 13:33:44 -0400
DFS <nospam@dfs.com> wrote:

At first, you didn't understand the rules. That's o.k.
Bart is pretty smart, but he didn't understand too.
Let's call it my fault.

But then 3 different people explained it to you. Despite that you still
didn't get it.
It's no longer my fault.





--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 4/4/2026 2:03 PM, Michael S wrote:

On Sat, 4 Apr 2026 13:33:44 -0400
DFS <nospam@dfs.com> wrote:

At first, you didn't understand the rules. That's o.k.
Bart is pretty smart, but he didn't understand too.
Let's call it my fault.

> But then 3 different people explained it to you. Despite that you still

didn't get it.
It's no longer my fault.

I got it right after Mike Terry explained it.

It's a hard CS challenge, and I just don't know how to "implement
function solver() in module solver.c"

But my brute force algorithm does get 20 matches about 1/4th of the
time, in as little as .00002s.

Only 20picks/20types 100% of the time is a success, so I'll keep working
at it.

If you run my code you might like what it does.


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 04/04/2026 19:03, Michael S wrote:

On Sat, 4 Apr 2026 13:33:44 -0400
DFS <nospam@dfs.com> wrote:

At first, you didn't understand the rules. That's o.k.
Bart is pretty smart, but he didn't understand too.
Let's call it my fault.

Advent of Code challenges are very well explained.

They also provide a small-scale example, showing inputs, and expected
outputs.

I don't know how the difficulty of this compares with those; I've never
had enough patience to get past the first couple of days, and they
apparently got harder.

(I might yet get back to it, but I'm not working on it now. Even with
the O(N*N*M) hint you posted, which tells me all the approaches I can
think of are probably wrong.)




--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Sat, 4 Apr 2026 20:22:19 +0100
Bart <bc@freeuk.com> wrote:

On 04/04/2026 19:03, Michael S wrote:

On Sat, 4 Apr 2026 13:33:44 -0400
DFS <nospam@dfs.com> wrote:

At first, you didn't understand the rules. That's o.k.
Bart is pretty smart, but he didn't understand too.
Let's call it my fault.

Advent of Code challenges are very well explained.

They also provide a small-scale example, showing inputs, and expected outputs.

I don't know how the difficulty of this compares with those; I've
never had enough patience to get past the first couple of days, and
they apparently got harder.

I don't follow code challenges systematically.
I remember one posted here few years ago named Euler413.
I think that my challenge is simpler than that, but not a lot simpler.

(I might yet get back to it, but I'm not working on it now. Even with
the O(N*N*M) hint you posted, which tells me all the approaches I can
think of are probably wrong.)

I suppose that you tried heuristic based schemes. I can not tell that
they are necessarily wrong. Personally, I was not able to find working heuristics, but it does not mean that one do not exists.





--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Michael S <already5chosen@yahoo.com> writes:

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench that
I prepared is in C. [...]

Thank you for that.

So, here is the challenge:

I looked at the problem, and have written enough code now to
satisfy myself that I know how to solve it. Not ready to
post yet; among other things there are some other clc
posts I've been meaning to respond to, and I really should
try to do those first. I plan on not looking at anyone else's
code before I have something ready to say myself.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On 02/04/2026 20:10, Michael S wrote:

I'l look at your solution not before it is implemented according to
my spec: as a module solver.c that implements function solver() as
declared in solver.h and linkable with tb.c.

Isn't it called a translation unit, rather than a module?

Do we say "declared" for functions in C? I thought it was called
"prototyped."


--
Tristan Wibberley

The message body is Copyright (C) 2026 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk>
writes:

On 02/04/2026 20:10, Michael S wrote:

I'l look at your solution not before it is implemented according to
my spec: as a module solver.c that implements function solver() as
declared in solver.h and linkable with tb.c.

Isn't it called a translation unit, rather than a module?

Right.

Do we say "declared" for functions in C? I thought it was called "prototyped."

In C, a function can be declared (or even defined) without having
a prototype. I think that might change (IMO a change for the
worse) in C23, but before C23 a function declaration doesn't
have to include a prototype.

Personally I am not inclined to use "prototyped" as a verb in that
way. The C standard talks about "a type that includes a prototype"
or "a type that does not include a prototype", and normally I think
I would use that phrasing, or a similar one. Note that prototypes
can appear without necessarily being associated with any function,
as for example in a typedef or a cast.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk>
writes:

On 02/04/2026 20:10, Michael S wrote:

I'l look at your solution not before it is implemented according to
my spec: as a module solver.c that implements function solver() as
declared in solver.h and linkable with tb.c.

Isn't it called a translation unit, rather than a module?

Yes. The C standard doesn't define anything called "modules".
A translation unit consists of a source file and all the headers
and source files it #includes.

There's nothing necessarily wrong with referring to "modules" as a
way to talk about program organization, but it's helpful to define
what you mean by the term.

Do we say "declared" for functions in C? I thought it was called "prototyped."

Functions can be declared and/or defined. A definition provides a
declaration. A prototype is a declaration that specifies the types
of any parameters; the alternative is an old-style declaration.
Old-style function declarations and definitions are no longer
supported in C23.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Michael S <already5chosen@yahoo.com> writes:

[...]

Here I am again, ready now to write a more substantive response.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution exists.
I don't ask you to repeat the proof. Just peek cookies!

I think the problem is interesting. I thought I would try coding
something up.

It's obvious that one can find the solution by exhausting. Don't do
it. Indeed, the number of possible peek orders is finite, but ii is
large - 2.4e18.
Be smarter.
On modern PC I want to get a solution in less than 1 msec, bonus for
less than 50usec.

[.. C code to drive an exercise a proposed solution ..]

You have to implement function solver() in module solver.c

I ran into trouble when I tried to work within the posted framework
to drive a solver. The difficulties were of several kinds. The
code didn't compile in my standard compilation environment, which
is roughly this (the c99 might be c11 but that made no difference):

gcc -x c -std=c99 -pedantic ...

I was able to work through that problem but it was irksome. The
second difficulty is the interface to solver() seems rather clunky
to me, maybe not for the input but for the output, and it wasn't
clear to me what the specification is for the output (I did manage
to figure this out but only much later). I was having to put more
effort into figuring out the interface than solving the problem.

Finally I abandoned the idea of working within the structure of the
posted driver code and wrote a solver to my own specification.
Doing that was fairly straightforward and took half an hour or so
(disclaimer: after I had spent a good amount of time just thinking
about the problem). After writing the solver I reimplemented a
driver framework to drive it, conforming to the interface I was
using. Some debugging was needed to get everything working. I did
some rudimentary time measurements for the solver. Results were
good (more about the specifics later).

After doing the new solver I went back to the posted driver code,
and grafted together the new solver with the orginal driver. Some
glue code was needed to reconcile the differences in interface
between the new solver and the original driver. Then I needed to
figure out the semantics of the output, which were different than
what I expected and originally understood. I figured all that out
and got things working. Sadly the code was uglier than I would have
liked.

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.

Running the above code with default settings (128 11) produced this
output

o.k.
med=0.003542 msec, min=0.003487 msec, max=0.003911 msec

The timing results for my second code effort were similar, except
that the value for max was about 0.3 msec.

Informal timing measurements on my original solver -- in particular
using a different interface, and done simply by using 'time' in the
shell to measure a million calls to the solver -- gave per-call
times that were better by about a factor of five. I need to be
clear that this solver does not conform to the original interface,
and probably most of speedup is due to choosing an interface that
gives an easier fit to the solver.

Sorry not to have something better for you. It was a fair amount of
work to produce the results above.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Wed, 08 Apr 2026 08:42:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

[...]

Here I am again, ready now to write a more substantive response.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution exists.
I don't ask you to repeat the proof. Just peek cookies!

I think the problem is interesting. I thought I would try coding
something up.

It's obvious that one can find the solution by exhausting. Don't do
it. Indeed, the number of possible peek orders is finite, but ii is
large - 2.4e18.
Be smarter.
On modern PC I want to get a solution in less than 1 msec, bonus for
less than 50usec.

[.. C code to drive an exercise a proposed solution ..]

You have to implement function solver() in module solver.c

I ran into trouble when I tried to work within the posted framework
to drive a solver. The difficulties were of several kinds. The
code didn't compile in my standard compilation environment, which
is roughly this (the c99 might be c11 but that made no difference):

gcc -x c -std=c99 -pedantic ...

What were the problems?
My gcc 14.2.0 on msys2 produces no warnings or errors with above flags.

I was able to work through that problem but it was irksome. The
second difficulty is the interface to solver() seems rather clunky
to me, maybe not for the input but for the output, and it wasn't
clear to me what the specification is for the output (I did manage
to figure this out but only much later). I was having to put more
effort into figuring out the interface than solving the problem.

Yes, I should have explained it, at least briefly.
I'd guess that you expected that values in result vector correspond to
sorts of cookies, when in fact they are indices to position of the
cookie in the box.
I am sorry.

Finally I abandoned the idea of working within the structure of the
posted driver code and wrote a solver to my own specification.
Doing that was fairly straightforward and took half an hour or so (disclaimer: after I had spent a good amount of time just thinking
about the problem). After writing the solver I reimplemented a
driver framework to drive it, conforming to the interface I was
using. Some debugging was needed to get everything working. I did
some rudimentary time measurements for the solver. Results were
good (more about the specifics later).

After doing the new solver I went back to the posted driver code,
and grafted together the new solver with the orginal driver. Some
glue code was needed to reconcile the differences in interface
between the new solver and the original driver. Then I needed to
figure out the semantics of the output, which were different than
what I expected and originally understood. I figured all that out
and got things working. Sadly the code was uglier than I would have
liked.

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.

Running the above code with default settings (128 11) produced this
output

o.k.
med=0.003542 msec, min=0.003487 msec, max=0.003911 msec

The timing results for my second code effort were similar, except
that the value for max was about 0.3 msec.

My defaults were chosen for much slower solutions.
For fast solutions like yours or mine with default parameters an
overhead of clock_gettime() call is too significant.
In such case it's better to use rep1 of at least 10000.

Informal timing measurements on my original solver -- in particular
using a different interface, and done simply by using 'time' in the
shell to measure a million calls to the solver -- gave per-call
times that were better by about a factor of five. I need to be
clear that this solver does not conform to the original interface,
and probably most of speedup is due to choosing an interface that
gives an easier fit to the solver.

It's not something I'd expect.
I used "by value" type of interface both for input and for output in
order to reduce a chance of buggy solutions to mess with the test bench.
I fully expect that "by reference" type of interface could be somewhat
faster. May be, 1.5x faster for very fast solutions. But I certainly
don't expect a factor of five.

Sorry not to have something better for you. It was a fair amount of
work to produce the results above.

I read your code briefly, but didn't try to understand it yet.
I plugged it into my test bench and measured speed on very old home PC
(Intel i5-3450). With big values of rep1 it was ~3.3 times faster
than my original solution and ~1.9 times slower than my 2nd solution.
So, speed-wise your solution is good.
One thing that I don't particularly like after taking a glance - it
does not appear to be thread-safe. But it is probably very easy to make
it thread safe.
Another thing that I don't particularly like - if we want N_BOXES > 32
then it requires modifications; if we want N_BOXES > 64 then it
requires more serious modifications.

Now few words about my own solutions.
1. Original solution:
This solution is based on the proof that was given to me by somebody
with abstract math mind.
2. It is solution that I found independently, for which I hopefully
have a proof in the head, but I didn't write it out yet and didn't show
yet to said mathematician. It would not surprise me if idea of these
solution is the same as yours.

Later today (tonight) I plan to post both solutions here.




--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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];
}




--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Wed, 1 Apr 2026 16:34:47 +0300
Michael S <already5chosen@yahoo.com> wrote:

<snip>

My solution #2.
That is my own, with no proof preceding code. It went in other direction
- from hacking the code to proving it later.
It is pretty fast. Can be made faster yet by replication of some code
and re-arrangement in the find() routine, but for purposes of
illustration I wanted it short.


#include <stdint.h>
#include <string.h>
#include <stdbool.h>

#include "solver.h"

static
uint8_t solver_find(
const uint8_t b_idx[N_BOXES][N_BOXES],
uint8_t result[N_BOXES],
const uint8_t free[N_BOXES],
int n_free,
uint8_t v,
const uint8_t bx[N_BOXES][BOX_SIZE])
{
typedef struct {
uint8_t parent, bi;
} db_rec;
db_rec db[N_BOXES];
bool valid[N_BOXES] = {0};
uint8_t que[N_BOXES], *wr = que, *rd = que;

valid[v] = true;
*wr++ = v;
for (;;) {
uint8_t vv = *rd++;
for (int i = 0; i < n_free; ++i) {
uint8_t bi = free[i];
uint8_t ci = b_idx[bi][vv];
if (ci != BOX_SIZE) {
result[bi] = ci;
while (vv != v) {
bi = db[vv].bi;
vv = db[vv].parent;
result[bi] = b_idx[bi][vv];
};
return i;
}
}
// add neighbors to database
for (int bi = 0; bi < N_BOXES; ++bi) {
if (b_idx[bi][vv] != BOX_SIZE) {
uint8_t a = bx[bi][result[bi]];
if (!valid[a]) {
valid[a] = true;
db[a] = (db_rec){ .parent = vv, .bi = bi };
*wr++ = a;
}
}
}
}
}

peek_t solver(boxes_t boxes)
{
// build index
uint8_t b_idx[N_BOXES][N_BOXES];
memset(b_idx, BOX_SIZE, sizeof(b_idx));
for (int bi = 0; bi < N_BOXES; ++bi) {
for (int ci = 0; ci < BOX_SIZE; ++ci) {
uint8_t v = boxes.b[bi][ci];
if (b_idx[bi][v] == BOX_SIZE)
b_idx[bi][v] = ci;
}
}

uint8_t free_boxes[N_BOXES];
for (int bi = 0; bi < N_BOXES; ++bi)
free_boxes[bi] = bi;
int n_free = N_BOXES;

peek_t result = {0};
bool used_sorts[N_BOXES]={0};
while (n_free > 0) {
int bi = free_boxes[--n_free]; // new set
result.b[bi] = 0;
uint8_t v = boxes.b[bi][0];
used_sorts[v] = true;
uint8_t pend_que[N_BOXES],
*pend_wr = pend_que, *pend_rd = pend_que;
*pend_wr++ = bi;
while (pend_wr != pend_rd && n_free != 0) {
int bk = *pend_rd++;
for (int ci = 0; ci < BOX_SIZE; ++ci) {
v = boxes.b[bk][ci];
if (!used_sorts[v]) {
// new value in set
uint8_t v_fi = solver_find(
b_idx, result.b, free_boxes,
n_free, v, boxes.b);
uint8_t v_bi = free_boxes[v_fi];
used_sorts[v] = true;
*pend_wr++ = v_bi;
free_boxes[v_fi] = free_boxes[--n_free];
// remove from free list
}
}
}
}
return result;
}



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Michael S <already5chosen@yahoo.com> writes:

On Wed, 1 Apr 2026 16:34:47 +0300
Michael S <already5chosen@yahoo.com> wrote:

<snip>

My solution #2.
That is my own, with no proof preceding code. It went in other direction
- from hacking the code to proving it later.
It is pretty fast. Can be made faster yet by replication of some code
and re-arrangement in the find() routine, but for purposes of
illustration I wanted it short.

Just fyi.. I did some speed comparisons between the code below and
the compatible solver that I wrote. Your code is faster, scales
better, and also has better worst-case behavior (which is to say
that my code has worse worst-case behavior). So I think the timing
numbers I was seeing before may have been just the result of being
lucky in the draw of random numbers.

#include <stdint.h>
#include <string.h>
#include <stdbool.h>

#include "solver.h"

static
uint8_t solver_find(
const uint8_t b_idx[N_BOXES][N_BOXES],
uint8_t result[N_BOXES],
const uint8_t free[N_BOXES],
int n_free,
uint8_t v,
const uint8_t bx[N_BOXES][BOX_SIZE])
{
typedef struct {
uint8_t parent, bi;
} db_rec;
db_rec db[N_BOXES];
bool valid[N_BOXES] = {0};
uint8_t que[N_BOXES], *wr = que, *rd = que;

valid[v] = true;
*wr++ = v;
for (;;) {
uint8_t vv = *rd++;
for (int i = 0; i < n_free; ++i) {
uint8_t bi = free[i];
uint8_t ci = b_idx[bi][vv];
if (ci != BOX_SIZE) {
result[bi] = ci;
while (vv != v) {
bi = db[vv].bi;
vv = db[vv].parent;
result[bi] = b_idx[bi][vv];
};
return i;
}
}
// add neighbors to database
for (int bi = 0; bi < N_BOXES; ++bi) {
if (b_idx[bi][vv] != BOX_SIZE) {
uint8_t a = bx[bi][result[bi]];
if (!valid[a]) {
valid[a] = true;
db[a] = (db_rec){ .parent = vv, .bi = bi };
*wr++ = a;
}
}
}
}
}

peek_t solver(boxes_t boxes)
{
// build index
uint8_t b_idx[N_BOXES][N_BOXES];
memset(b_idx, BOX_SIZE, sizeof(b_idx));
for (int bi = 0; bi < N_BOXES; ++bi) {
for (int ci = 0; ci < BOX_SIZE; ++ci) {
uint8_t v = boxes.b[bi][ci];
if (b_idx[bi][v] == BOX_SIZE)
b_idx[bi][v] = ci;
}
}

uint8_t free_boxes[N_BOXES];
for (int bi = 0; bi < N_BOXES; ++bi)
free_boxes[bi] = bi;
int n_free = N_BOXES;

peek_t result = {0};
bool used_sorts[N_BOXES]={0};
while (n_free > 0) {
int bi = free_boxes[--n_free]; // new set
result.b[bi] = 0;
uint8_t v = boxes.b[bi][0];
used_sorts[v] = true;
uint8_t pend_que[N_BOXES],
*pend_wr = pend_que, *pend_rd = pend_que;
*pend_wr++ = bi;
while (pend_wr != pend_rd && n_free != 0) {
int bk = *pend_rd++;
for (int ci = 0; ci < BOX_SIZE; ++ci) {
v = boxes.b[bk][ci];
if (!used_sorts[v]) {
// new value in set
uint8_t v_fi = solver_find(
b_idx, result.b, free_boxes,
n_free, v, boxes.b);
uint8_t v_bi = free_boxes[v_fi];
used_sorts[v] = true;
*pend_wr++ = v_bi;
free_boxes[v_fi] = free_boxes[--n_free];
// remove from free list
}
}
}
}
return result;
}

I think I could eventually understand what this code is doing, and
after that get a sense of how and why it works. In its current
form I think that would take me a fair amount of time. It would
help to have a roadmap, more evocative names, more functional
decomposition, or ideally all three. Please understand, I'm not
asking or suggesting you do anything; my intention is only to
provide feedback that may be of some benefit to you.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Michael S <already5chosen@yahoo.com> writes:

On Wed, 08 Apr 2026 08:42:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

[...]

Here I am again, ready now to write a more substantive response.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in
20 boxes, again, 10 cookies in each boxes. You have to take exactly
one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution exists.
I don't ask you to repeat the proof. Just peek cookies!

I think the problem is interesting. I thought I would try coding
something up.

It's obvious that one can find the solution by exhausting. Don't do
it. Indeed, the number of possible peek orders is finite, but ii is
large - 2.4e18.
Be smarter.
On modern PC I want to get a solution in less than 1 msec, bonus for
less than 50usec.

[.. C code to drive an exercise a proposed solution ..]

You have to implement function solver() in module solver.c

I ran into trouble when I tried to work within the posted framework
to drive a solver. The difficulties were of several kinds. The
code didn't compile in my standard compilation environment, which
is roughly this (the c99 might be c11 but that made no difference):

gcc -x c -std=c99 -pedantic ...

What were the problems?
My gcc 14.2.0 on msys2 produces no warnings or errors with above flags.

These source lines

struct timespec t0;
clock_gettime(CLOCK_MONOTONIC, &t0);

produced these diagnostics

tb.c:134:21: error: storage size of 't0' isn't known
tb.c:135:5: warning: implicit declaration of function 'clock_gettime' [...]
tb.c:135:19: error: 'CLOCK_MONOTONIC' undeclared (first use in this function)

under -std=c99. Apparently the first diagnostic, about
struct timespec, is fixed under -std=c11. It wasn't hard
to fix these, but it was irksome.

I was able to work through that problem but it was irksome. The
second difficulty is the interface to solver() seems rather clunky
to me, maybe not for the input but for the output, and it wasn't
clear to me what the specification is for the output (I did manage
to figure this out but only much later). I was having to put more
effort into figuring out the interface than solving the problem.

Yes, I should have explained it, at least briefly.
I'd guess that you expected that values in result vector correspond to
sorts of cookies, when in fact they are indices to position of the
cookie in the box.
I am sorry.

Yes, that is in fact what I was thinking. Fortunately the difficulty
was resolved when the checker reported a value out of range.

Finally I abandoned the idea of working within the structure of the
posted driver code and wrote a solver to my own specification.
Doing that was fairly straightforward and took half an hour or so
(disclaimer: after I had spent a good amount of time just thinking
about the problem). After writing the solver I reimplemented a
driver framework to drive it, conforming to the interface I was
using. Some debugging was needed to get everything working. I did
some rudimentary time measurements for the solver. Results were
good (more about the specifics later).

After doing the new solver I went back to the posted driver code,
and grafted together the new solver with the orginal driver. Some
glue code was needed to reconcile the differences in interface
between the new solver and the original driver. Then I needed to
figure out the semantics of the output, which were different than
what I expected and originally understood. I figured all that out
and got things working. Sadly the code was uglier than I would have
liked.

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.

Running the above code with default settings (128 11) produced this
output

o.k.
med=0.003542 msec, min=0.003487 msec, max=0.003911 msec

The timing results for my second code effort were similar, except
that the value for max was about 0.3 msec.

My defaults were chosen for much slower solutions.
For fast solutions like yours or mine with default parameters an
overhead of clock_gettime() call is too significant.
In such case it's better to use rep1 of at least 10000.

It turns out that running with a larger number of trials didn't
change the results much. I think my averages got a bit worse and my
worst case got a bit better, but as I recall the difference wasn't
anything dramatic.

Informal timing measurements on my original solver -- in particular
using a different interface, and done simply by using 'time' in the
shell to measure a million calls to the solver -- gave per-call
times that were better by about a factor of five. I need to be
clear that this solver does not conform to the original interface,
and probably most of speedup is due to choosing an interface that
gives an easier fit to the solver.

It's not something I'd expect.
I used "by value" type of interface both for input and for output in
order to reduce a chance of buggy solutions to mess with the test bench.
I fully expect that "by reference" type of interface could be somewhat faster. May be, 1.5x faster for very fast solutions. But I certainly
don't expect a factor of five.

I will try to explain below.

Sorry not to have something better for you. It was a fair amount of
work to produce the results above.

I read your code briefly, but didn't try to understand it yet.

I need to say again that the code I posted was not code that I wrote.
The approach used is similar to code I did write, but the actual code
is quite a bit different.

I plugged it into my test bench and measured speed on very old home PC
(Intel i5-3450). With big values of rep1 it was ~3.3 times faster
than my original solution and ~1.9 times slower than my 2nd solution.
So, speed-wise your solution is good.
One thing that I don't particularly like after taking a glance - it
does not appear to be thread-safe. But it is probably very easy to make
it thread safe.

Do you mean because it is using (and changing) global objects? Yes
that is a drawback.

Another thing that I don't particularly like - if we want N_BOXES > 32
then it requires modifications; if we want N_BOXES > 64 then it
requires more serious modifications.

As it turns out my code handles N_BOXES up to 52. You may laugh
when you see why.

Now few words about my own solutions.
1. Original solution:
This solution is based on the proof that was given to me by somebody
with abstract math mind.

Yes, I posted a comment about that

2. It is solution that I found independently, for which I hopefully
have a proof in the head, but I didn't write it out yet and didn't show
yet to said mathematician. It would not surprise me if idea of these solution is the same as yours.

I don't really understand that code yet, but it looks like your
code is a bit fancier than mine (the code that wasn't posted
because it uses a different interface).

Later today (tonight) I plan to post both solutions here.

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.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Thu, 09 Apr 2026 21:22:51 -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:

Michael S <already5chosen@yahoo.com> writes:

[...]

Here I am again, ready now to write a more substantive response.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed
in 20 boxes, again, 10 cookies in each boxes. You have to take
exactly one cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution
exists. I don't ask you to repeat the proof. Just peek cookies!

I think the problem is interesting. I thought I would try coding
something up.

It's obvious that one can find the solution by exhausting. Don't
do it. Indeed, the number of possible peek orders is finite, but
ii is large - 2.4e18.
Be smarter.
On modern PC I want to get a solution in less than 1 msec, bonus
for less than 50usec.

[.. C code to drive an exercise a proposed solution ..]

You have to implement function solver() in module solver.c

I ran into trouble when I tried to work within the posted framework
to drive a solver. The difficulties were of several kinds. The
code didn't compile in my standard compilation environment, which
is roughly this (the c99 might be c11 but that made no difference):

gcc -x c -std=c99 -pedantic ...

What were the problems?
My gcc 14.2.0 on msys2 produces no warnings or errors with above
flags.

These source lines

struct timespec t0;
clock_gettime(CLOCK_MONOTONIC, &t0);

produced these diagnostics

tb.c:134:21: error: storage size of 't0' isn't known
tb.c:135:5: warning: implicit declaration of function
'clock_gettime' [...] tb.c:135:19: error: 'CLOCK_MONOTONIC'
undeclared (first use in this function)

under -std=c99. Apparently the first diagnostic, about
struct timespec, is fixed under -std=c11. It wasn't hard
to fix these, but it was irksome.

Sounds like under Linux and with -std=c99 flag function clock_gettime()
and related structures and constants are not declared/defined by default
in time.h.
Man page suggests magic pixie dust:

#define _XOPEN_SOURCE 600
#include <time.h>
#include <unistd.h>


If you ask why I used clock_gettime() instead of C standard
timespec_get() then the answer is that on Windows, eps. on older
versions like Win7 and WS2008 (which I prefer over newer stuff for
reasons unrelated to quality of C RTL), precision of timespec_get() is
poor. clock_gettime(CLOCK_MONOTONIC,) is much better.

I was able to work through that problem but it was irksome. The
second difficulty is the interface to solver() seems rather clunky
to me, maybe not for the input but for the output, and it wasn't
clear to me what the specification is for the output (I did manage
to figure this out but only much later). I was having to put more
effort into figuring out the interface than solving the problem.

Yes, I should have explained it, at least briefly.
I'd guess that you expected that values in result vector correspond
to sorts of cookies, when in fact they are indices to position of
the cookie in the box.
I am sorry.

Yes, that is in fact what I was thinking. Fortunately the difficulty
was resolved when the checker reported a value out of range.

Finally I abandoned the idea of working within the structure of the
posted driver code and wrote a solver to my own specification.
Doing that was fairly straightforward and took half an hour or so
(disclaimer: after I had spent a good amount of time just thinking
about the problem). After writing the solver I reimplemented a
driver framework to drive it, conforming to the interface I was
using. Some debugging was needed to get everything working. I did
some rudimentary time measurements for the solver. Results were
good (more about the specifics later).

After doing the new solver I went back to the posted driver code,
and grafted together the new solver with the orginal driver. Some
glue code was needed to reconcile the differences in interface
between the new solver and the original driver. Then I needed to
figure out the semantics of the output, which were different than
what I expected and originally understood. I figured all that out
and got things working. Sadly the code was uglier than I would
have liked.

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.

Running the above code with default settings (128 11) produced this
output

o.k.
med=0.003542 msec, min=0.003487 msec, max=0.003911 msec

The timing results for my second code effort were similar, except
that the value for max was about 0.3 msec.

My defaults were chosen for much slower solutions.
For fast solutions like yours or mine with default parameters an
overhead of clock_gettime() call is too significant.
In such case it's better to use rep1 of at least 10000.

It turns out that running with a larger number of trials didn't
change the results much. I think my averages got a bit worse and my
worst case got a bit better, but as I recall the difference wasn't
anything dramatic.

After testing on another (Windows) systems I have to admit that my
objections about default value of rep1 applies only to Win7. Even on
Ws2008, which is almost the same kernel, overhead of clock_gettime() is sufficiently low for rep1=128 to give fair measurements.

Informal timing measurements on my original solver -- in particular
using a different interface, and done simply by using 'time' in the
shell to measure a million calls to the solver -- gave per-call
times that were better by about a factor of five. I need to be
clear that this solver does not conform to the original interface,
and probably most of speedup is due to choosing an interface that
gives an easier fit to the solver.

It's not something I'd expect.
I used "by value" type of interface both for input and for output in
order to reduce a chance of buggy solutions to mess with the test
bench. I fully expect that "by reference" type of interface could
be somewhat faster. May be, 1.5x faster for very fast solutions.
But I certainly don't expect a factor of five.

I will try to explain below.

Sorry not to have something better for you. It was a fair amount
of work to produce the results above.

I read your code briefly, but didn't try to understand it yet.

I need to say again that the code I posted was not code that I wrote.
The approach used is similar to code I did write, but the actual code
is quite a bit different.

I plugged it into my test bench and measured speed on very old home
PC (Intel i5-3450). With big values of rep1 it was ~3.3 times
faster than my original solution and ~1.9 times slower than my 2nd solution. So, speed-wise your solution is good.
One thing that I don't particularly like after taking a glance - it
does not appear to be thread-safe. But it is probably very easy to
make it thread safe.

Do you mean because it is using (and changing) global objects? Yes
that is a drawback.

Yes.

Another thing that I don't particularly like - if we want N_BOXES >
32 then it requires modifications; if we want N_BOXES > 64 then it requires more serious modifications.

As it turns out my code handles N_BOXES up to 52. You may laugh
when you see why.

Now few words about my own solutions.
1. Original solution:
This solution is based on the proof that was given to me by somebody
with abstract math mind.

Yes, I posted a comment about that

<snip the rest, will respond later >


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Thu, 09 Apr 2026 21:22:51 -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:

Michael S <already5chosen@yahoo.com> writes:

<snip, answered in the other post>

As it turns out my code handles N_BOXES up to 52. You may laugh
when you see why.

The number of small+capital letters in English alphabet?
Probably, not.
Indeed, after reading the rest, it's not that.

Now few words about my own solutions.
1. Original solution:
This solution is based on the proof that was given to me by somebody
with abstract math mind.

Yes, I posted a comment about that

2. It is solution that I found independently, for which I hopefully
have a proof in the head, but I didn't write it out yet and didn't
show yet to said mathematician. It would not surprise me if idea
of these solution is the same as yours.

I don't really understand that code yet, but it looks like your
code is a bit fancier than mine (the code that wasn't posted
because it uses a different interface).

Later today (tonight) I plan to post both solutions here.

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.

Is it proven that this step helps?
To me it sounds unnecessary.

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.

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.



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Thu, 09 Apr 2026 16:37:30 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

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.

He was not fully sutisfied himself. 20 hours later he came with other formulation. Here is my attemp of translatioon:

1. There exist a disposition of cookies in boxes, for which it is
possible to select one cookie from each box, all of different sorts.
That is obvious. [MS: For example, each sort of cookies in its own
dedicated box. That is a disposition that I use in my code] Let's call
the selection "thread".

2. There exists an operation that changes the disposition, but
preserves the property "it is possible to select a thread" (the
description of the operation would be given separately, a.t.m. it does
not matter).

3. By means of multiple operations of that type it is possible to turn
any arbitrary disposition to any other. Since after every step the
property "it is possible to select a thread" is preserved and because
there exist a disposition, for which this property is true, it means
that the property is true for any possible disposition.

4. The operations in question - exchange of any pair of cookies.
Comment: Induction is used only in (2) for proof that an operation
preserves the desired property.

For me, the second variant was less helpful. May be, for you it would
be more helpful.

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.

Frankly, not all difficulties of following my code caused by the fact
that algorithm is derived from abstract proof.
Significant share of hurdles are rooted in my somewhat conflicting
desires to avoid all searches, except for inevitable search in the
innermost loop of the second pass, but at the same time to keep format
of the governing database (xch array+na array) minimalistic.



--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

On Thu, 09 Apr 2026 17:07:25 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

On Wed, 1 Apr 2026 16:34:47 +0300
Michael S <already5chosen@yahoo.com> wrote:

<snip>

My solution #2.
That is my own, with no proof preceding code. It went in other
direction
- from hacking the code to proving it later.
It is pretty fast. Can be made faster yet by replication of some
code and re-arrangement in the find() routine, but for purposes of illustration I wanted it short.

Just fyi.. I did some speed comparisons between the code below and
the compatible solver that I wrote. Your code is faster, scales
better, and also has better worst-case behavior (which is to say
that my code has worse worst-case behavior). So I think the timing
numbers I was seeing before may have been just the result of being
lucky in the draw of random numbers.

#include <stdint.h>
#include <string.h>
#include <stdbool.h>

#include "solver.h"

static
uint8_t solver_find(
const uint8_t b_idx[N_BOXES][N_BOXES],
uint8_t result[N_BOXES],
const uint8_t free[N_BOXES],
int n_free,
uint8_t v,
const uint8_t bx[N_BOXES][BOX_SIZE])
{
typedef struct {
uint8_t parent, bi;
} db_rec;
db_rec db[N_BOXES];
bool valid[N_BOXES] = {0};
uint8_t que[N_BOXES], *wr = que, *rd = que;

valid[v] = true;
*wr++ = v;
for (;;) {
uint8_t vv = *rd++;
for (int i = 0; i < n_free; ++i) {
uint8_t bi = free[i];
uint8_t ci = b_idx[bi][vv];
if (ci != BOX_SIZE) {
result[bi] = ci;
while (vv != v) {
bi = db[vv].bi;
vv = db[vv].parent;
result[bi] = b_idx[bi][vv];
};
return i;
}
}
// add neighbors to database
for (int bi = 0; bi < N_BOXES; ++bi) {
if (b_idx[bi][vv] != BOX_SIZE) {
uint8_t a = bx[bi][result[bi]];
if (!valid[a]) {
valid[a] = true;
db[a] = (db_rec){ .parent = vv, .bi = bi };
*wr++ = a;
}
}
}
}
}

peek_t solver(boxes_t boxes)
{
// build index
uint8_t b_idx[N_BOXES][N_BOXES];
memset(b_idx, BOX_SIZE, sizeof(b_idx));
for (int bi = 0; bi < N_BOXES; ++bi) {
for (int ci = 0; ci < BOX_SIZE; ++ci) {
uint8_t v = boxes.b[bi][ci];
if (b_idx[bi][v] == BOX_SIZE)
b_idx[bi][v] = ci;
}
}

uint8_t free_boxes[N_BOXES];
for (int bi = 0; bi < N_BOXES; ++bi)
free_boxes[bi] = bi;
int n_free = N_BOXES;

peek_t result = {0};
bool used_sorts[N_BOXES]={0};
while (n_free > 0) {
int bi = free_boxes[--n_free]; // new set
result.b[bi] = 0;
uint8_t v = boxes.b[bi][0];
used_sorts[v] = true;
uint8_t pend_que[N_BOXES],
*pend_wr = pend_que, *pend_rd = pend_que;
*pend_wr++ = bi;
while (pend_wr != pend_rd && n_free != 0) {
int bk = *pend_rd++;
for (int ci = 0; ci < BOX_SIZE; ++ci) {
v = boxes.b[bk][ci];
if (!used_sorts[v]) {
// new value in set
uint8_t v_fi = solver_find(
b_idx, result.b, free_boxes,
n_free, v, boxes.b);
uint8_t v_bi = free_boxes[v_fi];
used_sorts[v] = true;
*pend_wr++ = v_bi;
free_boxes[v_fi] = free_boxes[--n_free];
// remove from free list
}
}
}
}
return result;
}

I think I could eventually understand what this code is doing, and
after that get a sense of how and why it works. In its current
form I think that would take me a fair amount of time. It would
help to have a roadmap, more evocative names, more functional
decomposition, or ideally all three. Please understand, I'm not
asking or suggesting you do anything; my intention is only to
provide feedback that may be of some benefit to you.

I don't have a roadmap, but I have a variant of [approximately] the
same algorithm implemented in the style that is closer to your
preferences: implicit bookkeeping by recursion instead of explicit
lists and back-trace pointers. I even borrowed the name "seen" from the
code of your friend.
Hope it helps:

#include <stdint.h>
#include <string.h>
#include <stdbool.h>

#include "solver.h"

typedef struct {
uint8_t result[N_BOXES];
// result contains sorts of cookies per box
uint8_t free_boxes[N_BOXES];
int n_free;
uint8_t used_boxes[N_BOXES];
int n_used;
bool seen[N_BOXES];
uint8_t b_idx[N_BOXES][N_BOXES];
} solver_state_t;

static
bool solver_find(solver_state_t* s, uint8_t v, bool first)
{
int n_free = s->n_free;
for (int i = 0; i < n_free; ++i) {
uint8_t bi = s->free_boxes[i];
uint8_t ci = s->b_idx[bi][v];
if (ci != BOX_SIZE) {
s->result[bi] = v;
s->free_boxes[i] = s->free_boxes[--n_free];
// remove box from free list
s->n_free = n_free;
s->used_boxes[s->n_used++] = bi; // add box to used set
return true;
}
}

if (first) {
memset(s->seen, 0, sizeof(s->seen));
s->seen[v] = true;
}

int n_used = s->n_used;
for (int i = 0; i < n_used; ++i) {
int bi = s->used_boxes[i];
if (s->b_idx[bi][v] != BOX_SIZE) {
uint8_t a = s->result[bi];
if (!s->seen[a]) {
s->seen[a] = true;
if (solver_find(s, a, false)) {
s->result[bi] = v;
return true;
}
}
}
}
return false;
}

peek_t solver(boxes_t boxes)
{
solver_state_t s;
// build index
memset(s.b_idx, BOX_SIZE, sizeof(s.b_idx));
for (int bi = 0; bi < N_BOXES; ++bi) {
for (int ci = 0; ci < BOX_SIZE; ++ci) {
uint8_t v = boxes.b[bi][ci];
if (s.b_idx[bi][v] == BOX_SIZE)
s.b_idx[bi][v] = ci;
}
}

for (int bi = 0; bi < N_BOXES; ++bi)
s.free_boxes[bi] = bi;
s.n_free = N_BOXES;

bool used_sorts[N_BOXES]={0};
while (s.n_free > 0) {
int bi = s.free_boxes[--s.n_free]; // new set
uint8_t v = boxes.b[bi][0];
s.result[bi] = v;
used_sorts[v] = true;
s.used_boxes[0] = bi;
s.n_used = 1;
int rd_i = 0; // used_boxes accessed as queue
while (rd_i != s.n_used && s.n_free != 0) {
int bk = s.used_boxes[rd_i++];
for (int ci = 0; ci < BOX_SIZE; ++ci) {
v = boxes.b[bk][ci];
if (!used_sorts[v]) {
// new value in set
solver_find(&s, v, true);
used_sorts[v] = true;
}
}
}
}

// translate result from sorts to indices of selected cookies
peek_t peek;
for (int bi = 0; bi < N_BOXES; ++bi)
peek.b[bi] = s.b_idx[bi][s.result[bi]];
return peek;
}


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Michael S <already5chosen@yahoo.com> writes:

Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

[...]

I ran into trouble when I tried to work within the posted framework
to drive a solver. The difficulties were of several kinds. The
code didn't compile in my standard compilation environment, which
is roughly this (the c99 might be c11 but that made no difference):

gcc -x c -std=c99 -pedantic ...

What were the problems?
My gcc 14.2.0 on msys2 produces no warnings or errors with above
flags.

These source lines

struct timespec t0;
clock_gettime(CLOCK_MONOTONIC, &t0);

produced these diagnostics

tb.c:134:21: error: storage size of 't0' isn't known
tb.c:135:5: warning: implicit declaration of function
'clock_gettime' [...] tb.c:135:19: error: 'CLOCK_MONOTONIC'
undeclared (first use in this function)

under -std=c99. Apparently the first diagnostic, about
struct timespec, is fixed under -std=c11. It wasn't hard
to fix these, but it was irksome.

Sounds like under Linux and with -std=c99 flag function clock_gettime()
and related structures and constants are not declared/defined by default
in time.h.

Yes, gcc follows the ISO standard exactly, and does not define
symbols like clock_gettime, because the C standard does not
allow conforming impementations to do so.

Man page suggests magic pixie dust:

#define _XOPEN_SOURCE 600
#include <time.h>
#include <unistd.h>

It is my practice not to mix ISO-conformant and non-ISO-conformant
code in the same translation unit. It wasn't hard to find the
necessary tweak for a separate source file used to get the
current time:

#define _POSIX_C_SOURCE 199309L
#include <time.h>

after which both the 'struct timespec' and 'clock_gettime()' were
quite okay. I packaged the time in a way so it could get across
the function call interface and back to the main program.

If you ask why I used clock_gettime() instead of C standard
timespec_get() then the answer is that on Windows, eps. on older
versions like Win7 and WS2008 (which I prefer over newer stuff for
reasons unrelated to quality of C RTL), precision of timespec_get() is
poor. clock_gettime(CLOCK_MONOTONIC,) is much better.

Makes sense.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Michael S <already5chosen@yahoo.com> writes:

On Thu, 09 Apr 2026 16:37:30 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

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.

He was not fully sutisfied himself. 20 hours later he came with other formulation. Here is my attemp of translatioon:

1. There exist a disposition of cookies in boxes, for which it is
possible to select one cookie from each box, all of different sorts.
That is obvious. [MS: For example, each sort of cookies in its own dedicated box. That is a disposition that I use in my code] Let's call
the selection "thread".

2. There exists an operation that changes the disposition, but
preserves the property "it is possible to select a thread" (the
description of the operation would be given separately, a.t.m. it does
not matter).

3. By means of multiple operations of that type it is possible to turn
any arbitrary disposition to any other. Since after every step the
property "it is possible to select a thread" is preserved and because
there exist a disposition, for which this property is true, it means
that the property is true for any possible disposition.

4. The operations in question - exchange of any pair of cookies.
Comment: Induction is used only in (2) for proof that an operation
preserves the desired property.

For me, the second variant was less helpful. May be, for you it would
be more helpful.

I do at least understand it. It doesn't really help me construct
a solution, because I don't see how to transition from one choice
function (aka "thread") to another after exchanging a pair of
cookies. (Nor do I want an explanation of how to do so.)

[...code...]

In most cases I'm not a big fan of interactive debugging, but
trying to understand how this works might merit an exception.

Frankly, not all difficulties of following my code caused by the fact
that algorithm is derived from abstract proof.
Significant share of hurdles are rooted in my somewhat conflicting
desires to avoid all searches, except for inevitable search in the
innermost loop of the second pass, but at the same time to keep format
of the governing database (xch array+na array) minimalistic.

For what it's worth, I think your code has a better chance of
being understandable than the mathematical description of finding
a solution. Not interested enough to pursue it though.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Michael S <already5chosen@yahoo.com> writes:

[...]

I don't have a roadmap, but I have a variant of [approximately] the
same algorithm implemented in the style that is closer to your
preferences: implicit bookkeeping by recursion instead of explicit
lists and back-trace pointers. I even borrowed the name "seen" from the
code of your friend.

[..code..]

I appreciate the response. It will take me some time to look
at this, and so I'm not sure when I can get to it.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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?


--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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.

--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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.





--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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;
}




--- PyGate Linux v1.5.13
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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;
}














--- PyGate Linux v1.5.14
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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;
}


--- PyGate Linux v1.5.14
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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.

--- PyGate Linux v1.5.14
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Michael S <already5chosen@yahoo.com> writes:

[...]

After seeing your more recent posting I decided to focus on
that and let this one slide by.

--- PyGate Linux v1.5.14
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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.

--- PyGate Linux v1.5.14
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

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.






--- PyGate Linux v1.5.14
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)