Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #121172 > unrolled thread

Is this program OOP?

Back to article view | Back to comp.lang.c++

Contents

  Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-09 20:08 +0800
    Re: Is this program OOP? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-09 09:35 -0800
      Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-10 06:35 +0800
        Re: Is this program OOP? Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-12-09 17:26 -0800
        Re: Is this program OOP? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-09 22:15 -0800
          Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-10 17:23 +0800
            Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-10 17:04 +0100
              Re: Is this program OOP? Muttley@DastardlyHQ.org - 2024-12-10 16:35 +0000
                Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-11 08:59 +0100
                  Re: Is this program OOP? Muttley@DastardlyHQ.org - 2024-12-11 08:40 +0000
                    Re: Is this program OOP? Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-12-11 09:41 -0800
                      Re: Is this program OOP? Muttley@DastardlyHQ.org - 2024-12-12 08:32 +0000
                        Re: Is this program OOP? Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-12-12 10:43 -0800
                          Re: Is this program OOP? Ross Finlayson <ross.a.finlayson@gmail.com> - 2024-12-12 17:28 -0800
                    Re: Is this program OOP? Paavo Helde <eesnimi@osa.pri.ee> - 2024-12-12 09:59 +0200
                      Re: Is this program OOP? Muttley@DastardlyHQ.org - 2024-12-12 08:37 +0000
              Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-11 01:02 +0800
                Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-11 12:42 +0100
                  Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-12 13:26 +0800
                    Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-12 08:59 +0100
                      Re: Is this program OOP? wij <wyniijj5@gmail.com> - 2024-12-14 16:22 +0800
                        Re: Is this program OOP? David Brown <david.brown@hesbynett.no> - 2024-12-15 10:45 +0100
                Re: Is this program OOP? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-12 08:00 -0800

Page 2 of 2 — ← Prev page 1 [2]

#121204

