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: Wed, 08 Apr 2026 08:42:11 -0700
Organization: A noiseless patient Spider
Lines: 147
Message-ID: <86tstlwjak.fsf@linuxsc.com>
References: <20260401163447.000052de@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Wed, 08 Apr 2026 15:42:14 +0000 (UTC)
Injection-Info: dont-email.me; posting-host="078da6b6fdfa8b5cb04ea822fecda5b3"; logging-data="3891192"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19ggJ0QG4uP/0T2Pr5pBz0nMFce9lQ0Gg4="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:0Kr04MGT/gQfiLAyky3Tik48ezQ= sha1:5PvcmWkgMz/N1Lqe4ZoXQoDfWaY=
Xref: csiph.com comp.lang.c:397424

Michael S <already5chosen@yahoo.com> writes:

[...]

Here I am again, ready now to write a more substantive response.

> 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!

I think the problem is interesting.  I thought I would try coding
something up.

> 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.

[.. C code to drive an exercise a proposed solution ..]

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

I ran into trouble when I tried to work within the posted framework
to drive a solver.  The difficulties were of several kinds.  The
code didn't compile in my standard compilation environment, which
is roughly this (the c99 might be c11 but that made no difference):

    gcc -x c -std=c99 -pedantic ...

I was able to work through that problem but it was irksome.  The
second difficulty is the interface to solver() seems rather clunky
to me, maybe not for the input but for the output, and it wasn't
clear to me what the specification is for the output (I did manage
to figure this out but only much later).  I was having to put more
effort into figuring out the interface than solving the problem.

Finally I abandoned the idea of working within the structure of the
posted driver code and wrote a solver to my own specification.
Doing that was fairly straightforward and took half an hour or so
(disclaimer: after I had spent a good amount of time just thinking
about the problem).  After writing the solver I reimplemented a
driver framework to drive it, conforming to the interface I was
using.  Some debugging was needed to get everything working.  I did
some rudimentary time measurements for the solver.  Results were
good (more about the specifics later).

After doing the new solver I went back to the posted driver code,
and grafted together the new solver with the orginal driver.  Some
glue code was needed to reconcile the differences in interface
between the new solver and the original driver.  Then I needed to
figure out the semantics of the output, which were different than
what I expected and originally understood.  I figured all that out
and got things working.  Sadly the code was uglier than I would have
liked.

After that, I talked to a friend to try a different approach to
producing a solution.  After some light editing by myself -- mostly
just formatting and some name changes -- the code below was put into
the hopper.  (Note: I claim no credit for code below.  I did some
editing to make it more readable but beyond that none of it is a
result of my efforts.)

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

    static      uint32_t    adjacent[      N_BOXES ];
    static           int    cookie_of_box[ N_BOXES ];
    static           int    box_of_cookie[ N_BOXES ];
    static      uint32_t    seen;

    static int
    search( int b ){
        uint32_t m = adjacent[b];
        while(  m  ){
            uint32_t bit = m & -m;
            m ^= bit;
            int c = __builtin_ctz( bit );
            if(  seen & 1u<<c  )  continue;
            seen |= 1u<<c;
            if(  box_of_cookie[c] == -1  ||  search( box_of_cookie[c] )  ){
                box_of_cookie[c] = b;
                cookie_of_box[b] = c;
                return  1;
            }
        }
        return  0;
    }

    peek_t
    solver( boxes_t boxes ){
      peek_t res;

        for(  int i = 0;  i < N_BOXES;  i++  ){
            uint32_t m = 0;
            for(  int k = 0;  k < BOX_SIZE;  k++  ){
                m |= 1u << boxes.b[i][k];
            }
            adjacent[i] = m;
            cookie_of_box[i] = -1;
            box_of_cookie[i] = -1;
        }

        for(  int i = 0;  i < N_BOXES;  i++  ){
            seen = 0;
            search( i );
        }

        for(  int i = 0;  i < N_BOXES;  i++  ){
            int c = cookie_of_box[i];
            for(  int k = 0;  k < BOX_SIZE;  k++  ){
                if(  boxes.b[i][k] == c  ){
                    res.b[i] = k;
                    break;
                }
            }
        }
        return  res;
    }

Despite being derived independently, this code uses the same sort of
approach that I had used, except my code was recursive rather than
iterative.

Running the above code with default settings (128 11) produced this
output

    o.k.
    med=0.003542 msec, min=0.003487 msec, max=0.003911 msec

The timing results for my second code effort were similar, except
that the value for max was about 0.3 msec.

Informal timing measurements on my original solver -- in particular
using a different interface, and done simply by using 'time' in the
shell to measure a million calls to the solver -- gave per-call
times that were better by about a factor of five.  I need to be
clear that this solver does not conform to the original interface,
and probably most of speedup is due to choosing an interface that
gives an easier fit to the solver.

Sorry not to have something better for you.  It was a fair amount of
work to produce the results above.