Groups | Search | Server Info | Login | Register

Groups > comp.lang.c > #397470

Re: Cookies in boxes - algorithmic challenge

From Michael S <already5chosen@yahoo.com>
Newsgroups comp.lang.c
Subject Re: Cookies in boxes - algorithmic challenge
Date 2026-04-10 18:06 +0300
Organization A noiseless patient Spider
Message-ID <20260410180644.00006e88@yahoo.com> (permalink)
References <20260401163447.000052de@yahoo.com> <20260409000116.0000461d@yahoo.com> <86a4vbbruq.fsf@linuxsc.com>

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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 Michael S <already5chosen@yahoo.com> - 2026-04-15 02:15 +0300
      Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 02:57 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 17:04 +0300
  Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 23:45 +0300
    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 16:37 -0700
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 17:02 +0300
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 03:45 -0700
  Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-09 00:01 +0300
    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 17:07 -0700
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 18:06 +0300
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:31 -0700
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 03:22 -0700
  Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 17:58 +0200
    Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 18:08 +0200
    Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-17 17:47 +0100
      Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:24 +0200
    Re: Cookies in boxes - algorithmic challenge scott@slp53.sl.home (Scott Lurndal) - 2026-04-17 19:58 +0000
      Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-18 05:52 +0200
        Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 11:53 +0100
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 12:04 +0100
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-18 20:35 +0300
  Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:52 +0200
    Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 20:17 +0200

csiph-web