On Thu, 2024-12-12 at 08:59 +0100, David Brown wrote:
> On 12/12/2024 06:26, wij wrote:
> > On Wed, 2024-12-11 at 12:42 +0100, David Brown wrote:
> > > On 10/12/2024 18:02, wij wrote:
> > > > On Tue, 2024-12-10 at 17:04 +0100, David Brown wrote:
> > > > > On 10/12/2024 10:23, wij wrote:
> > > > > > On Mon, 2024-12-09 at 22:15 -0800, Tim Rentsch wrote:
> > > > > > > wij <wyniijj5@gmail.com> writes:
> > > > > > > 
> > > > > > > > On Mon, 2024-12-09 at 09:35 -0800, Tim Rentsch wrote:
> > > > > > > > 
> > > > > > > > > wij <wyniijj5@gmail.com> writes:
> > > > > > > > > 
> > > > > > > > > > Because I said:  C++ is the best language to model general
> > > > > > > > > > problems.  So it is.
> > > > > > > > > > 
> > > > > > > > > > Almost all are logical propositions.  Except those few keywords,
> > > > > > > > > > such programwon't be recognized as a C++ program, instead of some
> > > > > > > > > > kind of declarative language.
> > > > > > > > > > 
> > > > > > > > > > Zebra puzzle is an interesting programing exercise because it is
> > > > > > > > > > not too easy and also not too difficult.
> > > > > > > > > > 
> > > > > > > > > > ------------
> > > > > > > > > > /* Copyright is licensed by GNU LGPL, see file COPYING. by I.J.Wang 2023
> > > > > > > > > > 
> > > > > > > > > >     Example of solving the zebra puzzle by using propositional logic.
> > > > > > > > > >     Zebra Puzzle https://en.wikipedia.org/wiki/Zebra_Puzzle
> > > > > > > > > > 
> > > > > > > > > > [...]
> > > > > > > > > > */
> > > > > > > > > > #include <Wy.stdio.h>
> > > > > > > > > > #include <Sc/PropExpr.h>
> > > > > > > > > > 
> > > > > > > > > > using namespace Wy;
> > > > > > > > > > using namespace Sc;
> > > > > > > > > > 
> > > > > > > > > > [...]
> > > > > > > > > 
> > > > > > > > > You're asking a question that cannot be answered because much or
> > > > > > > > > most of the program is in the two include files, which are not
> > > > > > > > > shown.
> > > > > > > > > 
> > > > > > > > > As a general rule, when posting code there should be enough posted
> > > > > > > > > so that readers can at least compile it.  In cases like the program
> > > > > > > > > asked about here, what is posted should be enough to both compile
> > > > > > > > > the program and run the generated executable.
> > > > > > > > 
> > > > > > > > I thought nobody will be interested with the implement, and what
> > > > > > > > is shown should be enough for the moment.
> > > > > > > 
> > > > > > > The point is that what was posted is not enough to answer the
> > > > > > > question of the Subject: line.
> > > > > > > 
> > > > > > > > The Zebra Puzzle program has two version, a_puzzle_21.cpp (has
> > > > > > > > shown) takes too long to complete.  a_puzzle_2.cpp (736 lines, too
> > > > > > > > long to post, I thought) is the realistic one written in way I
> > > > > > > > feel just solving the prolem is enough.
> > > > > > > 
> > > > > > > I wrote a program in prolog to solve this puzzle.  The entire
> > > > > > > program is 60 lines long, including 13 blank lines.  It finds
> > > > > > > the solution in 0.03 seconds.  The program doesn't do anything
> > > > > > > fancy;  it pretty much just gives the listed conditions in the form
> > > > > > > of prolog rules, plus 20 lines to establish the structure of the
> > > > > > > information that is being sought.
> > > > > > 
> > > > > > Very dubious, show us what you say is true.
> > > > > > 
> > > > > 
> > > > > Prolog is a language that is ideally suited to such problems.
> > > > > Basically, you give the language a bunch of objects and facts and
> > > > > relations about those objects, then you ask it questions about them.
> > > > > It's at least 35 years since I tried Prolog one afternoon, and that's
> > > > > exactly the kind of task I played with (though a bit smaller).
> > > > 
> > > > I know a bit of prolog,lisp (in DOS era). Strongly suspicious what Tim says.
> > > > 
> > > > > This is not a big problem in any language.  It's 5 characteristics for
> > > > > each of 5 houses - that's 3125 possibilities.  Make a big array of
> > > > > booleans, initialised to true.  Run through the array and kill any
> > > > > combination that is contrary to one of the facts.  It might have been a
> > > > > worthy benchmark in 1962 but it should not be challenging to solve with
> > > > > modern machines.  (Of course it can still inspire interesting solutions
> > > > > and ways to express code in different languages.)
> > > > 
> > > > Not that simple, try it to know (your eye may fool you, just like with libwy).
> > > > 
> > > > a_puzzle_2.cpp (736 lines) was a random try in normal C++ programming
> > > > style. I did not try to optimize it. It took 3m22s.
> > > > a_puzzle_21.cpp has 178 lines, about 40 lines of comments, so 178-40=138 lines.
> > > > So, I have reason to doubt 60 lines of prolog can do the job. And most
> > > > importantly, the number of 0.03 seconds is too difficult to explain.
> > > > Prolog is not really a declarative language, you need to provide 'algorithm'
> > > > to 'compute' the answer. So, there is reason why 'prolog' program can run faster.
> > > > But, unless there is some built-in mechanism in modern prolog to solve
> > > > Zebra-puzzle-like problem, 60 lines of codes is dubious to me
> > > > and even so, 0.03 seconds remains highly dubious.
> > > > 
> > > 
> > > I just wrote a short Python program for the task.  Yes, it was a little
> > > more involved than I had suggested (though there was also no need to
> > > store an array of booleans).  I took all possible mixes for the house
> > > numbers, colours, etc. - that's 15625 sets and filtered out the ones
> > > that don't match the rules which did not involve neighbour-finding.
> > > Taking all the combinations there that pick one from each house, and
> > > there are 9810801 sets.  Eliminate sets where you don't have one of each
> > > nationality, one of each house colour, etc., then filter through the
> > > neighbour rules.  That gives one answer set.
> > 
> > (5^6)            = 156255
> > (5^6)*(4^6)      = 64000000
> > (5^6)*(4^6)*(3^6)= 46656000000
> > (5^6)*(4^6)*(3^6)*(2^6)= 2985984000000
> > 
> > 6-attr version simply has too many instances, so I changed to 5-attr version
> > 
> > (5^5)*(4^5)            = 3200000
> > (5^5)*(4^5)*(3^5)      = 777600000
> > (5^5)*(4^5)*(3^5)*(2^5)= 24883200000
> > 
> 
> There is a difference between "not optimising" and "thoughtlessly brute 
> force" !
> 
> Starting out, there are 5 ^ 5 sets for each house - 5 ^ 6 sets in all. 
> Apply rules 2, 3, 4, 5, 7, 8, 9, 10, 13 and 14 to filter these - that's 
> the rules that don't involve any kind of neighbour relationships.  That 
> gives you 21 possibilities for house 0, 13 possibilities for house 2, 
> and 33 possibilities for the other houses.  (Rules 9 and 10 reduce the 
> numbers for houses 2 and 0.)
> 
> 21 * 33 * 13 * 33 * 33 = 9810801
> 
> That's the search space for considering the "Latin square" requirement 
> (only one in each set from each nationality, with each pet, etc.).  That 
> gets you down to 2016 combinations.
> 
> Then filter through rules 6, 11, 12, 15 about neighbour relationships to 
> get one answer set.
> 
> Of course there are many other ways to organise this problem - in 
> particular, you can handle the constraints in different orders, or you 
> can divide the "build search space then filter out" in different ways (I 
> used two levels, as described).  Or you can view the search space as a 
> tree that you build up and prune as you go along.
> 
> You can even go for the most brute-force method of all - there are 5 ^ 5 
> combinations for each house, so you have (5 ^ 5) ^ 5 sets for all five 
> houses.  Check each of these 298023223876953125 sets against all the 
> rules, and see which one passes.
> 
> Your approach is a little less bad than that, but only a little.

