Path: news.eternal-september.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: David Brown <david.brown@hesbynett.no>
Newsgroups: comp.lang.c++
Subject: Re: Is this program OOP?
Date: Wed, 11 Dec 2024 12:42:28 +0100
Organization: A noiseless patient Spider
Lines: 119
Message-ID: <vjbtr5$1h44t$1@dont-email.me>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 11 Dec 2024 12:42:29 +0100 (CET)
Injection-Info: dont-email.me; posting-host="2219d0e81fc8abda50710a06e8939fe0";
	logging-data="1609885"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/DasgfuHlgOli16O/U3U0peQx7a0BtYpI="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.11.0
Cancel-Lock: sha1:WEzrjKXUbWj50HaB9/OKW5OObwg=
Content-Language: en-GB
In-Reply-To: <fb4cdf9c1c99986b84c6f598858efe1a9473cd26.camel@gmail.com>

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.

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.

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