Solve Einstein's problem with perl?!

Dear fellow monks,

being a novice I try to improve my skills by solving the following problem with perl. It is said to be invented by Albert Einstein who believed only 2 percent of the world population could solve it. He had no idea of perl or the monastery, of course ;^)

--8<--8<--snip--8<--8<--

So here's the task:

1. There are five houses with different colours.

2. In each of the houses there lives a member of a different nation.

3. Each one of these people likes a special drink and a special cigarrette best and has a special pet.

4. None of the 5 persons likes the same drink or cigarrete best or has the same pet as one of his neighbours.

Question:

To whom belongs the fish?

Hints:

The British lives in the red house.
The Swedish has a dog.
The Danish likes tea.
The green house is standing left of the white house.
The owner of the green house drinks coffee.
The person smoking Pall Mall, has a bird.
The man living in the middle house, drinks milk.
The owner of the yellow house smokes Dunhill.
The Norwegian lives in the first house.
The Marlboro-smoker's neighbour has a cat.
The man with the horse lives next to the Dunhill-smoker.
The Winfiels-smoker drinks beer.
The Norwegian lives beneath the blue house.
The German smokes Rothmanns.
The Marlboro-smoker has a neighbour who drinks water.

--8<--8<--snap--8<--8<--

I think of creating an array of five hashes (with the six keys: house_number, colour, drink, cigarette, pet, and nation). One could then fill out the known attributes and try to move the hashes around the array until each but one field is filled.

So far the thoughts of a poor brain ... Can anyone please tell me if this might be the right start and how to get on?

Having solved the problem by hand, there is another question: How comes, that the German doesn't drink beer? ;^) Thanks for your help!

weini

Comment on Solve Einstein's problem with perl?!

Replies are listed 'Best First'.
Re: Solve Einstein's problem with perl?! by Masem (Monsignor) on Feb 21, 2002 at 12:44 UTC
First, from the rec.puzzles FAQ that I maintain: ... A detailed explanation is available at http://www.frontiernet.net/~mwdaly/recpuzzles/einstein.html. For the record, Einstein didn't write the puzzle and far more than 2% of the world's population could solve it. As for your approach to solving it, it's certainly possible to permutate all possible combinations, then use perl version of the statements to remove solutions that can't work. However, technicially, I wouldn't call this 'solving' the riddle, since at some point you'd visit all 60^5 possible solutions (I believe that's the right number), and thus this is more like solving an NP problem by just trying every possibility, unlike using some heuristics to pick and choose. (Now, with rules based programming, it technicially still would have to be solved by the same methods of visiting every solution given the way rules programming is set up, but one can argue that the rules-based system is more efficient since it might find the solution before visiting all solutions.) ----------------------------------------------------- Dr. Michael K. Neylon - mneylon-pm@masemware.com \|\| "You've left the lens cap of your mind on again, Pinky" - The Brain "I can see my house from here!" It's not what you know, but knowing how to find it if you don't know that's important	[reply]
Re: Solve Einstein's problem with perl?! by clemburg (Curate) on Feb 21, 2002 at 15:26 UTC
Paradigms of Artificial Intelligence Programming has an excellent chapter 11 "Logic Programming" which uses a nearly identical problem (the "zebra puzzle") as example input for a prolog interpreter developed in the chapter. Christian Lemburg Brainbench MVP for Perl http://www.brainbench.com	[reply]
May be OT (Re: Solve Einstein's problem with perl?!) by arhuman (Vicar) on Feb 21, 2002 at 13:33 UTC
Sounds like a problem where PROLOG could shine... As far as I remember writing the data as predicate will be all you'll have to do, to let Prolog "find" the solution(s) thanx to unification and backtracking... IMHO, There are really few problems where PROLOG is the right tool, this one is one of them... (Maybe those modules could help) "Only Bad Coders Code Badly In Perl" (OBC2BIP)	[reply]
Re: May be OT (Re: Solve Einstein's problem with perl?!) by Anonymous Monk on Feb 22, 2002 at 00:14 UTC
I tried doing a similar puzzle with Prolog. Formulating it in Prolog took longer than for my wife to do it with graph paper. I suspect I could have done it with pencil and propositional calculus quicker; I had previously done another that way. The final constraint None of the 5 persons likes the same drink or cigarrete best or has the same pet as one of his neighbours. is both the most unrealisitic (wrto Real World) and the one that is hardest to express in Prolog or other LP paradigms. A reduction-based theorem-prover (as opposed to the unification based one that makes Prolog go) might have a better chance at meeting the rec.puzzles definition of "solving", as opposed to trying by exhaustion. -- Bill	[reply]
I think it's Lewis Carrol's puzzle by wrvhage (Sexton) on Feb 21, 2002 at 23:47 UTC
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	[reply]

Back to Meditations