"21 * 33 * 13 * 33 * 33 = 9810801" is a pretty much *optimized* solution.
Depending on the viewpoint (what kind of problem you want to solve), 
the puzzle solving algorithm can be from O(1) to O(2^N).

> > 
> > If my PC only runs the program like the t.cpp above, it will need 49.8s to
> > complete (below 49.8s is not possible, unless the program model is not
> > (5^5)*(4^5)*(3^5)*(2^5)).
> > 
> > With the 5-attr version (t_zebra2.cpp):
> > 
> > -----------------
> > []$ g++ t_zebra2.cpp -lwy -O2
> > []$ time ./a.out
> > (Yellow,Norwegian,Water,Kools,Fox)
> > (Blue,Ukrainian,Tea,Chesterfield,Horse)
> > (Red,Englishman,Milk,OldGold,Snail)
> > (Ivory,Spaniard,OrangeJuice,LuckyStrike,Dog)
> > (Green,Japanese,Coffee,Parliament,Zebra)
> > OK
> > 
> > real    4m1.683s
> > user    4m1.244s
> > sys     0m0.001s
> > 
> > > It was about 80 lines of Python (43 lines of code), and took 3.6 seconds
> > > to run (interpreted Python 3.10 - with pypy, it was about 1 second).
> > > There was no optimisation effort at all, with lots of use of list
> > > comprehensions, comparisons of strings, and so on - there's plenty of
> > > scope for writing it in a faster way.
> > 
> > I guess, 3.6s is the first solution found.
> 
> There is only one solution.  So yes, technically it /is/ the first 
> solution found - it is also the /last/ solution found.  (Had there been 
> more than one solution, they'd all have come out.)
> 
> > 
> > > Do I believe that a decently written program in a language that is
> > > dedicated to such tasks could be a hundred times as fast as interpreted
> > > Python?  I think it is not entirely unrealistic.  (And I expect that a
> > > carefully written C++ program would be too fast to measure on a single
> > > run - especially if you through in vector instructions.)
> > 
> > Nothing absolutely bad with interpreted language. If properly supported
> > and used, Python should be better than C++ (conditional).
> > 
> 
> This example demonstrates that a slow interpreted language with a good 
> algorithm soundly beating a fast compiled language with a bad algorithm. 
>   (And my algorithm was far from optimal, and the implementation of it 
> in Python was also far from optimal.)
> 
> 
> Now I just need to translate my code into C++ :-)

