Groups | Search | Server Info | Login | Register
Groups > comp.lang.c > #397363
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Cookies in boxes - algorithmic challenge |
| Date | 2026-04-02 20:13 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <10qmf5f$1bug5$1@dont-email.me> (permalink) |
| References | <20260401163447.000052de@yahoo.com> <10qk2e3$j5ho$3@dont-email.me> <10qm1pu$16u4j$1@dont-email.me> <10qm7go$194p8$1@dont-email.me> |
On 02/04/2026 18:03, DFS wrote:
> On 4/2/2026 11:25 AM, Mike Terry wrote:
>> On 01/04/2026 22:24, DFS wrote:
>>> On 4/1/2026 9:34 AM, Michael S wrote:
>>>
>>>> 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.
>>>
>>>
>>> I say it's impossible (or extremely, extremely rare) to accomplish that if you have to:
>>>
>>> 1) fill the boxes randomly, and
>>> 2) make only one random choice from each box
>>>
>>
>> I think you're misunderstanding the challenge.
>>
>> AIUI, you're /given/ the boxes, filled with cookies (randomly or otherwise) and your challenge is
>> to provide an algorithm to select 1 cookie from each box, such that one of each cookie type is
>> selected.
>>
>> The supplied code is some kind of test bench to check your solution. Your job is to supply the
>> missing solver() function so that the test bench program is successful. You do not need to fill
>> the boxes at all (they are supplied to you to solve), and you do not need to choose the cookies
>> you select randomly! (If you select randomly, you are highly likely to select two cookies of the
>> same type at some point, so you will fail...)
>
>
> This is a far better explanation than the original, but it's still confusing.
>
> Let me talk/think it through:
>
> Per Michael's original you have to choose exactly one cookie from each box, and end up with 20
> different types of cookie. That means each box contains at least one of the 20 cookie types (also
> could be 2+ of the same type). If I can't choose randomly, I would naively just evaluate each
> cookie in the box against what I've already chosen, grab one that hasn't been chosen, and move on to
> the next box.
>
> But I bet that by the 12th to 15th box, it won't have a cookie type that hasn't been chosen. So
> there's no way I could get to 20 cookie types with one selection from each box. I would have to
> start over, maybe begin with a different cookie type than I started with the first time, then hit
> the wall again, etc.
>
> Does that jibe with your understanding?
Yes, that's exactly the problem. You need to /search/ for a solution, which requires some kind of
search strategy. You won't be able to make a definitively correct choice at each decision point,
because that choice can affect the effective constraints way down the line as you explain. It might
turn out that the 1st choice you made seemed reasonable right at the start, but when you get to the
15th choice, nothing works. So you will need to back-track and try a different choice at one of
your decision points, and if that doesn't work maybe back-track even further, and so on.
(These types of problems are common - e.g. we have to fit various tiles or blocks to make a
particular shape, or a jigsaw where many pieces might match any particular edge pattern, but only a
small number of fully completed solutions exist. A typical approach is to make "guesses" that match
all constraints at the time the guess is made, and continue until it becomes clear no further
guesses can work, at which point go back a bit and try a different choice and so on...)
Some kind of recursive logic would be natural to give structure to the back-tracking, but the
devil's in the details to make the solver efficient. An alternative approach might be to just
choose randomly and see if it works, and if it doesn't, throw everything away and start from scratch
again - that's going to work /eventually/, but isn't going to satisfy the performance requirements!
>
> The code I wrote initially made sure each box contained at least one of the 20 types, then filled
> the rest randomly.
I think I know what you are trying to say, but your words have come out wrong - each box can /only/
contain cookies of the given types, so must obviously contains "at least one of the 20 types"! Hmm,
maybe you're thinking all boxes must contain one of /each/ of the 20 types? That's not right - it's
possible box1 contains only type1 cookies, box2 contains only type2 cookies and so on...
Anyhow, Michael says someone has proved that every possible assignment of the 400 given cookies to
boxes has a solution, so to create a starting puzzle you can just assign the 400 given cookies
randomly to boxes. (Perhaps start with the 400 cookies in a single line, then "shuffle" them, then
deal the first 20 to box1, the next 20 to box2, etc..)
> But then I made random choices. So I can go back and redo the code and NOT make
> random choices and see what happens.
>
> I see some sorting in my future.
>
> Thanks for the analysis.
>
> Did you try it?
>
I haven't tried to code a solution, but to be honest I probably have a dozen or so "similar type"
problems approached with C/C++ code, so I could maybe start with one of them to save some time that
way. (But I'm busy with other stuff at the moment.)
Here are some off the cuff thoughts:
1. Illustrations have showed a grid of cookie types, 20 columns (boxes) and 10 rows,
but lots of that data is redundant - we only really need to consider:
a) which boxes contain cookies for each cookie type (not how many of each type)
b) which cookie types appear in each box (again not how many of each type)
Also, there is no cookie order within any box...
So the first thing I'd do with a presented input is extract (a) and (b) and just
work with that.
2. There's a pleasing "symmetry" between boxes and cookie types.
E.g. you could decide to make "guesses" successively for each cookie-type
(guessing which box to take it from), or you could decide to guess successively
for the various box numbers (guessing which cookie type to take from it).
3. Both the cookie types AND the boxes, can become more or less "constrained"
as successive guesses are made. Probably a good strategy is to guess for
the most constrained cookie type /or/ box at each decision point. It's
not easy for me to explain exactly why I think that is best, but it seems
natural to me... E.g. if cookie-type-7 can be taken from 5 boxes, and
box4 contains only 3 cookie-types, then box4 is "more constrained" and
so my thinking would be to investigate what to take from box4 rather
than which box will I take a type-7 cookie from...
But... code working like that will probably be more fiddly to get right
and test etc.. (Normally I start with simple code, then start trying
to improve it if it's not "good enough" as it stands.)
Mike.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar
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