Groups > comp.lang.c > #397345 > unrolled thread

Cookies in boxes - algorithmic challenge

Started by	Michael S <already5chosen@yahoo.com>
First post	2026-04-01 16:34 +0300
Last post	2026-04-17 20:17 +0200
Articles	18 on this page of 78 — 10 participants

Back to article view | Back to comp.lang.c

  Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 16:34 +0300
    Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 10:02 -0400
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:15 +0300
        Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 10:28 -0400
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:58 +0300
    Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 15:20 +0100
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:56 +0300
        Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 19:50 +0100
          Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 15:56 -0400
            Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 23:33 +0100
          Re: Cookies in boxes - algorithmic challenge Richard Harnden <richard.nospam@gmail.invalid> - 2026-04-04 07:43 +0100
            Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-04 11:54 +0100
    Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 15:24 -0400
    Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 17:24 -0400
      Re: Cookies in boxes - algorithmic challenge Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-04-02 16:25 +0100
        Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-02 17:10 +0100
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:19 +0300
        Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-02 13:03 -0400
          Re: Cookies in boxes - algorithmic challenge Richard Harnden <richard.nospam@gmail.invalid> - 2026-04-02 18:52 +0100
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-02 19:50 +0100
            Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:24 +0300
          Re: Cookies in boxes - algorithmic challenge Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-04-02 20:13 +0100
            Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:36 +0300
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:14 +0300
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:10 +0300
        Re: Cookies in boxes - algorithmic challenge Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-04-06 22:36 +0100
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 15:42 -0700
          Re: Cookies in boxes - algorithmic challenge Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-04-06 15:44 -0700
    Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-04 13:33 -0400
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-04 21:03 +0300
        Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-04 14:19 -0400
        Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-04 20:22 +0100
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-04 22:40 +0300
    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-04 17:08 -0700
    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-08 08:42 -0700
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 22:23 +0300
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 21:22 -0700
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 12:23 +0300
            Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-10 22:41 -0700
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 16:16 +0300
            Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:27 -0700
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-11 22:56 +0300
            Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 15:57 -0700
              Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-12 02:15 +0300
              Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-13 02:03 +0300
              Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-13 17:11 +0300
                Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 23:52 -0700
                  Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 14:44 +0300
                    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-17 07:40 -0700
                      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 18:30 +0300
                      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-20 00:43 +0300
                        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-21 20:37 +0300
                        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-21 18:22 -0700
                          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-22 12:05 +0300
                            Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-29 06:55 -0700
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-15 02:15 +0300
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 02:57 -0700
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 17:04 +0300
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 23:45 +0300
      Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 16:37 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 17:02 +0300
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 03:45 -0700
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-09 00:01 +0300
      Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 17:07 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 18:06 +0300
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:31 -0700
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 03:22 -0700
    Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 17:58 +0200
      Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 18:08 +0200
      Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-17 17:47 +0100
        Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:24 +0200
      Re: Cookies in boxes - algorithmic challenge scott@slp53.sl.home (Scott Lurndal) - 2026-04-17 19:58 +0000
        Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-18 05:52 +0200
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 11:53 +0100
            Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 12:04 +0100
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-18 20:35 +0300
    Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:52 +0200
      Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 20:17 +0200

Page 4 of 4 — ← Prev page 1 2 3 [4]

#397469

From	Michael S <already5chosen@yahoo.com>
Date	2026-04-10 17:02 +0300
Message-ID	<20260410170258.00000a01@yahoo.com>
In reply to	#397457

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.

[toc] | [prev] | [next] | [standalone]

#397483

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-04-11 03:45 -0700
Message-ID	<86wlydai7y.fsf@linuxsc.com>
In reply to	#397469

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.

[toc] | [prev] | [next] | [standalone]

#397430

From	Michael S <already5chosen@yahoo.com>
Date	2026-04-09 00:01 +0300
Message-ID	<20260409000116.0000461d@yahoo.com>
In reply to	#397345

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

[toc] | [prev] | [next] | [standalone]

#397458

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-04-09 17:07 -0700
Message-ID	<86a4vbbruq.fsf@linuxsc.com>
In reply to	#397430

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.

[toc] | [prev] | [next] | [standalone]

