Deutsch English Français Italiano |
<64393d96ff8cc12e274038abda13ac54eacadfed.camel@gmail.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: news.eternal-september.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: wij <wyniijj5@gmail.com> Newsgroups: comp.lang.c++ Subject: Re: Is this program OOP? Date: Thu, 12 Dec 2024 13:26:13 +0800 Organization: A noiseless patient Spider Lines: 215 Message-ID: <64393d96ff8cc12e274038abda13ac54eacadfed.camel@gmail.com> References: <63cd41709a703e4ac6d76427d53fe06d7ee8b8b1.camel@gmail.com> <86plm0iwtj.fsf@linuxsc.com> <035b9e2186f9dc6467806e27a76d98525c104e54.camel@gmail.com> <86h67chxn8.fsf@linuxsc.com> <03fcd46b8d44390c78ca1719e2311b528570d276.camel@gmail.com> <vj9oql$114ip$1@dont-email.me> <fb4cdf9c1c99986b84c6f598858efe1a9473cd26.camel@gmail.com> <vjbtr5$1h44t$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Date: Thu, 12 Dec 2024 06:26:15 +0100 (CET) Injection-Info: dont-email.me; posting-host="873b505833b0f249bb4de2bcd173ffe6"; logging-data="2076574"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18KOZ+NBEyc/Q4afJx2oIWq" User-Agent: Evolution 3.50.2 (3.50.2-1.fc39) Cancel-Lock: sha1:ghcJ6zsxYALliWZIVwSQyX2H0aY= In-Reply-To: <vjbtr5$1h44t$1@dont-email.me> 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: > > > > >=20 > > > > > > On Mon, 2024-12-09 at 09:35 -0800, Tim Rentsch wrote: > > > > > >=20 > > > > > > > wij <wyniijj5@gmail.com> writes: > > > > > > >=20 > > > > > > > > Because I said:=C2=A0 C++ is the best language to model gen= eral > > > > > > > > problems.=C2=A0 So it is. > > > > > > > >=20 > > > > > > > > Almost all are logical propositions.=C2=A0 Except those few= keywords, > > > > > > > > such programwon't be recognized as a C++ program, instead o= f some > > > > > > > > kind of declarative language. > > > > > > > >=20 > > > > > > > > Zebra puzzle is an interesting programing exercise because = it is > > > > > > > > not too easy and also not too difficult. > > > > > > > >=20 > > > > > > > > ------------ > > > > > > > > /* Copyright is licensed by GNU LGPL, see file COPYING. by = I.J.Wang 2023 > > > > > > > >=20 > > > > > > > > =C2=A0=C2=A0=C2=A0Example of solving the zebra puzzle by us= ing propositional logic. > > > > > > > > =C2=A0=C2=A0=C2=A0Zebra Puzzle https://en.wikipedia.org/wik= i/Zebra_Puzzle > > > > > > > >=20 > > > > > > > > [...] > > > > > > > > */ > > > > > > > > #include <Wy.stdio.h> > > > > > > > > #include <Sc/PropExpr.h> > > > > > > > >=20 > > > > > > > > using namespace Wy; > > > > > > > > using namespace Sc; > > > > > > > >=20 > > > > > > > > [...] > > > > > > >=20 > > > > > > > You're asking a question that cannot be answered because much= or > > > > > > > most of the program is in the two include files, which are no= t > > > > > > > shown. > > > > > > >=20 > > > > > > > As a general rule, when posting code there should be enough p= osted > > > > > > > so that readers can at least compile it.=C2=A0 In cases like = the program > > > > > > > asked about here, what is posted should be enough to both com= pile > > > > > > > the program and run the generated executable. > > > > > >=20 > > > > > > I thought nobody will be interested with the implement, and wha= t > > > > > > is shown should be enough for the moment. > > > > >=20 > > > > > The point is that what was posted is not enough to answer the > > > > > question of the Subject: line. > > > > >=20 > > > > > > The Zebra Puzzle program has two version, a_puzzle_21.cpp (has > > > > > > shown) takes too long to complete.=C2=A0 a_puzzle_2.cpp (736 li= nes, too > > > > > > long to post, I thought) is the realistic one written in way I > > > > > > feel just solving the prolem is enough. > > > > >=20 > > > > > I wrote a program in prolog to solve this puzzle.=C2=A0 The entir= e > > > > > program is 60 lines long, including 13 blank lines.=C2=A0 It find= s > > > > > the solution in 0.03 seconds.=C2=A0 The program doesn't do anythi= ng > > > > > fancy;=C2=A0 it pretty much just gives the listed conditions in t= he form > > > > > of prolog rules, plus 20 lines to establish the structure of the > > > > > information that is being sought. > > > >=20 > > > > Very dubious, show us what you say is true. > > > >=20 > > >=20 > > > 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). > >=20 > > I know a bit of prolog,lisp (in DOS era). Strongly suspicious what Tim = says. > >=20 > > > This is not a big problem in any language.=C2=A0 It's 5 characteristi= cs for > > > each of 5 houses - that's 3125 possibilities.=C2=A0 Make a big array = of > > > booleans, initialised to true.=C2=A0 Run through the array and kill a= ny > > > combination that is contrary to one of the facts.=C2=A0 It might have= been a > > > worthy benchmark in 1962 but it should not be challenging to solve wi= th > > > modern machines.=C2=A0 (Of course it can still inspire interesting so= lutions > > > and ways to express code in different languages.) > >=20 > > Not that simple, try it to know (your eye may fool you, just like with = libwy). > >=20 > > 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=3D= 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 'algor= ithm' > > to 'compute' the answer. So, there is reason why 'prolog' program can r= un faster. > > But, unless there is some built-in mechanism in modern=C2=A0prolog to s= olve > > Zebra-puzzle-like problem, 60 lines of codes is dubious to me > > and even so, 0.03 seconds remains highly dubious. > >=20 >=20 > I just wrote a short Python program for the task.=C2=A0 Yes, it was a lit= tle=20 > more involved than I had suggested (though there was also no need to=20 > store an array of booleans).=C2=A0 I took all possible mixes for the hous= e=20 > numbers, colours, etc. - that's 15625 sets and filtered out the ones=20 > that don't match the rules which did not involve neighbour-finding.=20 > Taking all the combinations there that pick one from each house, and=20 > there are 9810801 sets.=C2=A0 Eliminate sets where you don't have one of = each=20 > nationality, one of each house colour, etc., then filter through the=20 > neighbour rules.=C2=A0 That gives one answer set. (5^6) =3D 156255 (5^6)*(4^6) =3D 64000000 (5^6)*(4^6)*(3^6)=3D 46656000000 (5^6)*(4^6)*(3^6)*(2^6)=3D 2985984000000 6-attr version simply has too many instances, so I changed to 5-attr versio= n (5^5)*(4^5) =3D 3200000 (5^5)*(4^5)*(3^5) =3D 777600000 (5^5)*(4^5)*(3^5)*(2^5)=3D 24883200000 ----------- t.cpp (for estimation) int main() { long long a=3D3; for(long long i=3D0; i<1000000000L; ++i) { // loop 10^9 a+=3D3; } return 0; }; []$ g++ t.cpp []$ time ./a.out eal 0m2.164s user 0m2.154s sys 0m0.005s ----------------- (3200000/1000000000)*2s =3D 0.0064s (777600000/1000000000)*2s =3D 1.555s (24883200000/1000000000)*2s=3D 49.766s If my PC only runs the program like the t.cpp above, it will need 49.8s to= ========== REMAINDER OF ARTICLE TRUNCATED ==========