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 ==========