#397470

From	Michael S <already5chosen@yahoo.com>
Date	2026-04-10 18:06 +0300
Message-ID	<20260410180644.00006e88@yahoo.com>
In reply to	#397458

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

[toc] | [prev] | [next] | [standalone]

#397485

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-04-11 04:31 -0700
Message-ID	<86ik9xag2z.fsf@linuxsc.com>
In reply to	#397470

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.

[toc] | [prev] | [next] | [standalone]

#397591

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2026-04-16 03:22 -0700
Message-ID	<86ik9r6w8n.fsf@linuxsc.com>
In reply to	#397470

Michael S <already5chosen@yahoo.com> writes:

[...]

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

[toc] | [prev] | [next] | [standalone]

#397633

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2026-04-17 17:58 +0200
Message-ID	<10rtlbt$2igdj$1@raubtier-asyl.eternal-september.org>
In reply to	#397345

Is this a correct way to randomize the boxes so that there's at least
one cookie of each kind per box ?

#include <iostream>
#include <array>
#include <random>
#include <cstdint>
#include <algorithm>
#include <span>

using namespace std;

int main()
{
	using box = array<uint8_t, 10>;
	array<box, 20> boxes;
	for( size_t bx = 0; bx < boxes.size(); ++bx )
		for( uint8_t &cookie : boxes[bx] )
			cookie = (uint8_t)bx;
	mt19937_64 mt;
	uniform_int_distribution<size_t>
		rndBox( 0, 19 ),
		rndCookie( 1, 9 );
	for( box &bx : boxes )
	{
		for( uint8_t &ck : span( bx.begin() + 1, bx.end() ) )
			swap( ck, boxes[rndBox( mt )][rndCookie( mt )] );
		swap( bx[0], boxes[rndBox( mt )][0] );
	}
	for( box &bx : boxes )
		sort( bx.begin(), bx.end() );
}

[toc] | [prev] | [next] | [standalone]

#397634

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2026-04-17 18:08 +0200
Message-ID	<10rtlt8$2igdj$2@raubtier-asyl.eternal-september.org>
In reply to	#397633

Now the shuffling is complete:

int main()
{
	using box = array<uint8_t, 10>;
	array<box, 20> boxes;
	for( size_t bx = 0; bx < boxes.size(); ++bx )
		for( uint8_t &cookie : boxes[bx] )
			cookie = (uint8_t)bx;
	mt19937_64 mt;
	uniform_int_distribution<size_t>
		rndBox( 0, 19 ),
		rndCookie19( 1, 9 ),
		rndCookie09( 0, 9 );
	for( box &bx : boxes )
	{
		for( uint8_t &ck : span( bx.begin() + 1, bx.end() ) )
			swap( ck, boxes[rndBox( mt )][rndCookie19( mt )] );
		for( uint8_t &ck : bx )
			swap( ck, bx[rndCookie09( mt )] );
	}
}

[toc] | [prev] | [next] | [standalone]

#397636

From	Bart <bc@freeuk.com>
Date	2026-04-17 17:47 +0100
Message-ID	<10rto7j$2jfm5$2@dont-email.me>
In reply to	#397633

On 17/04/2026 16:58, Bonita Montero wrote:
> Is this a correct way to randomize the boxes so that there's at least
> one cookie of each kind per box ?

That's not possible. There are 20 types of cookie, but you can only have 
10 per box. Those might all be of the same kind.

(I took an array of 200 cookies (10 times one instance of each) and 
randomly shuffled, then stored those in the boxes. Or you can populate 
the boxes with an ordered selection then shuffle in situ.)


> #include <iostream>
> #include <array>
> #include <random>
> #include <cstdint>
> #include <algorithm>
> #include <span>
> 
> using namespace std;
> 
> int main()
> {
>      using box = array<uint8_t, 10>;
>      array<box, 20> boxes;
>      for( size_t bx = 0; bx < boxes.size(); ++bx )
>          for( uint8_t &cookie : boxes[bx] )
>              cookie = (uint8_t)bx;
>      mt19937_64 mt;
>      uniform_int_distribution<size_t>
>          rndBox( 0, 19 ),
>          rndCookie( 1, 9 );
>      for( box &bx : boxes )
>      {
>          for( uint8_t &ck : span( bx.begin() + 1, bx.end() ) )
>              swap( ck, boxes[rndBox( mt )][rndCookie( mt )] );
>          swap( bx[0], boxes[rndBox( mt )][0] );
>      }
>      for( box &bx : boxes )
>          sort( bx.begin(), bx.end() );
> }

