mro wrote:
> Here's one for you all. Print it out and take some time for mind crunching
> fun. Admittedly, it took me quite some time to figure out.
>
> There are 5 houses in five different colors. In each house lives a person
> with a different nationality. These five owners drink a certain drink, smoke
> a certain brand of cigar, and keep a certain pet. No owners have the same
> pet, smoke the same brand of cigar or drink the same drink. The question is
> --- who owns the fish?
>
> Hints:
> - the Brit lives in the red house
> - the Swede keeps dogs as pets
> - the Dane drinks tea
> - the green house is on the left of the white house
> - the green house owner drinks coffee
> - the person who smokes Pall Mal rears birds
> - the owner of the yellow house smokes Dunhill
> - the man living in the house right in the center drinks milk
> - the Norwegian lives in the first house
> - the man who smokes Blends lives next to the one who keeps cats
> - the man who keeps horses lives next to the one who smokes Dunhill
> - the owner who smokes Blue Master drinks beer
> - the German smokes Prince
> - the Norwegian lives next to the blue house
> - the man who smokes Blend has a neighbor who drinks water
> *** Einstein wrote this quiz last century. He said that 98% of the World
> could not figure it out. ***
Aagh! That is too hard for me. I had to ask my computer to help.
(A solver, written in Python, is attached. It requires Python 2.2.)
--
Bob Miller K<bob>
kbobsoft software consulting
http://kbobsoft.com [EMAIL PROTECTED]
# There are 5 houses in five different colors. In each house lives a person
# with a different nationality. These five owners drink a certain drink, smoke
# a certain brand of cigar, and keep a certain pet. No owners have the same
# pet, smoke the same brand of cigar or drink the same drink. The question is
# --- who owns the fish?
#
# Hints:
# R1 - the Brit lives in the red house
# R2 - the Swede keeps dogs as pets
# R3 - the Dane drinks tea
# R4 - the green house is on the left of the white house
# R5 - the green house owner drinks coffee
# R6 - the person who smokes Pall Mall rears birds
# R7 - the owner of the yellow house smokes Dunhill
# R8 - the man living in the house right in the center drinks milk
# R9 - the Norwegian lives in the first house
# R10 - the man who smokes Blends lives next to the one who keeps cats
# R11 - the man who keeps horses lives next to the one who smokes Dunhill
# R12 - the owner who smokes Blue Master drinks beer
# R13 - the German smokes Prince
# R14 - the Norwegian lives next to the blue house
# R15 - the man who smokes Blend has a neighbor who drinks water
# *** Einstein wrote this quiz last century. He said that 98% of the World
# could not figure it out. ***
########################################################################
#
# Some terminology.
#
# There are five "persons". Each person has five traits.
#
# There are five "traits". The traits are house_color,
# nationality, drink, smoke, and pet.
#
# Each trait has five "alternatives". For example,
# the alternatives for drink are beer, coffee, milk, tea, and water.
#
# There are fifteen "rules" which restrict which persons have
# which alternatives. For example, Rule 1 is, "The Brit lives in
# the red house."
#
# A "solution" is a permutation of alternatives among persons.
# It is implemented as a list of five persons, and each person
# is implemented as a list of five alternatives.
from __future__ import generators
def enumerate(seq): # built in in Python 2.3
"""Generate (index, element) for all elements in a sequence."""
i = 0
it = iter(seq)
while 1:
yield i, it.next()
i += 1
class Alternative(object):
def __init__(self, name, trait):
self.name = name
self.trait = trait
def get_trait(self):
return self.trait
def __repr__(self):
return self.name
class Trait(int):
"""Trait is derived from int so that traits can be used to index lists."""
count = 0
def _make(_class, name, alternatives):
"""Make a new trait."""
t = _class(_class.count)
_class.count += 1
t.init(name, alternatives)
# Put the trait name in the global namespace.
exec('global %s; %s = t' % (name, name))
return t
make = classmethod(_make)
def init(self, name, alternatives):
"""Initialize a trait."""
self.name = name
self.rules = []
self.alternatives = []
for altname in alternatives.split(' '):
alt = Alternative(altname, self)
self.alternatives.append(alt)
# Put each alternative in the global namespace.
exec('global %s; %s = alt' % (altname, altname))
def __repr__(self):
return self.name
def add_rule(self, rule):
self.rules.append(rule)
def apply_rules(self, solution):
"Apply this trait's rules to a solution. Returns true "
"if all rules test okay."
return reduce(lambda p, r: p and r.apply(solution),
self.rules, True)
number_of_persons = 5
traits = [
Trait.make('house_color', 'blue green red white yellow'),
Trait.make('nationality', 'Briton Dane German Norwegian Swede'),
Trait.make('drink', 'beer coffee milk tea water'),
Trait.make('smoke', 'Blend BlueMaster Dunhill PallMall Prince'),
Trait.make('pet', 'birds cats dogs fish horses')
]
number_of_traits = len(traits)
if 0:
print traits, [int(t) for t in traits]
print pet.alternatives
print fish
import sys
sys.exit()
class Rule(object):
def __init__(self):
self.applications = 0
def apply(self, solution):
self.applications += 1
self.solution = solution
r = self.test()
assert r == True or r == False
return r
def test(self):
raise NotImplemented
def same_person_is(self, alt1, alt2):
t1 = alt1.get_trait()
for person in self.solution:
if person[t1] == alt1:
return person[alt2.get_trait()] == alt2
return None # fail
def person_is_left_of(self, alt1, alt2):
t2 = alt2.get_trait()
for i, man in enumerate(self.solution):
if man[t2] == alt2:
return i > 0 and self.solution[i-1][alt1.get_trait()] == alt1
return None # fail
def persons_are_adjacent(self, alt1, alt2):
return self.person_is_left_of(alt1, alt2) or \
self.person_is_left_of(alt2, alt1)
class Rule1(Rule):
def test(self):
"""The Brit lives in the red house."""
return self.same_person_is(Briton, red)
class Rule2(Rule):
def test(self):
"""The Swede keeps dogs as pets."""
return self.same_person_is(Swede, dogs)
class Rule3(Rule):
def test(self):
"""The Dane drinks tea."""
return self.same_person_is(Dane, tea)
class Rule4(Rule):
def test(self):
"""The green house is on the left of the white house."""
return self.person_is_left_of(green, white)
class Rule5(Rule):
def test(self):
"""The green house owner drinks coffee."""
return self.same_person_is(green, coffee)
class Rule6(Rule):
def test(self):
"""The person who smokes Pall Mall rears birds."""
return self.same_person_is(PallMall, birds)
class Rule7(Rule):
def test(self):
"""The owner of the yellow house smokes Dunhill."""
return self.same_person_is(yellow, Dunhill)
class Rule8(Rule):
def test(self):
"""The man living in the house right in the center drinks milk."""
return self.solution[2][drink] == milk
class Rule9(Rule):
def test(self):
"""The Norwegian lives in the first house."""
return self.solution[0][nationality] == Norwegian
class Rule10(Rule):
def test(self):
"""The man who smokes Blends lives next to the one who keeps cats."""
return self.persons_are_adjacent(Blend, cats)
class Rule11(Rule):
def test(self):
"""The man who keeps horses lives next to the one who smokes Dunhill"""
return self.persons_are_adjacent(horses, Dunhill)
class Rule12(Rule):
def test(self):
"""The owner who smokes Blue Master drinks beer."""
return self.same_person_is(BlueMaster, beer)
class Rule13(Rule):
def test(self):
"""The German smokes Prince."""
return self.same_person_is(German, Prince)
class Rule14(Rule):
def test(self):
"""The Norwegian lives next to the blue house."""
return self.persons_are_adjacent(Norwegian, blue)
class Rule15(Rule):
def test(self):
"""The man who smokes Blend has a neighbor who drinks water."""
return self.persons_are_adjacent(Blend, water)
rules = [Rule1(), Rule2(), Rule3(), Rule4(), Rule5(),
Rule6(), Rule7(), Rule8(), Rule9(), Rule10(),
Rule11(), Rule12(), Rule13(), Rule14(), Rule15()]
# This is the important bit. As we try solutions, we try permuting
# each trait in turn. So that we can reject bad solutions early on,
# and skip large parts of the solution space, we attach each rule to
# the "last" trait that rule depends on. By "last", we mean last in
# the traits list, which means it's filled out last by
# generate_solutions.
#
# We get ugly and reach inside each rule's code block to find out what
# traits/alternatives the rule references.
for rule in rules:
last_trait = None
for trait in traits:
for thing in [trait] + trait.alternatives:
if thing.name in rule.test.func_code.co_names:
last_trait = trait
last_trait.add_rule(rule)
def gen_permutations(n):
"""Generate all permutations of range(n)."""
def find_ascending(seq):
"""Find rightmost place where seq is in ascending order."""
i = len(seq) - 2
while i >= 0:
if seq[i] < seq[i+1]:
return i
i -= 1
def min_more(v, seq, start):
"""Find smallest item in seq[start:] greater than v."""
k = start
for j in range(start + 1, n):
if seq[j] > v and seq[j] < seq[k]:
k = j
return k
seq = range(n)
while 1:
yield seq
i = find_ascending(seq)
if i is None:
break
k = min_more(seq[i], seq, i + 1)
tail = seq[i:k] + seq[k+1:]
tail.sort()
seq = seq[:i] + seq[k:k+1] + tail
permutations = [p for p in gen_permutations(number_of_persons)]
def print_solution(solution):
for i, person in enumerate(solution):
print '%d: %s' % (i, ' '.join(['%-10s' % str(a) for a in person]))
print
def generate_solutions(traitindex, solution):
"""Generate all solutions that meet the rules."""
n = number_of_traits
if traitindex == n:
yield solution
return
trait = traits[traitindex]
av = trait.alternatives
for perm in permutations:
for i in range(number_of_persons):
solution[i][traitindex] = av[perm[i]]
if trait.apply_rules(solution):
for sol in generate_solutions(traitindex + 1, solution):
yield sol
def null_solution():
"""Return the null solution.
Has the right shape, but None for all values. """
return [[None] * number_of_traits for i in range(number_of_persons)]
def doit():
"""Solve the puzzle."""
for sol in generate_solutions(0, null_solution()):
print_solution(sol)
if 0:
for i, rule in enumerate(rules):
print 'applied rule %d %d times' % (i, rule.applications)
if __name__ == '__main__':
doit()
