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-18 20:35 +0300
Organization	A noiseless patient Spider
Message-ID	<20260418203512.0000272a@yahoo.com> (permalink)
References	<20260401163447.000052de@yahoo.com> <10rtlbt$2igdj$1@raubtier-asyl.eternal-september.org> <EhwER.293851$4wI6.212206@fx24.iad> <10ruv6c$2v9nf$1@raubtier-asyl.eternal-september.org>

Show all headers | View raw

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

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