[toc] | [prev] | [next] | [standalone]

#397638

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2026-04-17 19:24 +0200
Message-ID	<10rtqbe$2k7oj$1@raubtier-asyl.eternal-september.org>
In reply to	#397636

Am 17.04.2026 um 18:47 schrieb Bart:
> On 17/04/2026 16:58, Bonita Montero wrote:
>> Is this a correct way to randomize the boxes so that there's at least
>> one cookie of each kind per box ?
> 
> That's not possible. There are 20 types of cookie, but you can only have 
> 10 per box. Those might all be of the same kind.

_At least one_ is possible, but not all kinds.

There was a subtle bug with my latest code.
Here's the correct shuffling:

#include <iostream>
#include <array>
#include <random>
#include <cstdint>
#include <algorithm>
#include <span>

using namespace std;

int main()
{
	constexpr size_t
		Boxes = 20,
		Cookies = 10;
	using box = array<uint8_t, Cookies>;
	array<box, Boxes> boxes;
	for( size_t flavour = 0; flavour < Boxes; ++flavour )
		fill( boxes[flavour].begin(), boxes[flavour].end(), (uint8_t)flavour );
	mt19937_64 mt;
	uniform_int_distribution<size_t>
		rndBox( 0, Boxes - 1 ),
		rndInBoxX1( 1, Cookies - 1 ),
		rndInBox( 0, Cookies - 1 );
	for( box &bx : boxes )
		for( uint8_t &cookie : span( bx.begin() + 1, bx.end() ) )
			swap( cookie, boxes[rndBox( mt )][rndInBoxX1( mt )] );
	for( box &bx : boxes )
		for( uint8_t &cookie : bx )
			swap( cookie, bx[rndInBox( mt )] );
}

[toc] | [prev] | [next] | [standalone]

#397643

From	scott@slp53.sl.home (Scott Lurndal)
Date	2026-04-17 19:58 +0000
Message-ID	<EhwER.293851$4wI6.212206@fx24.iad>
In reply to	#397633

Bonita Montero <Bonita.Montero@gmail.com> writes:
>Is this a correct way to randomize the boxes so that there's at least
>one cookie of each kind per box ?

No, because this is comp.lang.c, not comp.lang.c++.

[toc] | [prev] | [next] | [standalone]

#397649

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2026-04-18 05:52 +0200
Message-ID	<10ruv6c$2v9nf$1@raubtier-asyl.eternal-september.org>
In reply to	#397643

Am 17.04.2026 um 21:58 schrieb Scott Lurndal:

> Bonita Montero <Bonita.Montero@gmail.com> writes:

>> Is this a correct way to randomize the boxes so that there's at least
>> one cookie of each kind per box ?

> No, because this is comp.lang.c, not comp.lang.c++.

"The solution does not have to be in C, ..."

[toc] | [prev] | [next] | [standalone]

#397654

From	Bart <bc@freeuk.com>
Date	2026-04-18 11:53 +0100
Message-ID	<10rvnra$34jna$2@dont-email.me>
In reply to	#397649

On 18/04/2026 04:52, Bonita Montero wrote:
> Am 17.04.2026 um 21:58 schrieb Scott Lurndal:
> 
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
> 
>>> Is this a correct way to randomize the boxes so that there's at least
>>> one cookie of each kind per box ?
> 
>> No, because this is comp.lang.c, not comp.lang.c++.
> 
> "The solution does not have to be in C, ..."
> 

