Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Cookies in boxes - algorithmic challenge
Date: Thu, 09 Apr 2026 17:07:25 -0700
Organization: A noiseless patient Spider
Lines: 130
Message-ID: <86a4vbbruq.fsf@linuxsc.com>
References: <20260401163447.000052de@yahoo.com> <20260409000116.0000461d@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Fri, 10 Apr 2026 00:07:26 +0000 (UTC)
Injection-Info: dont-email.me; posting-host="fec39c7ed8a94a1212fc4479cf7de941"; logging-data="752111"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+nAu6Aa9HDJwvbDWZqDZxsXey/hxK1Cro="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:Leyotyy+2Dq1UQ5t+9jIXTrwLFw= sha1:MdwGueavVy2R3r8ubdVHbQSDH/s=
Xref: csiph.com comp.lang.c:397458

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.