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;
[...]
On Mon, 2024-12-09 at 09:35 -0800, Tim Rentsch wrote:
wij <[email protected]> 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 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.
On Mon, 2024-12-09 at 22:15 -0800, Tim Rentsch wrote:
wij <[email protected]> writes:
On Mon, 2024-12-09 at 09:35 -0800, Tim Rentsch wrote:
wij <[email protected]> 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.
On 10/12/2024 10:23, wij wrote:
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).
On Tue, 10 Dec 2024 17:04:37 +0100
David Brown <[email protected]> wibbled:
On 10/12/2024 10:23, wij wrote:
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 found Prolog an absolute bugger of a language. Beyond simple clauses it never did what I expected it to do. Its the one language I never really
got. I think it requires a certain mindset or way of thinking.
On 10/12/2024 17:35, [email protected] wrote:
On Tue, 10 Dec 2024 17:04:37 +0100
David Brown <[email protected]> wibbled:
On 10/12/2024 10:23, wij wrote:
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 found Prolog an absolute bugger of a language. Beyond simple clauses it
never did what I expected it to do. Its the one language I never really
got. I think it requires a certain mindset or way of thinking.
Having only tried it for a short time as a teenager, it's not fair for
me to judge it - but it is certainly quite a different kind of language
from C++!
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 <[email protected]> writes:
On Mon, 2024-12-09 at 09:35 -0800, Tim Rentsch wrote:
wij <[email protected]> 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.
On Wed, 11 Dec 2024 08:59:18 +0100
David Brown <[email protected]> wibbled:
On 10/12/2024 17:35, [email protected] wrote:
On Tue, 10 Dec 2024 17:04:37 +0100
David Brown <[email protected]> wibbled:
On 10/12/2024 10:23, wij wrote:
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 found Prolog an absolute bugger of a language. Beyond simple clauses it >>> never did what I expected it to do. Its the one language I never really
got. I think it requires a certain mindset or way of thinking.
Having only tried it for a short time as a teenager, it's not fair for
me to judge it - but it is certainly quite a different kind of language >>from C++!
We had to use it in the AI module at uni. :/
I suspect its raison d'etre has rather been shot down these days as AI has moved away from propositional logic to neural networks.
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 <[email protected]> writes:
On Mon, 2024-12-09 at 09:35 -0800, Tim Rentsch wrote:
wij <[email protected]> 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
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).
and friends have been running "AI" since for example
the '80's at least since Moravec said "you know
we've had human-level AI for a while, ....".
It's moreso that various un-truths about the actual
implementations of AI offerings are designed to
reduce liability with regards to things like
"well it doesn't really think, and thus be
responsible for its actions, the dictates".
On 11.12.2024 10:40, [email protected] wrote:
We had to use it in the AI module at uni. :/
I suspect its raison d'etre has rather been shot down these days as AI has >> moved away from propositional logic to neural networks.
Some propositional logic would be very beneficial for the current
babble-GPT style AI. This is exactly what they are missing. Alas, this
would assume they understand a bit what they are babbling about, which
is not the case.
Given that even many people have huge problems with a), b) and d) I
would not hold my hopes high that all these things would somehow
randomly emerge.
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 <[email protected]> writes:
On Mon, 2024-12-09 at 09:35 -0800, Tim Rentsch wrote:
wij <[email protected]> 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.
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).
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.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 715 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 157:10:01 |
| Calls: | 12,093 |
| Calls today: | 1 |
| Files: | 15,000 |
| Messages: | 6,517,750 |