OK, here's one in my scripting language:

   proc main=
       names := splitstring("Martin Hohenberg, ... Andres Cordova", ", ")
       for i, x in names do
           names[i] := splitstring(x, " ")
       end

       isort(names, {a, b: convlc(a[$]) > convlc(b[$])})

       for i, x in names do
           println i, joinstrings(x, " ")
       end
   end

Its output is shown below. The parsing is not thorough, for examples it 
expects exactly one comma and one space between names, but it works for 
the OP's test data.

If the string data is excluded, my version is 245 characters, compared 
with 1589 for your C++. Compilation time is 0.0 seconds.

1 Paul Abbott
2 Neil Anuskiewicz
3 Masa Bando
4 Tim Bando
5 George Brower
6 Kyle Burkholder
7 John Carmack
8 Dale Carstensen
9 Jonathan Cast
10 Christopher Chang
11 Gratiela Chergu
12 William Christensen
13 Michael Ciagala
14 Andres Cordova
15 James Cronin
16 Nodarius Darjania
17 darrin
18 Rod Davenport
19 Chip Davis
20 Killer Delicious
21 Sven Dowideit
22 Steven Evans
23 Cheryl Evry
24 Daniel Garber
25 Mark Gardner
26 Donald Greer
27 Hal Hildebrand
28 Martin Hohenberg
29 David L. Jessup
30 Liudmilla Karukina
31 Ken Kennedy
32 Ken LaCrosse
33 Clemens Ladisch
34 Ron Lauzon
35 Wenfeng Liang
36 Brendan Long
37 Jacob Lyles
38 Jim McCloskey
39 Mordant
40 Mike Nichols
41 Michael Nygard
42 Malcolm Ocean
43 Doug Phillips
44 Mark Ping
45 Matt Pollard
46 ReallyBored
47 Irving Rivas
48 Jan Roudaut
49 Dewey Sasser
50 John Simpson
51 Bill Soistman
52 Hsueh Sung
53 taishi28012
54 Jane Tang
55 Tom Taylor
56 TheFred
57 Paul Theodoropolous
58 Jerod Tufte
59 Les Vogel
60 Xingyu Wang
61 Arnold F. Williams
62 Stan Witherspoon
63 Dave Witten
64 Connor Wood
65 Wojciech Woytniak
66 Jae Yang
67 Άρης Δάσος

[toc] | [prev] | [next] | [standalone]

#397655

From	Bart <bc@freeuk.com>
Date	2026-04-18 12:04 +0100
Message-ID	<10rvof7$34jna$3@dont-email.me>
In reply to	#397654

On 18/04/2026 11:53, Bart wrote:
> On 18/04/2026 04:52, Bonita Montero wrote:
>> Am 17.04.2026 um 21:58 schrieb Scott Lurndal:
>>
>>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>
>>>> Is this a correct way to randomize the boxes so that there's at least
>>>> one cookie of each kind per box ?
>>
>>> No, because this is comp.lang.c, not comp.lang.c++.
>>
>> "The solution does not have to be in C, ..."
>>
> 
> OK, here's one in my scripting language:

Um, this is for DFS's sorting challenge, not Michael S's cookie puzzle.

DFS I think specified a solution in C.

So both my and your versions aren't allowed.

(I'm not going to do a C version; it's far too much fiddly work.

For a real application, I would look at creating a suite of functions to 
help out, but it's not worth doing that here.)

> If the string data is excluded, my version is 245 characters, compared 
> with 1589 for your C++. Compilation time is 0.0 seconds.

That is, the C++ for the name sorting program.

[toc] | [prev] | [next] | [standalone]

#397662

From	Michael S <already5chosen@yahoo.com>
Date	2026-04-18 20:35 +0300
Message-ID	<20260418203512.0000272a@yahoo.com>
In reply to	#397649

On Sat, 18 Apr 2026 05:52:46 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> Am 17.04.2026 um 21:58 schrieb Scott Lurndal:
> 
> > Bonita Montero <Bonita.Montero@gmail.com> writes:  
> 
> >> Is this a correct way to randomize the boxes so that there's at
> >> least one cookie of each kind per box ?  
> 
> > No, because this is comp.lang.c, not comp.lang.c++.  
> 
> "The solution does not have to be in C, ..."
>

The solution, i.e. implementation of the function solver(), does not
have to be in C. But it has to be pluggable into specified test bench,
which is coded in C.
It does not sound as you're interested in finding solution of the
challenge. 
On my part, I am not interested in your attempts to provide an
alternative test bench.

In unlikely case that I am wrong about your intentions, below provided
variant of test bench that can be compiled both as C and as 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,
  uint64_t* prngs, uint64_t seed);
