Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

I think it's Lewis Carrol's puzzle

by wrvhage (Sexton)
on Feb 21, 2002 at 23:47 UTC ( [id://146832]=note: print w/replies, xml ) Need Help??


in reply to Solve Einstein's problem with perl?!

Actually I think this is an isomorphism of Lewis Carroll's Zebra Puzzle.
You can read about the puzzle in Krzysztof Apt's lecture notes:
http://www.cwi.nl/~apt/constraints/notes1.ps
It starts at the bottom of page 8, which is really the 10th page if
you include the two title pages...

I solved this puzzle in two different ways in Prolog and Lisp.
In Prolog I chose to first specify all the constraints on the domains
of the five values, every constraint shrinking the domains and in the
end you're left with only one solution.
In Lisp I used streams to generate all permutations in a lazy way
and I filtered out all the possibilities that clashed with the rules
in the same way you'd sieve primes from the stream of integers.

The biggest choice I think is if you see the house number as a value
certain variables {colour, drink, pet, nationality, profession} can have
or if you see everything as a symbol and reason about things occurring
together or not.

I'm very curious to know how fast your Perl solution is.
I know it doesn't make much sense calling any numbers,
since there are too many variables, but my Prolog version took
0.004 seconds, using swi-prolog on a Sun Ultra 5 and I didn't time
the Lisp version. I'm just wondering if Perl will be in the same
order of magnitude.

I was also completely amazed that the Englishman doesn't drink tea
and that the Italian doesn't drink coffee, but I assumed that was just
to make things less obvious :)

Pasted in here is the Prolog version, as it's the most readable of the two:

% find the Zebra and the Water, zebra_water(X).
% by Willem Robert van Hage, wrvhage@science.uva.nl

right(2,1).
right(3,2).
right(4,3).
right(5,4).
nextdoor(X,Y) :- right(X,Y).
nextdoor(X,Y) :- right(Y,X).

match([],_).
match([X|Xs],Ys) :-
        member(X,Ys),
        match(Xs,Ys).

zebra_water(X) :-
        nextdoor(Horse,Diplomat),
        nextdoor(Fox,Doctor),
        nextdoor(Norwegian,Blue),
        Y = [house(    Green,          _,  green,         _,      _,      _),
             house(    White,          _,  white,         _,      _,      _),
             house(Norwegian,  norwegian,      _,         _,      _,      _),
             house(     Blue,          _,   blue,         _,      _,      _),
             house(      Fox,          _,      _,         _,    fox,      _),
             house(   Doctor,          _,      _,    doctor,      _,      _),
             house(    Horse,          _,      _,         _,  horse,      _),
             house( Diplomat,          _,      _,  diplomat,      _,      _),
             house(        3,          _,      _,         _,      _,   milk),
             house(        1,  norwegian,      _,         _,      _,      _),
             house(        _, englishman,    red,         _,      _,      _),
             house(        _,   spaniard,      _,         _,    dog,      _),
             house(        _,   japanese,      _,   painter,      _,      _),
             house(        _,    italian,      _,         _,      _,    tea),
             house(        _,          _, yellow,  diplomat,      _,      _),
             house(        _,          _,  green,         _,      _, coffee),
             house(        _,          _,      _,  sculptor, snails,      _),
             house(        _,          _,      _, violinist,      _,  juice),
             house(        _,          _,      _,         _,  zebra,      _),
             house(        _,          _,      _,         _,      _,  water) ],
        X = [ house(1,_,_,_,_,_),
              house(2,_,_,_,_,_),
              house(3,_,_,_,_,_),
              house(4,_,_,_,_,_),
              house(5,_,_,_,_,_) ],
        right(Green,White),
        match(Y,X).

It should come out nicely aligned when pasted into an ascii editor :)

brother Willem (wrvhage)
--
wrvh@xs4all.nl | http://wrvh.xs4all.nl

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://146832]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2024-03-29 12:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found