Hi,
I am new to lisp and Im trying to solve a riddle a friend gave me
using lisp. Here is the problem: I have a bunch of clues and I have to
examine all of the clues to solve the riddle. The clues are things like:
There are 5 houses.
Each house has a person of different nationality.
Each house has a person that drinks a different drink.
Each house has a person who owns a different pet.
The person who drinks milk lives in the middle house.
The Norwegian lives in the first house.
The Englishman drinks beer.
The guy who drinks coffee lives in the red house.
The green house is next to the white house.
The Norwegian lives to the left of the blue house.
The German lives next to the yellow house.
The Swede is 2 houses from the guy who drinks water
The guy in the green house drinks coffe.
Where does the American live?
What you have to do is construct all of the houses, and when you are done
one house will only be defined as having a drink and color, everyone else will
have a drink, color, and nationality. The house missing the nationality is
the house where the American lives because every house has a different
nationality, drink, and color.
However, how do I do something like this in Lisp. Im not asking for
complete code, but just a basic algorithm or something to help me out.
The solution:
Norwegian German ------ Swede Englishman
Coffee Water Milk Tea Beer
Red Blue Yellow Green White
Therefore the American lives in the middle house.
Thanks a lot for any advice
-Bill Koscho
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Klaus Schilling
Subject: Re: Help solving a puzzle...
Date:
Message-ID: <87k91m2eiv.fsf@ivm.de>
·······@syncsort.com writes:
> There are 5 houses.
> Each house has a person of different nationality.
> Each house has a person that drinks a different drink.
> Each house has a person who owns a different pet.
> The person who drinks milk lives in the middle house.
> The Norwegian lives in the first house.
> The Englishman drinks beer.
> The guy who drinks coffee lives in the red house.
> The green house is next to the white house.
> The Norwegian lives to the left of the blue house.
> The German lives next to the yellow house.
> The Swede is 2 houses from the guy who drinks water
> The guy in the green house drinks coffe.
>
> Where does the American live?
>
> The solution:
>
> Norwegian German ------ Swede Englishman
> Coffee Water Milk Tea Beer
> Red Blue Yellow Green White
>
Tea is nowhere mentioned above, how does it come into play?
Klaus Schilling
Bill Koscho wrote:
> I am new to lisp and Im trying to solve a riddle a friend gave me
> using lisp.
You're quite sure "a friend" doesn't mean "the person teaching
this class I'm taking"? (If it doesn't, I'm sorry I asked; but
this group does get a lot of people asking for help with their
homework, who often try to lie about why they want help. Alas.)
> Here is the problem: I have a bunch of clues and I have to
> examine all of the clues to solve the riddle. The clues are things like:
>
> There are 5 houses.
> Each house has a person of different nationality.
> Each house has a person that drinks a different drink.
> Each house has a person who owns a different pet.
> The person who drinks milk lives in the middle house.
> The Norwegian lives in the first house.
> The Englishman drinks beer.
> The guy who drinks coffee lives in the red house.
> The green house is next to the white house.
> The Norwegian lives to the left of the blue house.
> The German lives next to the yellow house.
> The Swede is 2 houses from the guy who drinks water
> The guy in the green house drinks coffe.
>
> Where does the American live?
>
> What you have to do is construct all of the houses, and when you are
> done one house will only be defined as having a drink and color,
> everyone else will have a drink, color, and nationality. The house
> missing the nationality is the house where the American lives
> because every house has a different nationality, drink, and color.
>
> However, how do I do something like this in Lisp. Im not asking for
> complete code, but just a basic algorithm or something to help me out.
>
> The solution:
>
> Norwegian German ------ Swede Englishman
> Coffee Water Milk Tea Beer
> Red Blue Yellow Green White
This solution is not consistent with the problem you have
described.
> Therefore the American lives in the middle house.
Interesting that you're being asked to do this in Lisp,
because this exact same problem (no, I'm wrong: not the
exact same problem, because the original problem actually
mentions the pets pointlessly referred to in the statement
of the problem you describe) can be found in one of
the more famous textbooks on (other things and) Lisp,
where it's presented as an example of how to make good
use of ... Prolog!
One approach you could take is constraint propagation.
In other words: you try to fill in the 15 pieces of
information in your table above, considering one slot
at a time and seeing what values for it are consistent
with the facts you know (considered only one at a time).
The first time you do this, the only thing you'll discover
is that milk is drunk in the middle house. Having done that,
you choose one of the slots you haven't filled yet and
try in turn each of the possible values. For each possible
value you make a recursive call to your solving routine,
which will apply all the rules again and see what comes out.
This will not be very efficient.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
From: Klaus Schilling
Subject: Re: Help solving a puzzle...
Date:
Message-ID: <87d87d3lb8.fsf@ivm.de>
Gareth McCaughan <·····@dpmms.cam.ac.uk> writes:
> Bill Koscho wrote:
>
> > I am new to lisp and Im trying to solve a riddle a friend gave me
> > using lisp.
>
> You're quite sure "a friend" doesn't mean "the person teaching
> this class I'm taking"? (If it doesn't, I'm sorry I asked; but
> this group does get a lot of people asking for help with their
> homework, who often try to lie about why they want help. Alas.)
When I saw something the like first, it was a riddle in a journal for normal
people that had nothing at all to do with computation and programming. It was
with 5 cars in a parking lots, different brands, colors, and cities.
>
> > Here is the problem: I have a bunch of clues and I have to
> > examine all of the clues to solve the riddle. The clues are things like:
> >
> > There are 5 houses.
> > Each house has a person of different nationality.
> > Each house has a person that drinks a different drink.
> > Each house has a person who owns a different pet.
> > The person who drinks milk lives in the middle house.
> > The Norwegian lives in the first house.
> > The Englishman drinks beer.
> > The guy who drinks coffee lives in the red house.
> > The green house is next to the white house.
> > The Norwegian lives to the left of the blue house.
> > The German lives next to the yellow house.
> > The Swede is 2 houses from the guy who drinks water
> > The guy in the green house drinks coffe.
> >
> > Where does the American live?
> >
> > What you have to do is construct all of the houses, and when you are
> > done one house will only be defined as having a drink and color,
> > everyone else will have a drink, color, and nationality. The house
> > missing the nationality is the house where the American lives
> > because every house has a different nationality, drink, and color.
> >
> > However, how do I do something like this in Lisp. Im not asking for
> > complete code, but just a basic algorithm or something to help me out.
> >
> > The solution:
> >
> > Norwegian German ------ Swede Englishman
> > Coffee Water Milk Tea Beer
> > Red Blue Yellow Green White
>
> This solution is not consistent with the problem you have
> described.
>
(((and fairly unconsistant with rl , but that's prolly besides the point :)))
> > Therefore the American lives in the middle house.
>
> Interesting that you're being asked to do this in Lisp,
> because this exact same problem (no, I'm wrong: not the
> exact same problem, because the original problem actually
> mentions the pets pointlessly referred to in the statement
> of the problem you describe) can be found in one of
> the more famous textbooks on (other things and) Lisp,
> where it's presented as an example of how to make good
> use of ... Prolog!
>
I also thought that prolog might be the most natural language for solving
logical riddles.
Is there also an easy way to construct riddles of that sort computationally,
i.e. having a solution table and generating a random complete, independant
and consistant set of relations? That might make quiz book publishers happy.
Klaus Schilling
On 27 Oct 1998 19:35:07 +0100, Klaus Schilling
<···············@home.ivm.de> claimed or asked:
% Is there also an easy way to construct riddles of that sort computationally,
% i.e. having a solution table and generating a random complete, independant
% and consistant set of relations? That might make quiz book publishers happy.
I believe crossword puzzles are constructed that way.
In "Dirk Gently's Holistic Detective Agency", Douglas Adams talked of
a program called "reason" that made one of the characters extremely
rich. Say you wanted to buy a Porsche (this is paraphrased from the
book). You entered this into the program. The program would then
work out why you needed a Porsche and how you would pay for it.
--
David Steuber (ver 1.31.2a)
http://www.david-steuber.com
To reply by e-mail, replace trashcan with david.
"Ignore reality there's nothing you can do about it..."
-- Natalie Imbruglia "Don't you think?"
Klaus Schilling wrote:
> Is there also an easy way to construct riddles of that sort computationally,
> i.e. having a solution table and generating a random complete, independant
> and consistant set of relations? That might make quiz book publishers happy.
I don't know. I'd approach the problem incrementally: start with
the empty set of constraints and the knowledge that all "solutions"
are possible; then repeatedly add a constraint (using some kind
of heuristic to try to eliminate as many possibilities as you
can, but obviously also a random element) and do some constraint
propagation. Keep going until you get either no solution at all
(when you can either backtrack or give up and start again), or
get a unique solution. Or maybe until you get, say, <= 5 solutions,
and then print them all out and let a human come up with a clever
last constraint.
It seems to me that it should be possible.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
·······@syncsort.com wrote in message <············@nnrp1.dejanews.com>...
>The solution:
>
> Norwegian German ------ Swede Englishman
> Coffee Water Milk Tea Beer
> Red Blue Yellow Green White
>
Another possibility if ya have the computer horse power to do it is>>>
[see the thread about permutation in lisp earlier in this new group]
1. the houses are esoteric positions in the list...position 1 is house 1
etc
2. use one of the permutation functions from the above thread to build all
possible
permuation of beverage, color, nationality
3. ya need a robust pattern matcher. there are a number in literature.
the one we use
is a very enhanced version of the one in _common lispcraft_ by robert
wilensky. To
our patterner matcher MA respresents "match any or none" and X is a
place holder.
4. facts or represented a list as follows
;;; person who drinks milk lives in middle house
(beverage X X milk X X) ;matcher returns lists of beverage with beer in
mid-position
;;; norwegin lives in first house
(nationality norw X X X X) ;matcher returns lists of nationality in 1st
position
;;; green house is next to white house
(color MA green white MA) ;returns list of color with green next to, any
position
;;; english drinks beer
((beverage MA beer MA)
(nationalit MA engl MA)) ; matcher returns list of beverage and
nationality where
; beer and english in above
and below configuration
....etc
....etc
swede is 2 houses from the guy who drinks water
((beverage X X water X X) ;;matcher returns list of beverag with
water in mid-
(or (nationality swed X X MA);;and nationality matching this pattern
(nationality MA X X swed)))
....
After all the matches are ran what is left is the possiblities. in some of
the problems we use this for, a number of possiblites are left....but that
is what we are after. The matcher we have written is consider proprietary,
thus I can not share the code for it. In fact it is fairly unremarkable and
any of these clever folks could write it (and problably have) in very little
time. The motto of our hospital informatics is "LACK OF PROGRAMMING SKILLS
CAN BE OVER COME BY MORE COMPUTER POWER"
we call this algorithm EBF (exhasutive brute force) it takes a lot of
compture horse power if the problem is less than trivial.
looking for more ram and faster cycles
rusty
rusty craine wrote:
[snip]
> ... The motto of our hospital informatics is "LACK OF PROGRAMMING SKILLS
> CAN BE OVER COME BY MORE COMPUTER POWER"
lol! Is that an original or taken from the "MS Book of Programming
Secrets"?
Sorry for being off topic but I am seriously tempted to change my
signature :)
ciske
--
-------------------------------------------------------------------
"Real stupidity beats artificial intelligence every time."
M.Ridcully
Ciske Busch
Lehrstuhl fuer Kuenstliche Intelligenz und Angewandte Informatik
Universitaet Wuerzburg, Germany
http://ki-server.informatik.uni-wuerzburg.de/~ciske/
ICQ: #12558072
-------------------------------------------------------------------