int main(int argz, char** argv)
{
  int rep1=128, rep2=11;
  unsigned long long seed = 1;
  if (argz > 1) {
    if (strcmp(argv[1], "?")== 0 ||
        strcmp(argv[1], "-?")== 0) {
      fprintf(stderr,
        "Usage:\n"
        "greg_solver_tb [rep1 [rep2]] -s=seed\n"
        "where\n"
        "rep1 - number of solver calls in one time measurement set.
Default 128\n" "rep2 - number of repetitions of time measurement.
Default 11\n" "seed - PRNG seed\n"
      );
      return 0;
    }

    static const int mx[2] = { (int)1e7, 10000 };
    for (int arg_i = 1, val_i = 0; arg_i < 4 && arg_i < argz; ++arg_i) {
      char* arg = argv[arg_i];
      if (strncmp(arg, "-s=", 3)== 0) {
        char* seedstr = arg+3;
        char* endp;
        seed = strtoull(seedstr, &endp, 0);
        if (endp == seedstr) {
          fprintf(stderr, "seed argument '%s' is not a number\n",
    seedstr); return 1;
        }
      } else {
        char* endp;
        long long n = strtoll(arg, &endp, 0);
        if (endp == arg) {
          fprintf(stderr, "argument '%s' is not a number\n", arg);
          return 1;
        }
        int n_mx = mx[val_i];
        if (n < 1 || n > n_mx) {
          fprintf(stderr, "argument '%s' out of range. Please specify
    value in range[1:%d]\n" , arg, n_mx);
          return 1;
        }
        if (val_i==0)
          rep1 = n;
        else
          rep2 = n;
        ++val_i;
      }
    }
  }

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

  uint64_t* prngs = (uint64_t*)mem;
  boxes_t* boxes = (boxes_t*)&prngs[rep1];
  peek_t* results = (peek_t*)&boxes[rep1];
  int ret = test(boxes, results, rep1, rep2, prngs, seed);
  free(mem);

  return ret;
}

static uint32_t my_prng(uint64_t* pState)
{
  // we don't need very good PRNG,
  // but it has to repeatable cross-platform,
  // so C RTL rand() is not suitable
  const uint64_t PRNG_A = 2862933555777941757ull;
  const uint64_t PRNG_C = 20260329ull;
  uint64_t s = *pState*PRNG_A + PRNG_C;
  *pState = s;
  return s >> 32;
}

static void make_random_boxes(boxes_t* dst, uint64_t* prng)
{
  uint8_t pool[N_BOXES*BOX_SIZE];
  for (int i = 0; i < N_BOXES; ++i)
    for (int k = 0; k < BOX_SIZE; ++k)
      pool[i*BOX_SIZE+k] = i;

  for (int i = 0; i < N_BOXES; ++i) {
    for (int k = 0; k < BOX_SIZE; ++k) {
      uint32_t rnd = my_prng(prng);
      int idx0 = i*BOX_SIZE+k;
      int idx1 = ((N_BOXES*BOX_SIZE-idx0)*(uint64_t)rnd >> 32)+idx0;
      uint8_t v0 = pool[idx0];
      uint8_t v1 = pool[idx1];
      dst->b[i][k] = v1;
      pool[idx1] = v0;
    }
  }
}

static bool validate(const boxes_t* bx, const peek_t* res)
{
  bool cookies[N_BOXES]={0};
  for (int i = 0; i < N_BOXES; ++i) {
    unsigned v = res->b[i];
    if (v >= BOX_SIZE) {
      fprintf(stderr, "res[%d] = %d. Out of range!\n", i, v);
      return false;
    }
    unsigned c = bx->b[i][v];
    if (cookies[c]) {
      fprintf(stderr, "res[%d] = %d. bx[%d][%d]=%d repeated.\n"
        , i, v
        , i, v, c);
      return false;
    }
    cookies[c] = true;
  }
  return true;
}

static int cmp_ll(const void* pa, const void* pb) {
  long long a = *(const long long*)pa;
  long long b = *(const long long*)pb;
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}


static int test(boxes_t* boxes, peek_t* results, int rep1, int rep2,
  uint64_t* prngs, uint64_t seed)
{
  uint64_t prng = seed;
  long long dt[rep2];
  long long mn, mx;
  uint64_t mn_prng, mx_prng;
  for (int it = 0; it < rep2; ++it) {
    for (int i = 0; i < rep1; ++i) {
      prngs[i] = prng;
      make_random_boxes(&boxes[i], &prng);
    }
    struct timespec t0;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int i = 0; i < rep1; ++i)
      results[i] = solver(boxes[i]);
    struct timespec t1;
    clock_gettime(CLOCK_MONOTONIC, &t1);
    long long delta_t = (t1.tv_sec-t0.tv_sec)*(long long)1e9+
t1.tv_nsec-t0.tv_nsec; dt[it] = delta_t;
    if (it == 0 || mn > delta_t) {
      mn = delta_t;
      mn_prng = prngs[0];
    }
    if (it == 0 || mx < delta_t) {
      mx = delta_t;
      mx_prng = prngs[0];
    }

    for (int i = 0; i < rep1; ++i) {
      if (!validate(&boxes[i], &results[i])) {
        fprintf(stderr,
          "Test fail at iteration %d,%d. prng %llu\n"
          ,it, i, prngs[i]);
        fprintf(stderr, "boxes:\n");
        for (int bi = 0; bi < N_BOXES; ++bi) {
          for (int k = 0; k < BOX_SIZE; ++k)
            fprintf(stderr, " %2d", boxes[i].b[bi][k]);
          fprintf(stderr, " : %d => %2d\n"
            , results[i].b[bi]
            , boxes[i].b[bi][results[i].b[bi]]);
        }
        return 1;
      }
    }
  }

  qsort(dt, rep2, sizeof(*dt), cmp_ll);
  long long med = dt[rep2/2];
  double scale = 1e-6/rep1;
  printf("o.k.\nmed=%.6f msec. min=%.6f msec, prng %llu. max=%.6f msec,
  prng %llu.\n" , med*scale
    , mn*scale, mn_prng
    , mx*scale, mx_prng
  );

  return 0;
}

