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-17 18:30 +0300
Organization	A noiseless patient Spider
Message-ID	<20260417183017.000011ba@yahoo.com> (permalink)
References	(5 earlier) <865x5x9kbw.fsf@linuxsc.com> <20260413171129.0000003d@yahoo.com> <86a4v26pup.fsf@linuxsc.com> <20260417144410.00006d46@yahoo.com> <865x5p7ir6.fsf@linuxsc.com>

Show all headers | View raw

On Fri, 17 Apr 2026 07:40:13 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
> 
> > On Thu, 16 Apr 2026 23:52:14 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:  
> 
> [...]
> 
> > 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.  
> 
> I posted what I did because I wanted the focus to be on reading the
> code and not on running the code.  I was hoping that understanding
> would be feasible without needing any guessing.
> 
> > It's pretty easy to guess that the code above preceded by:
> >
> > [...]  
> 
> Looks reasonable.
> 
> > 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.  
> 
> Here is one implementation of best_next_ctype():
> 
> Ctype
> best_next_ctype( Index depth, Bset free, Bsets *bsets, Ctype ctypes[]
> ){ // permute?
>     return  ctypes[depth];
> }
> 
> At the "permute?" comment an implementation could perform any
> permutation of the elements of the ctypes[] array, within the range
> of ctypes[depth] and ctypes[COOKIE_LIMIT-1], and the result should
> still be a working solution.  Or just leave it as a comment.  The
> correctness of the code doesn't depend on what permutation is done
> or how the choice is made.
> 
> >> 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!  
> 
> The way the code is written it allows the value of COOKIE_LIMIT to
> be chosen independently of the value of N_BOXES (or at least I hope
> it does).  I didn't explore any such cases but it might be
> interesting to do that.
> 
> > 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.  
> 
> Of course for the code posted the value of N_BOXES must be no more
> than the number of bits in the bitset type Bset (which is meant to
> be short for "Box set", or a set of box values).
> 
> > But, then again, without source code of best_next_ctype() I can not
> > be sure about it.  
> 
> My questions are these.  One, could you understand what the code is
> doing and how it works?  And two, if given an appropriate choice of
> what permutation is done in best_next_ctype(), does this code do the
> same thing as your code?  I was trying to match the behavior of your
> code but I wasn't able to figure out how it decided where to go
> next.

No, as it is, it does not match the behavior of my code or of code of
your friend. One very simple, but very important element of search state
is missing.
I am reasonably sure that it can not be emulated by permutation of
ctypes array within best_next_ctype() routine.

As to observed timing, if your code is run for big number of cases, e.g.
rep1=128, rep2=9999 (small modification of test bench required to enable
bigger rep2), it sometimes ends up very slow. My test bench is not well
suited to find exactly how slow, but my guess is above 0.1 sec. That's
very different from mine or your friends, where difference between
median and worst case is small, likeley less than 3x.


More convenient test bench that reports PRNG and can take PRNG seed as
input:

#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] = { 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 = 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;
}

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

csiph-web