Groups | Search | Server Info | Login | Register

Groups > comp.lang.c > #397345

Cookies in boxes - algorithmic challenge

From Michael S <already5chosen@yahoo.com>
Newsgroups comp.lang.c
Subject Cookies in boxes - algorithmic challenge
Date 2026-04-01 16:34 +0300
Organization A noiseless patient Spider
Message-ID <20260401163447.000052de@yahoo.com> (permalink)

Show all headers | View raw

My challenge is not about 'C'. 'C' is a boring language that mostly
happens to work. I see no point in challenging it.
The challenge is algorithmic.

However I am issuing it in comp.lang.c group. Then the test bench that
I prepared is in C. The solution does not have to be in C, but it would
be significantly simpler for everybody, esp. for those that are
interested in reproduction, if solution comes in 'C'.

So, here is the challenge:
There are 20 sorts of cookies, 10 of each sort. They are placed in 20
boxes, again, 10 cookies in each boxes. You have to take exactly one
cookie from each box, all 20 of different sorts.
Smart math heads proved that for any distribution a solution exists. I
don't ask you to repeat the proof. Just peek cookies!

It's obvious that one can find the solution by exhausting. Don't do
it. Indeed, the number of possible peek orders is finite, but ii is
large - 2.4e18.
Be smarter.
On modern PC I want to get a solution in less than 1 msec, bonus for
less than 50usec.

Test bench.

// solver.h
#include <stdint.h>

enum {
  N_BOXES = 20,
  BOX_SIZE = 10,
};

typedef struct {
  uint8_t b[N_BOXES][BOX_SIZE];
} boxes_t;

typedef struct {
  uint8_t b[N_BOXES];
} peek_t;

peek_t solver(boxes_t boxes);
// end of  solver.h


// tb.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);
int main(int argz, char** argv)
{
  int rep1=128, rep2=11;
  if (argz > 1) {
    if (strcmp(argv[1], "?")== 0 ||
        strcmp(argv[1], "-?")== 0) {
      fprintf(stderr,
"Usage:\n"
"solver_tb [rep1 [rep2]]\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" 
      );
      return 0;
    }

    static const int mx[2] = { 1e7, 1000 };
    for (int arg_i = 1; arg_i < 3 && arg_i < argz; ++arg_i) {
      char* arg = argv[arg_i];
      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[arg_i-1];
      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 (arg_i==1)
        rep1 = n;
      else
        rep2 = n;
    }
  }

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

  boxes_t* boxes = mem;
  peek_t* results = (peek_t*)&boxes[rep1];
  int ret = test(boxes, results, rep1, rep2);
  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 prng = 1;
  long long dt[rep2];
  for (int it = 0; it < rep2; ++it) {
    for (int i = 0; i < rep1; ++i)
      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);
    dt[it] = (t1.tv_sec-t0.tv_sec)*(long long)1e9+ 
      t1.tv_nsec-t0.tv_nsec;

    for (int i = 0; i < rep1; ++i) {
      if (!validate(&boxes[i], &results[i])) {
        fprintf(stderr,
          "Test fail at iteration %d,%d\n"
          ,it, 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 mn = dt[0], mx = dt[rep2-1], med = dt[rep2/2];
  double scale = 1e-6/rep1;
  printf("o.k.\nmed=%.6f msec, min=%.6f msec, max=%.6f msec\n"
    ,med*scale, mn*scale, mx*scale);

  return 0;
}
// end of tb.c

You have to implement function solver() in module solver.c

Back to comp.lang.c | Previous | Next — 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