[toc] | [prev] | [next] | [standalone]

#397640

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2026-04-17 19:52 +0200
Message-ID	<10rts10$2kh5m$1@raubtier-asyl.eternal-september.org>
In reply to	#397345

I guess that works. Coding style is perfect for my taste.

#include <iostream>
#include <array>
#include <random>
#include <cstdint>
#include <algorithm>
#include <span>
#include <iomanip>

using namespace std;

int main()
{
	constexpr size_t
		Boxes = 20,
		Cookies = 10;
	using box = array<uint8_t, Cookies>;
	array<box, Boxes> boxes;
	for( size_t iFlavour = 0; iFlavour < Boxes; ++iFlavour )
		fill( boxes[iFlavour].begin(), boxes[iFlavour].end(), (uint8_t)iFlavour );
	mt19937_64 mt( (random_device())() );
	uniform_int_distribution<size_t>
		rndBox( 0, Boxes - 1 ),
		rndInBoxX1( 1, Cookies - 1 ),
		rndInBox( 0, Cookies - 1 );
	for( box &bx : boxes )
		for( uint8_t &cookie : span( bx.begin() + 1, bx.end() ) )
			swap( cookie, boxes[rndBox( mt )][rndInBoxX1( mt )] );
	for( box &bx : boxes )
		for( uint8_t &cookie : bx )
			swap( cookie, bx[rndInBox( mt )] );
	for( box &bx : boxes )
		swap( bx, boxes[rndBox( mt )] );
	for( size_t iBx = 0; iBx < Boxes; ++iBx )
	{
		auto attrs = []( auto &prnt ) -> auto & { return prnt << setw( 2 ) << 
setfill( ' ' ) << right; };
		attrs( cout << "box " ) << (int)iBx << ": ";
		box &bx = boxes[iBx];
		for( uint8_t cookie : span( bx.begin(), bx.end() - 1 ) )
			attrs( cout ) << (int)cookie << ", ";
		attrs( cout ) << (int)bx[Cookies - 1] << endl;
	}
	cout << endl;
	for( size_t iFlavour = 0; iFlavour < Boxes; ++iFlavour )
		for( size_t iBox = 0; iBox < Boxes; ++iBox )
			for( size_t iCookie = 0; iCookie < Cookies; ++iCookie )
				if( boxes[iBox][iCookie] == iFlavour )
				{
					cout << "flavour " << iFlavour << " is at place " << iCookie << " 
in box " << iBox << endl;
					iCookie = Cookies;
					iBox = Boxes;
				}
}

