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

Groups > comp.lang.c++ > #121192

Re: Is this program OOP?

Show all headers | View raw

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

----------- t.cpp (for estimation)
int main()
{
 long long a=3;
 for(long long i=0; i<1000000000L; ++i) { // loop 10^9
   a+=3;
 }
 return 0;
};

[]$ g++ t.cpp
[]$ time ./a.out

eal     0m2.164s
user    0m2.154s
sys     0m0.005s
-----------------
(3200000/1000000000)*2s    = 0.0064s
(777600000/1000000000)*2s  = 1.555s
(24883200000/1000000000)*2s= 49.766s

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.

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

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web