Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #397345 > unrolled thread
| Started by | Michael S <already5chosen@yahoo.com> |
|---|---|
| First post | 2026-04-01 16:34 +0300 |
| Last post | 2026-04-17 20:17 +0200 |
| Articles | 20 on this page of 78 — 10 participants |
Back to article view | Back to comp.lang.c
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
Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-02 22:24 +0300 |
| Message-ID | <20260402222458.00000897@yahoo.com> |
| In reply to | #397361 |
On Thu, 2 Apr 2026 19:50:06 +0100 Bart <bc@freeuk.com> wrote: > 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? > > > > The code I wrote initially made sure each box contained at least > > one of the 20 types, then filled the rest randomly. > > Hang on, if each box is guaranteed to contain at least one of any > cookie you're looking for, then it can make it trivial. > > At least, with my poor algorithm, it would always work, since it > starts by looking for a type A in box 1, box B in box 2, and so on. > > It would go wrong if it got to type F say, and that is only present > in boxes already picked. Here I start redoing some earlier choices, > which is where it can go wrong. > > Seems like you are trying to solve by exhausting. If you read my original post, you'd see that I suggest against it and give an explanation why it is not a good idea.
[toc] | [prev] | [next] | [standalone]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2026-04-02 20:13 +0100 |
| Message-ID | <10qmf5f$1bug5$1@dont-email.me> |
| In reply to | #397359 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-02 22:36 +0300 |
| Message-ID | <20260402223600.00006107@yahoo.com> |
| In reply to | #397363 |
On Thu, 2 Apr 2026 20:13:50 +0100 Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote: > 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. > Interesting thing about that problem is that while it looks NP-complete at the 1st glance, it turns out dramatically simpler than that. My current solution is O(N*N*M). I would not be surprised if there exist solutions with even lower computational complexity than that.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-02 22:14 +0300 |
| Message-ID | <20260402221413.000058e2@yahoo.com> |
| In reply to | #397357 |
On Thu, 2 Apr 2026 16:25:49 +0100 Mike Terry <news.dead.person.stones@darjeeling.plus.com> 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...) > > > Mike. > Correct. I hoped that it was very clear, but some people are much better at misunderstanding than I can imagine.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-02 22:10 +0300 |
| Message-ID | <20260402221052.000015d9@yahoo.com> |
| In reply to | #397355 |
On Wed, 1 Apr 2026 17:24:19 -0400
DFS <nospam@dfs.com> 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 can't understand your code, but it seems like you do a LOT more
> than just 1 and 2.
>
>
> Given those 2 constraints and using rand(), I saw a range of 9 to 16
> (out of 20), with a typical score of 11-12.
>
> Score = 1 point for each unique flavor you randomly choose. If you
> choose a flavor from box 2 that you already chose from box 1, you get
> 0 points.
>
> Here's that code:
>
>
> //public domain code
>
> #include <stdlib.h>
> #include <stdio.h>
> #include <string.h>
> #include <time.h>
>
>
> int main(void) {
>
> //----------------------------------------------------------------------------
> //fill a box of 20 sections with 10 cookies each, from 20
> random //cookie flavors - duplicate flavors allowed in each section
> //----------------------------------------------------------------------------
>
> //big beautiful box
> int *box = malloc(200 * sizeof(int));
>
> //randomly fill the box - this means all flavors might not be
> used srand(time(NULL));
> for (int i = 0; i < 200; i += 10) {
> for (int j = 0; j <= 9; j++) {
> int r = (rand() % 19) + 1;
> box[i+j] = r;
> }
> }
>
>
> //print contents of box column by row
> printf("----------------------------------------------------------------------------------------------------------\n");
> printf(" Random flavors in each box -
> duplicate flavors allowed\n ");
> for (int i = 1; i <= 9; i++) {printf("%d ", i);}
> for (int i = 10; i <= 20; i++) {printf("%d ", i);}
> printf("\n----------------------------------------------------------------------------------------------------------\n");
> int rows = 10, cols = 20, colwidth = 5;
> for (int r = 1; r <= rows; r++) {
> if (r <= 200) {
> int nbr = r-1;
> printf("%3d %-*c", r, colwidth, box[nbr]
> + 65); for (int i = 0; i < cols-1; i++) {
> nbr += rows;
> if (nbr <= 200) {
> printf("%-*c", colwidth,
> box[nbr] + 65); }
> }
> printf("\n");
> }
> }
> printf("----------------------------------------------------------------------------------------------------------\n");
>
>
> //chose a random flavor, if it hasn't been used add it to the
> chosen array char chosen[150] = {0};
> char randoms[150] = {0};
> char theflavor[8], therandom[8];
> int chosencnt = 0;
> for (int i = 0; i < 200; i+=10) {
> int start = i; int end = i + 9;
> int r = (rand() % (end - start + 1)) + start;
> sprintf(theflavor," %c ", box[r] + 65);
> strncat(randoms , theflavor, strlen(theflavor));
> if (strstr(chosen, theflavor) == NULL) {
> strncat(chosen , theflavor,
> strlen(theflavor)); chosencnt++;
> }
> }
>
> printf("Random: %s\n", randoms);
> printf("Chosen: %s\n", chosen);
> printf("Score : %d\n", chosencnt);
>
> free(box);
> return 0;
> }
>
>
I'l look at your solution not before it is implemented according to
my spec: as a module solver.c that implements function solver() as
declared in solver.h and linkable with tb.c.
tb.c is provided for you to use for testing your solution. Don't waste
time writing your own main().
[toc] | [prev] | [next] | [standalone]
| From | Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> |
|---|---|
| Date | 2026-04-06 22:36 +0100 |
| Message-ID | <10r190u$2d47m$1@dont-email.me> |
| In reply to | #397362 |
On 02/04/2026 20:10, Michael S wrote: > I'l look at your solution not before it is implemented according to > my spec: as a module solver.c that implements function solver() as > declared in solver.h and linkable with tb.c. Isn't it called a translation unit, rather than a module? Do we say "declared" for functions in C? I thought it was called "prototyped." -- Tristan Wibberley The message body is Copyright (C) 2026 Tristan Wibberley except citations and quotations noted. All Rights Reserved except that you may, of course, cite it academically giving credit to me, distribute it verbatim as part of a usenet system or its archives, and use it to promote my greatness and general superiority without misrepresentation of my opinions other than my opinion of my greatness and general superiority which you _may_ misrepresent. You definitely MAY NOT train any production AI system with it but you may train experimental AI that will only be used for evaluation of the AI methods it implements.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-06 15:42 -0700 |
| Message-ID | <86zf3fyam9.fsf@linuxsc.com> |
| In reply to | #397393 |
Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> writes: > On 02/04/2026 20:10, Michael S wrote: > >> I'l look at your solution not before it is implemented according to >> my spec: as a module solver.c that implements function solver() as >> declared in solver.h and linkable with tb.c. > > Isn't it called a translation unit, rather than a module? Right. > Do we say "declared" for functions in C? I thought it was called > "prototyped." In C, a function can be declared (or even defined) without having a prototype. I think that might change (IMO a change for the worse) in C23, but before C23 a function declaration doesn't have to include a prototype. Personally I am not inclined to use "prototyped" as a verb in that way. The C standard talks about "a type that includes a prototype" or "a type that does not include a prototype", and normally I think I would use that phrasing, or a similar one. Note that prototypes can appear without necessarily being associated with any function, as for example in a typedef or a cast.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2026-04-06 15:44 -0700 |
| Message-ID | <87y0iz3e0i.fsf@example.invalid> |
| In reply to | #397393 |
Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk>
writes:
> On 02/04/2026 20:10, Michael S wrote:
>> I'l look at your solution not before it is implemented according to
>> my spec: as a module solver.c that implements function solver() as
>> declared in solver.h and linkable with tb.c.
>
> Isn't it called a translation unit, rather than a module?
Yes. The C standard doesn't define anything called "modules".
A translation unit consists of a source file and all the headers
and source files it #includes.
There's nothing necessarily wrong with referring to "modules" as a
way to talk about program organization, but it's helpful to define
what you mean by the term.
> Do we say "declared" for functions in C? I thought it was called
> "prototyped."
Functions can be declared and/or defined. A definition provides a
declaration. A prototype is a declaration that specifies the types
of any parameters; the alternative is an old-style declaration.
Old-style function declarations and definitions are no longer
supported in C23.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2026-04-04 13:33 -0400 |
| Message-ID | <10qri1m$s330$1@dont-email.me> |
| In reply to | #397345 |
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.
> Smart math heads proved that for any distribution a solution exists.
//public domain code
//this 'brute force' algorithm tries to choose 20 unique types of
cookies from 20 boxes of 10 cookies each
//almost always get 18 19 or 20
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
//print contents of box - by row then column
void print_row_by_col(int box[]) {
int b = 1;
for (int i = 0; i < 200; i += 10) {
for (int j = 0; j < 10; j++) {
printf("%2d %c\n",b, box[i+j] +65);
}
b++;
}
}
//print contents of box column by row
void print_col_by_row(int box[], char *hdr) {
printf(" Boxes (%s)\n",hdr);
printf("Cookie
--------------------------------------------------------------------------------------------------\n");
printf(" Nbr ");
for (int i = 1; i <= 9; i++) {printf("%d ", i);}
for (int i = 10; i <= 20; i++) {printf("%d ", i);}
printf("\n----------------------------------------------------------------------------------------------------------\n");
int rows = 10, cols = 20, colwidth = 5;
for (int r = 1; r <= rows; r++) {
if (r <= 200) {
int nbr = r-1;
printf("%3d %-*c", r, colwidth, box[nbr] + 65);
for (int i = 0; i < cols-1; i++) {
nbr += rows;
if (nbr <= 200) {
printf("%-*c", colwidth, box[nbr] + 65);
}
}
printf("\n");
}
}
printf("----------------------------------------------------------------------------------------------------------\n\n");
}
//sort box by section then cookie type (not used)
//for (int i = 0; i < 200; i += 10) {
// qsort(box + i, 10, sizeof(box[0]), compare2ints);
//}
int compare2ints(const void *a, const void *b) {
const int *intA = (const int *)a;
const int *intB = (const int *)b;
if (intA[0] != intB[0]) {
return intA[0] - intB[0];
}
return intA[1] - intB[1];
}
int main(void) {
//----------------------------------------------------------------------------
//fill a box of 20 sections with 10 cookies each, from 20 random
//cookie flavors - duplicate flavors allowed in each section
//----------------------------------------------------------------------------
//big beautiful box
int *box = malloc(200 * sizeof(int));
//assign -33 to show blanks later
for (int i = 0; i < 200; i++) {box[i] = -33;} //to show blank later
//ensure all types are used at least once
//assign one of each cookie type to a unique random box, and to a
//random position within the box
srand(time(NULL));
char usedlist[75] = {0};
char therandom[5];
int j = 0;
for (int i = 0; i < 200; i ++) {
int r = rand() % 20; //random box
sprintf(therandom," %d ", r);
if (strstr(usedlist, therandom) == NULL) {
if (j < 20) {
int s = rand() % 10; //random position in the box
box[(r * 10) + s] = j++;
strncat(usedlist, therandom, strlen(therandom));
}
if (j == 20) {break;}
}
}
//print contents of box column by row
//note: at this point in the code this will blanks and one cookie type
per box
print_col_by_row(box,"random successful path");
//randomly fill in the remaining 9 cookie types in each section
for (int i = 0; i < 200; i += 10) {
for (int j = 0; j < 10; j++) {
int r = rand() % 20;
if (box[i+j] == -33) {
box[i+j] = r;
}
}
}
//print contents of filled box - column by row
print_col_by_row(box,"random fill");
//search algorithm
char usedcookies[600] = {0};
char usedboxes[62] = {0};
char solution[62] = {0};
int *usedboxesarr = malloc(20 * sizeof(int));
int *solutionarr = malloc(10 * sizeof(int));
char thecookie[4], thebox[4];
int matches = 0;
clock_t starttime, endtime;
starttime = clock(); //CPU timing
for (int j = 0; j < 10; j++) {
matches = 0;
sprintf(thecookie, " %c ", box[j] + 65);
sprintf(thebox , " %d ", (j/10) + 1);
strcat(usedcookies, thecookie);
strcat(solution, thecookie);
strcat(usedboxes, thebox);
solutionarr[matches] = box[j];
usedboxesarr[matches] = (j/10) + 1;
matches++;
for (int i = 10; i < 200; i++) {
sprintf(thecookie, " %c ", box[i] + 65);
sprintf(thebox , " %d ", (i/10) + 1);
if (strstr(usedcookies, thecookie) == NULL && strstr(usedboxes,
thebox) == NULL) {
strcat(usedcookies, thecookie);
strcat(solution, thecookie);
strcat(usedboxes, thebox);
solutionarr[matches] = box[i];
usedboxesarr[matches] = (i/10) + 1;
matches++;
}
}
if (matches == 20) {break;}
memset(usedcookies, 0, sizeof(usedcookies));
memset(usedboxes, 0, sizeof(usedboxes));
memset(solution, 0, sizeof(solution));
memset(solutionarr, 0, sizeof(solutionarr));
memset(usedboxesarr, 0, sizeof(usedboxesarr));
}
endtime = clock();
//# of choices (20 = success = a different type from 20 boxes)
printf("Matches: %d\n", matches);
//print boxes used
printf("Box :");
for (int i = 0; i < matches; i++) {printf("%3d ",usedboxesarr[i]);}
//print cookie types used
printf("\nType:");
for (int i = 0; i < matches; i++) {printf("%3c ",solutionarr[i] + 65);}
printf("\nCPU time = %.5fs\n\n",((double)(endtime - starttime)) /
CLOCKS_PER_SEC);
free(box);
return 0;
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-04 21:03 +0300 |
| Message-ID | <20260404210345.0000704a@yahoo.com> |
| In reply to | #397372 |
On Sat, 4 Apr 2026 13:33:44 -0400 DFS <nospam@dfs.com> wrote: At first, you didn't understand the rules. That's o.k. Bart is pretty smart, but he didn't understand too. Let's call it my fault. But then 3 different people explained it to you. Despite that you still didn't get it. It's no longer my fault.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2026-04-04 14:19 -0400 |
| Message-ID | <10qrkmj$s330$4@dont-email.me> |
| In reply to | #397374 |
On 4/4/2026 2:03 PM, Michael S wrote: > On Sat, 4 Apr 2026 13:33:44 -0400 > DFS <nospam@dfs.com> wrote: > > At first, you didn't understand the rules. That's o.k. > Bart is pretty smart, but he didn't understand too. > Let's call it my fault. > But then 3 different people explained it to you. Despite that you still > didn't get it. > It's no longer my fault. I got it right after Mike Terry explained it. It's a hard CS challenge, and I just don't know how to "implement function solver() in module solver.c" But my brute force algorithm does get 20 matches about 1/4th of the time, in as little as .00002s. Only 20picks/20types 100% of the time is a success, so I'll keep working at it. If you run my code you might like what it does.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2026-04-04 20:22 +0100 |
| Message-ID | <10qrodb$tvm9$1@dont-email.me> |
| In reply to | #397374 |
On 04/04/2026 19:03, Michael S wrote: > On Sat, 4 Apr 2026 13:33:44 -0400 > DFS <nospam@dfs.com> wrote: > > At first, you didn't understand the rules. That's o.k. > Bart is pretty smart, but he didn't understand too. > Let's call it my fault. Advent of Code challenges are very well explained. They also provide a small-scale example, showing inputs, and expected outputs. I don't know how the difficulty of this compares with those; I've never had enough patience to get past the first couple of days, and they apparently got harder. (I might yet get back to it, but I'm not working on it now. Even with the O(N*N*M) hint you posted, which tells me all the approaches I can think of are probably wrong.)
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-04 22:40 +0300 |
| Message-ID | <20260404224038.0000745b@yahoo.com> |
| In reply to | #397376 |
On Sat, 4 Apr 2026 20:22:19 +0100 Bart <bc@freeuk.com> wrote: > On 04/04/2026 19:03, Michael S wrote: > > On Sat, 4 Apr 2026 13:33:44 -0400 > > DFS <nospam@dfs.com> wrote: > > > > At first, you didn't understand the rules. That's o.k. > > Bart is pretty smart, but he didn't understand too. > > Let's call it my fault. > > Advent of Code challenges are very well explained. > > They also provide a small-scale example, showing inputs, and expected > outputs. > > I don't know how the difficulty of this compares with those; I've > never had enough patience to get past the first couple of days, and > they apparently got harder. > I don't follow code challenges systematically. I remember one posted here few years ago named Euler413. I think that my challenge is simpler than that, but not a lot simpler. > (I might yet get back to it, but I'm not working on it now. Even with > the O(N*N*M) hint you posted, which tells me all the approaches I can > think of are probably wrong.) > I suppose that you tried heuristic based schemes. I can not tell that they are necessarily wrong. Personally, I was not able to find working heuristics, but it does not mean that one do not exists.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-04 17:08 -0700 |
| Message-ID | <86wlymz2t9.fsf@linuxsc.com> |
| In reply to | #397345 |
Michael S <already5chosen@yahoo.com> writes: > 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. [...] Thank you for that. > So, here is the challenge: I looked at the problem, and have written enough code now to satisfy myself that I know how to solve it. Not ready to post yet; among other things there are some other clc posts I've been meaning to respond to, and I really should try to do those first. I plan on not looking at anyone else's code before I have something ready to say myself.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-08 08:42 -0700 |
| Message-ID | <86tstlwjak.fsf@linuxsc.com> |
| In reply to | #397345 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-08 22:23 +0300 |
| Message-ID | <20260408222330.00005cf8@yahoo.com> |
| In reply to | #397424 |
On Wed, 08 Apr 2026 08:42:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> 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 ...
>
What were the problems?
My gcc 14.2.0 on msys2 produces no warnings or errors with above flags.
> 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.
>
Yes, I should have explained it, at least briefly.
I'd guess that you expected that values in result vector correspond to
sorts of cookies, when in fact they are indices to position of the
cookie in the box.
I am sorry.
> 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.
>
My defaults were chosen for much slower solutions.
For fast solutions like yours or mine with default parameters an
overhead of clock_gettime() call is too significant.
In such case it's better to use rep1 of at least 10000.
> 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.
>
It's not something I'd expect.
I used "by value" type of interface both for input and for output in
order to reduce a chance of buggy solutions to mess with the test bench.
I fully expect that "by reference" type of interface could be somewhat
faster. May be, 1.5x faster for very fast solutions. But I certainly
don't expect a factor of five.
> Sorry not to have something better for you. It was a fair amount of
> work to produce the results above.
I read your code briefly, but didn't try to understand it yet.
I plugged it into my test bench and measured speed on very old home PC
(Intel i5-3450). With big values of rep1 it was ~3.3 times faster
than my original solution and ~1.9 times slower than my 2nd solution.
So, speed-wise your solution is good.
One thing that I don't particularly like after taking a glance - it
does not appear to be thread-safe. But it is probably very easy to make
it thread safe.
Another thing that I don't particularly like - if we want N_BOXES > 32
then it requires modifications; if we want N_BOXES > 64 then it
requires more serious modifications.
Now few words about my own solutions.
1. Original solution:
This solution is based on the proof that was given to me by somebody
with abstract math mind.
2. It is solution that I found independently, for which I hopefully
have a proof in the head, but I didn't write it out yet and didn't show
yet to said mathematician. It would not surprise me if idea of these
solution is the same as yours.
Later today (tonight) I plan to post both solutions here.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-09 21:22 -0700 |
| Message-ID | <865x5zbg10.fsf@linuxsc.com> |
| In reply to | #397427 |
Michael S <already5chosen@yahoo.com> writes:
> On Wed, 08 Apr 2026 08:42:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> 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 ...
>
> What were the problems?
> My gcc 14.2.0 on msys2 produces no warnings or errors with above flags.
These source lines
struct timespec t0;
clock_gettime(CLOCK_MONOTONIC, &t0);
produced these diagnostics
tb.c:134:21: error: storage size of 't0' isn't known
tb.c:135:5: warning: implicit declaration of function 'clock_gettime' [...]
tb.c:135:19: error: 'CLOCK_MONOTONIC' undeclared (first use in this function)
under -std=c99. Apparently the first diagnostic, about
struct timespec, is fixed under -std=c11. It wasn't hard
to fix these, but it was irksome.
>> 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.
>
> Yes, I should have explained it, at least briefly.
> I'd guess that you expected that values in result vector correspond to
> sorts of cookies, when in fact they are indices to position of the
> cookie in the box.
> I am sorry.
Yes, that is in fact what I was thinking. Fortunately the difficulty
was resolved when the checker reported a value out of range.
>> 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.
>
> My defaults were chosen for much slower solutions.
> For fast solutions like yours or mine with default parameters an
> overhead of clock_gettime() call is too significant.
> In such case it's better to use rep1 of at least 10000.
It turns out that running with a larger number of trials didn't
change the results much. I think my averages got a bit worse and my
worst case got a bit better, but as I recall the difference wasn't
anything dramatic.
>> 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.
>
> It's not something I'd expect.
> I used "by value" type of interface both for input and for output in
> order to reduce a chance of buggy solutions to mess with the test bench.
> I fully expect that "by reference" type of interface could be somewhat
> faster. May be, 1.5x faster for very fast solutions. But I certainly
> don't expect a factor of five.
I will try to explain below.
>> Sorry not to have something better for you. It was a fair amount of
>> work to produce the results above.
>
> I read your code briefly, but didn't try to understand it yet.
I need to say again that the code I posted was not code that I wrote.
The approach used is similar to code I did write, but the actual code
is quite a bit different.
> I plugged it into my test bench and measured speed on very old home PC
> (Intel i5-3450). With big values of rep1 it was ~3.3 times faster
> than my original solution and ~1.9 times slower than my 2nd solution.
> So, speed-wise your solution is good.
> One thing that I don't particularly like after taking a glance - it
> does not appear to be thread-safe. But it is probably very easy to make
> it thread safe.
Do you mean because it is using (and changing) global objects? Yes
that is a drawback.
> Another thing that I don't particularly like - if we want N_BOXES > 32
> then it requires modifications; if we want N_BOXES > 64 then it
> requires more serious modifications.
As it turns out my code handles N_BOXES up to 52. You may laugh
when you see why.
> Now few words about my own solutions.
> 1. Original solution:
> This solution is based on the proof that was given to me by somebody
> with abstract math mind.
Yes, I posted a comment about that
> 2. It is solution that I found independently, for which I hopefully
> have a proof in the head, but I didn't write it out yet and didn't show
> yet to said mathematician. It would not surprise me if idea of these
> solution is the same as yours.
I don't really understand that code yet, but it looks like your
code is a bit fancier than mine (the code that wasn't posted
because it uses a different interface).
> Later today (tonight) I plan to post both solutions here.
Here is an outline of the first (non-interface-compatible) code that
I wrote.
Use a straightforward backtracking scheme. Make a choice at the
current level, and do a recursive call to try the next level. If
the next level returns, it failed, so go on to the next choice at
this level and call again.
The output value is an array (passed recursively via pointer) with
either a cookie type for each box or a box number for each cookie
type (I don't remember which). This array is filled in as the
recursive backtrack progresses.
The whole search is started by doing a setjmp() before the call to
the top level. If the search succeeds, a longjmp() is done to
deliver an answer. That means that if the call to the top level
returns then the search was a failure. The central recursive
function has four parameters:
an Answer *'out', to hold the solution
a jmp_buf 'found', for a longjmp() when a full answer is found
a counter/index to reflect search depth (starting 0, 20 means done)
a "solution state" to direct the search (conceptually by value)
The "solution state" is at the heart of the algorithm. It's a
structure holding an array of 20 "cookie values", where a cookie
value is represented by an unsigned 64-bit int. The bits are
used as follows:
low six bits: the cookie type
next 52 bits: a "box mask", indicating at least one cookie of
this type in the corresponding box (so up to 52
boxes)
upper bits: count of boxes (ie, number of ones in the box mask)
The cookie type is important when storing a partial result in the
answer, not at any other time.
The box mask is important to know which boxes to try during the
backtracking.
The count of boxes is important to help guide the backtracking, in a
way that we hope will get an answer faster.
At each level of recursion, do the following:
If the search depth is the number of boxes, longjmp()
Next find the cookie of cookies in the solution state at or
above this level that has the smallest number of boxes. Because
the box count is held in the uppermost bits the 64-bit values can
simply be directly compared, without any masking. Move that
cookie to the array location corresponding to the current depth
(and put the cookie that was there in the hole left by doing the
move).
For each box in the box mask of that cookie, try selecting that
box for this cookie, which means:
copy the state of cookies above this level to a new solution
state, so the changed solution state described above can be
left alone
for each of those cookies, if the cookie has the "selected box"
set in its box mask, clear the bit and reduce the box count
by one. (again since the box count is held in high order bits
this count can be reduced by just subtracting a scaled one
value.)
recurse to continue searching at the next level
If we run out of boxes to check, just return; continue trying
alternatives at the next level up, if there is one.
I think that's it. I hope it makes sense.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-10 12:23 +0300 |
| Message-ID | <20260410122314.000063c5@yahoo.com> |
| In reply to | #397461 |
On Thu, 09 Apr 2026 21:22:51 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 08 Apr 2026 08:42:11 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> 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 ...
> >
> > What were the problems?
> > My gcc 14.2.0 on msys2 produces no warnings or errors with above
> > flags.
>
> These source lines
>
> struct timespec t0;
> clock_gettime(CLOCK_MONOTONIC, &t0);
>
> produced these diagnostics
>
> tb.c:134:21: error: storage size of 't0' isn't known
> tb.c:135:5: warning: implicit declaration of function
> 'clock_gettime' [...] tb.c:135:19: error: 'CLOCK_MONOTONIC'
> undeclared (first use in this function)
>
> under -std=c99. Apparently the first diagnostic, about
> struct timespec, is fixed under -std=c11. It wasn't hard
> to fix these, but it was irksome.
>
Sounds like under Linux and with -std=c99 flag function clock_gettime()
and related structures and constants are not declared/defined by default
in time.h.
Man page suggests magic pixie dust:
#define _XOPEN_SOURCE 600
#include <time.h>
#include <unistd.h>
If you ask why I used clock_gettime() instead of C standard
timespec_get() then the answer is that on Windows, eps. on older
versions like Win7 and WS2008 (which I prefer over newer stuff for
reasons unrelated to quality of C RTL), precision of timespec_get() is
poor. clock_gettime(CLOCK_MONOTONIC,) is much better.
> >> 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.
> >
> > Yes, I should have explained it, at least briefly.
> > I'd guess that you expected that values in result vector correspond
> > to sorts of cookies, when in fact they are indices to position of
> > the cookie in the box.
> > I am sorry.
>
> Yes, that is in fact what I was thinking. Fortunately the difficulty
> was resolved when the checker reported a value out of range.
>
> >> 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.
> >
> > My defaults were chosen for much slower solutions.
> > For fast solutions like yours or mine with default parameters an
> > overhead of clock_gettime() call is too significant.
> > In such case it's better to use rep1 of at least 10000.
>
> It turns out that running with a larger number of trials didn't
> change the results much. I think my averages got a bit worse and my
> worst case got a bit better, but as I recall the difference wasn't
> anything dramatic.
>
After testing on another (Windows) systems I have to admit that my
objections about default value of rep1 applies only to Win7. Even on
Ws2008, which is almost the same kernel, overhead of clock_gettime() is
sufficiently low for rep1=128 to give fair measurements.
> >> 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.
> >
> > It's not something I'd expect.
> > I used "by value" type of interface both for input and for output in
> > order to reduce a chance of buggy solutions to mess with the test
> > bench. I fully expect that "by reference" type of interface could
> > be somewhat faster. May be, 1.5x faster for very fast solutions.
> > But I certainly don't expect a factor of five.
>
> I will try to explain below.
>
> >> Sorry not to have something better for you. It was a fair amount
> >> of work to produce the results above.
> >
> > I read your code briefly, but didn't try to understand it yet.
>
> I need to say again that the code I posted was not code that I wrote.
> The approach used is similar to code I did write, but the actual code
> is quite a bit different.
>
> > I plugged it into my test bench and measured speed on very old home
> > PC (Intel i5-3450). With big values of rep1 it was ~3.3 times
> > faster than my original solution and ~1.9 times slower than my 2nd
> > solution. So, speed-wise your solution is good.
> > One thing that I don't particularly like after taking a glance - it
> > does not appear to be thread-safe. But it is probably very easy to
> > make it thread safe.
>
> Do you mean because it is using (and changing) global objects? Yes
> that is a drawback.
>
Yes.
> > Another thing that I don't particularly like - if we want N_BOXES >
> > 32 then it requires modifications; if we want N_BOXES > 64 then it
> > requires more serious modifications.
>
> As it turns out my code handles N_BOXES up to 52. You may laugh
> when you see why.
>
> > Now few words about my own solutions.
> > 1. Original solution:
> > This solution is based on the proof that was given to me by somebody
> > with abstract math mind.
>
> Yes, I posted a comment about that
>
<snip the rest, will respond later >
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-04-10 22:41 -0700 |
| Message-ID | <861pgmawaz.fsf@linuxsc.com> |
| In reply to | #397463 |
Michael S <already5chosen@yahoo.com> writes:
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>> Michael S <already5chosen@yahoo.com> writes:
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
[...]
>>>> 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 ...
>>>
>>> What were the problems?
>>> My gcc 14.2.0 on msys2 produces no warnings or errors with above
>>> flags.
>>
>> These source lines
>>
>> struct timespec t0;
>> clock_gettime(CLOCK_MONOTONIC, &t0);
>>
>> produced these diagnostics
>>
>> tb.c:134:21: error: storage size of 't0' isn't known
>> tb.c:135:5: warning: implicit declaration of function
>> 'clock_gettime' [...] tb.c:135:19: error: 'CLOCK_MONOTONIC'
>> undeclared (first use in this function)
>>
>> under -std=c99. Apparently the first diagnostic, about
>> struct timespec, is fixed under -std=c11. It wasn't hard
>> to fix these, but it was irksome.
>
> Sounds like under Linux and with -std=c99 flag function clock_gettime()
> and related structures and constants are not declared/defined by default
> in time.h.
Yes, gcc follows the ISO standard exactly, and does not define
symbols like clock_gettime, because the C standard does not
allow conforming impementations to do so.
> Man page suggests magic pixie dust:
>
> #define _XOPEN_SOURCE 600
> #include <time.h>
> #include <unistd.h>
It is my practice not to mix ISO-conformant and non-ISO-conformant
code in the same translation unit. It wasn't hard to find the
necessary tweak for a separate source file used to get the
current time:
#define _POSIX_C_SOURCE 199309L
#include <time.h>
after which both the 'struct timespec' and 'clock_gettime()' were
quite okay. I packaged the time in a way so it could get across
the function call interface and back to the main program.
> If you ask why I used clock_gettime() instead of C standard
> timespec_get() then the answer is that on Windows, eps. on older
> versions like Win7 and WS2008 (which I prefer over newer stuff for
> reasons unrelated to quality of C RTL), precision of timespec_get() is
> poor. clock_gettime(CLOCK_MONOTONIC,) is much better.
Makes sense.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2026-04-10 16:16 +0300 |
| Message-ID | <20260410161638.00007745@yahoo.com> |
| In reply to | #397461 |
On Thu, 09 Apr 2026 21:22:51 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Wed, 08 Apr 2026 08:42:11 -0700 > > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > > > >> Michael S <already5chosen@yahoo.com> writes: > >> <snip, answered in the other post> > As it turns out my code handles N_BOXES up to 52. You may laugh > when you see why. > The number of small+capital letters in English alphabet? Probably, not. Indeed, after reading the rest, it's not that. > > Now few words about my own solutions. > > 1. Original solution: > > This solution is based on the proof that was given to me by somebody > > with abstract math mind. > > Yes, I posted a comment about that > > > 2. It is solution that I found independently, for which I hopefully > > have a proof in the head, but I didn't write it out yet and didn't > > show yet to said mathematician. It would not surprise me if idea > > of these solution is the same as yours. > > I don't really understand that code yet, but it looks like your > code is a bit fancier than mine (the code that wasn't posted > because it uses a different interface). > > > Later today (tonight) I plan to post both solutions here. > > Here is an outline of the first (non-interface-compatible) code that > I wrote. > > Use a straightforward backtracking scheme. Make a choice at the > current level, and do a recursive call to try the next level. If > the next level returns, it failed, so go on to the next choice at > this level and call again. > > The output value is an array (passed recursively via pointer) with > either a cookie type for each box or a box number for each cookie > type (I don't remember which). This array is filled in as the > recursive backtrack progresses. > > The whole search is started by doing a setjmp() before the call to > the top level. If the search succeeds, a longjmp() is done to > deliver an answer. That means that if the call to the top level > returns then the search was a failure. The central recursive > function has four parameters: > > an Answer *'out', to hold the solution > a jmp_buf 'found', for a longjmp() when a full answer is found > a counter/index to reflect search depth (starting 0, 20 means done) > a "solution state" to direct the search (conceptually by value) > > The "solution state" is at the heart of the algorithm. It's a > structure holding an array of 20 "cookie values", where a cookie > value is represented by an unsigned 64-bit int. The bits are > used as follows: > > low six bits: the cookie type > next 52 bits: a "box mask", indicating at least one cookie of > this type in the corresponding box (so up to 52 > boxes) > upper bits: count of boxes (ie, number of ones in the box mask) > > The cookie type is important when storing a partial result in the > answer, not at any other time. > > The box mask is important to know which boxes to try during the > backtracking. > > The count of boxes is important to help guide the backtracking, in a > way that we hope will get an answer faster. > > At each level of recursion, do the following: > > If the search depth is the number of boxes, longjmp() > > Next find the cookie of cookies in the solution state at or > above this level that has the smallest number of boxes. Because > the box count is held in the uppermost bits the 64-bit values can > simply be directly compared, without any masking. Is it proven that this step helps? To me it sounds unnecessary. > Move that > cookie to the array location corresponding to the current depth > (and put the cookie that was there in the hole left by doing the > move). > > For each box in the box mask of that cookie, try selecting that > box for this cookie, which means: > > copy the state of cookies above this level to a new solution > state, so the changed solution state described above can be > left alone > > for each of those cookies, if the cookie has the "selected box" > set in its box mask, clear the bit and reduce the box count > by one. (again since the box count is held in high order bits > this count can be reduced by just subtracting a scaled one > value.) > > recurse to continue searching at the next level > > If we run out of boxes to check, just return; continue trying > alternatives at the next level up, if there is one. > > I think that's it. I hope it makes sense. It makes sense, but it looks to me as solution by exhausting, augmented by "smallest number of boxes" heuristic. It's not obvious [to me] without further thinking that the worst case is not very slow.
[toc] | [prev] | [next] | [standalone]
Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →
Back to top | Article view | comp.lang.c
csiph-web