[toc] | [prev] | [next] | [standalone]

#397641

From	Bonita Montero <Bonita.Montero@gmail.com>
Date	2026-04-17 20:17 +0200
Message-ID	<10rttfg$2l7rd$1@raubtier-asyl.eternal-september.org>
In reply to	#397640

There was still a bug in the before code: Cookies could be taken
from a box more than once. I guess this code is perfect now:

#include <iostream>
#include <array>
#include <random>
#include <cstdint>
#include <algorithm>
#include <span>
#include <iomanip>

using namespace std;

int main()
{
	constexpr size_t
		Flavours = 20,
		Cookies = 10;
	using box = array<uint8_t, Cookies>;
	array<box, Flavours> boxes;
	for( size_t iFlavour = 0; iFlavour < Flavours; ++iFlavour )
		fill( boxes[iFlavour].begin(), boxes[iFlavour].end(), (uint8_t)iFlavour );
	mt19937_64 mt( (random_device())() );
	uniform_int_distribution<size_t>
		rndBox( 0, Flavours - 1 ),
		rndInBoxX1( 1, Cookies - 1 ),
		rndInBox( 0, Cookies - 1 );
	for( box &bx : boxes )
		for( uint8_t &cookie : span( bx.begin() + 1, bx.end() ) )
			swap( cookie, boxes[rndBox( mt )][rndInBoxX1( mt )] );
	for( box &bx : boxes )
		for( uint8_t &cookie : bx )
			swap( cookie, bx[rndInBox( mt )] );
	for( box &bx : boxes )
		swap( bx, boxes[rndBox( mt )] );
	for( size_t iBx = 0; iBx < Flavours; ++iBx )
	{
		auto attrs = []( auto &prnt ) -> auto & { return prnt << setw( 2 ) << 
setfill( ' ' ) << right; };
		attrs( cout << "box " ) << (int)iBx << ": ";
		box &bx = boxes[iBx];
		for( uint8_t cookie : span( bx.begin(), bx.end() - 1 ) )
			attrs( cout ) << (int)cookie << ", ";
		attrs( cout ) << (int)bx[Cookies - 1] << endl;
	}
	cout << endl;
	array<bool, Flavours> used { false };
	for( size_t iFlavour = 0; iFlavour < Flavours; ++iFlavour )
		for( size_t iBox = 0; iBox < Flavours; ++iBox )
			if( !used[iBox] )
				for( size_t iCookie = 0; iCookie < Cookies; ++iCookie )
					if( boxes[iBox][iCookie] == iFlavour )
					{
						cout << "flavour " << iFlavour << " is at place " << iCookie << " 
in box " << iBox << endl;
						used[iBox] = true;
						iCookie = Cookies;
						iBox = Flavours;
					}
}

[toc] | [prev] | [standalone]

Page 4 of 4 — ← Prev page 1 2 3 [4]

csiph-web

Cookies in boxes - algorithmic challenge

Contents

#397469

#397483

#397430

#397458

#397470

#397485

#397591

#397633

#397634

#397636

#397638

#397643

#397649

#397654

#397655

#397662

#397640

#397641