So far from I know, using C++ to beat those numbers you provided from Python 
is no trivial task. I estimate the limit is 0.08s (on my PC's speed) if nothing
significantly changed.

[toc] | [prev] | [next] | [standalone]

#121205

On 14/12/2024 09:22, wij wrote:
> On Thu, 2024-12-12 at 08:59 +0100, David Brown wrote:

> "21 * 33 * 13 * 33 * 33 = 9810801" is a pretty much *optimized* solution.
> Depending on the viewpoint (what kind of problem you want to solve),
> the puzzle solving algorithm can be from O(1) to O(2^N).
> 

"Optimised" would mean, as I see it, as fast as possible within 
reasonably practical limits.  (And of course it would be unreasonable to 
simply pre-calculate the answer.)  For a problem like this, there are 
three kinds of optimisations - algorithmic, choice of language or 
compute platform, and optimisation of the implementation itself.

I have done none of these, so IMHO my solution is far from optimal.  All 
I did was split the problem into two parts based on a simple criteria. 
To me, the split was so obvious that I do not see it as something 
special - but perhaps it is one of these things that seems obvious once 
you have thought of it.

Algorithmic optimisation would involve dividing the problem into more 
parts, probably using a search tree and stack structure of some kind but 
ensuring that it is all allocated and handled with as little dynamic 
allocation as possible.

Language and compute platform choice optimisation would certainly result 
in something other than single-threaded Python.  It might mean Prolog, 
it might mean C++.  Maybe this can be done on a GPU in CUDA - I don't 
know such platforms well.  Certainly it would aim to be multi-threaded 
(at least, for a similar style of problem that is large enough to 
justify the overheads).  And a key consideration would be cache friendly 
structures.

And I didn't bother doing any kind of implementation optimisation at 
all.  There is probably scope for increasing speed by a factor of 5 or 
so in straightforward Python, more from the use of numpy.  But there's a 
lot more possibility in C++.


>>
>> Now I just need to translate my code into C++ :-)
> 
> So far from I know, using C++ to beat those numbers you provided from Python
> is no trivial task. I estimate the limit is 0.08s (on my PC's speed) if nothing
> significantly changed.
> 

I don't think it should be hard to do a lot better than the Python code 
from a fairly direct translation of the Python - lists to std::vector<>, 
and so on.  Translating into more optimal C++ code would lead to a huge 
improvement in speed.  I would not expect the results to be measurable 
with the "time" command without looping the algorithm many times.

[toc] | [prev] | [next] | [standalone]

#121199

wij <wyniijj5@gmail.com> writes:

> On Tue, 2024-12-10 at 17:04 +0100, David Brown wrote:
>
>> On 10/12/2024 10:23, wij wrote:
>>
>>> On Mon, 2024-12-09 at 22:15 -0800, Tim Rentsch wrote:
>>>
>>>> wij <wyniijj5@gmail.com> writes:
>>>>
>>>>> On Mon, 2024-12-09 at 09:35 -0800, Tim Rentsch wrote:
>>>>>
>>>>>> wij <wyniijj5@gmail.com> writes:
>>>>>>
>>>>>>> Because I said:  C++ is the best language to model general
>>>>>>> problems.  So it is.
>>>>>>>
>>>>>>> Almost all are logical propositions.  Except those few
>>>>>>> keywords, such programwon't be recognized as a C++ program,
>>>>>>> instead of some kind of declarative language.
>>>>>>>
>>>>>>> Zebra puzzle is an interesting programing exercise because it
>>>>>>> is not too easy and also not too difficult.
>>>>>>>
>>>>>>> ------------
>>>>>>> /* Copyright is licensed by GNU LGPL, see file COPYING. by
>>>>>>> I.J.Wang 2023
>>>>>>>
>>>>>>> Example of solving the zebra puzzle by using propositional logic.
>>>>>>> Zebra Puzzle https://en.wikipedia.org/wiki/Zebra_Puzzle
>>>>>>>
>>>>>>> [...]
>>>>>>> */
>>>>>>> #include <Wy.stdio.h>
>>>>>>> #include <Sc/PropExpr.h>
>>>>>>>
>>>>>>> using namespace Wy;
>>>>>>> using namespace Sc;
>>>>>>>
>>>>>>> [...]
>>>>>>
>>>>>> You're asking a question that cannot be answered because much
>>>>>> or most of the program is in the two include files, which are
>>>>>> not shown.
>>>>>>
>>>>>> As a general rule, when posting code there should be enough
>>>>>> posted so that readers can at least compile it.  In cases like
>>>>>> the program asked about here, what is posted should be enough
>>>>>> to both compile the program and run the generated executable.
>>>>>
>>>>> I thought nobody will be interested with the implement, and what
>>>>> is shown should be enough for the moment.
>>>>
>>>> The point is that what was posted is not enough to answer the
>>>> question of the Subject: line.
>>>>
>>>>> The Zebra Puzzle program has two version, a_puzzle_21.cpp (has
>>>>> shown) takes too long to complete.  a_puzzle_2.cpp (736 lines,
>>>>> too long to post, I thought) is the realistic one written in way
>>>>> I feel just solving the prolem is enough.
>>>>
>>>> I wrote a program in prolog to solve this puzzle.  The entire
>>>> program is 60 lines long, including 13 blank lines.  It finds the
>>>> solution in 0.03 seconds.  The program doesn't do anything fancy;
>>>> it pretty much just gives the listed conditions in the form of
>>>> prolog rules, plus 20 lines to establish the structure of the
>>>> information that is being sought.
>>>
>>> Very dubious, show us what you say is true.
>>
>> Prolog is a language that is ideally suited to such problems.
>> Basically, you give the language a bunch of objects and facts and
>> relations about those objects, then you ask it questions about
>> them.  It's at least 35 years since I tried Prolog one afternoon,
>> and that's exactly the kind of task I played with (though a bit
>> smaller).
>
> I know a bit of prolog,lisp (in DOS era).  Strongly suspicious what
> Tim says.
>
>> This is not a big problem in any language.  It's 5 characteristics
>> for each of 5 houses - that's 3125 possibilities.  Make a big array
>> of booleans, initialised to true.  Run through the array and kill
>> any combination that is contrary to one of the facts.  It might
>> have been a worthy benchmark in 1962 but it should not be
>> challenging to solve with modern machines.  (Of course it can still
>> inspire interesting solutions and ways to express code in different
>> languages.)
>
> Not that simple, try it to know (your eye may fool you, just like
> with libwy).
>
> a_puzzle_2.cpp (736 lines) was a random try in normal C++
> programming style.  I did not try to optimize it.  It took 3m22s.
> a_puzzle_21.cpp has 178 lines, about 40 lines of comments, so
> 178-40=138 lines.  So, I have reason to doubt 60 lines of prolog
> can do the job.  And most importantly, the number of 0.03 seconds
> is too difficult to explain.  Prolog is not really a declarative
> language, you need to provide 'algorithm' to 'compute' the answer.
> So, there is reason why 'prolog' program can run faster.  But,
> unless there is some built-in mechanism in modernprolog to solve
> Zebra-puzzle-like problem, 60 lines of codes is dubious to me and
> even so, 0.03 seconds remains highly dubious.

I'm wondering what it is you are dubious about.  Are you dubious

 (a) that I know how to use the 'wc' program to see how many
     lines there are in a file?

 (b) that I know how to use awk, and pipe the results into wc,
     to see how many blank lines there are in a file?

 (c) that I am capable of writing a prolog program that can be
     accepted and run by the swipl prolog interpreter?

 (d) that I know how to run a prolog program contained in a file,
     and look at the output it produces?

 (e) that I am capable of checking the output against the problem
     specification, to be sure the purported solution satisifies
     the conditions of the problem?

 (f) that I know how to use 'time' in a linux/unix shell, to see
     how long it took to run a program?

 (g) that I know how to interpret the output of 'time', and map
     it onto a time as measured by a regular time-keeping device
     such as a stopwatch?

Or is that you just think I'm a liar?

Incidentally I cleaned up the program a bit, and now it is only 50
lines long, including 13 blank lines.  It doesn't run any faster
than it did before;  still taking about 0.03 seconds of user time,
and about 0.04 seconds real time (that includes the time taken by a
short shell script wrapper to prettify the output).

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c++

csiph-web