Bob, Elegant solution.
The solving concept seems similar to linear programming. You may also be interested in 'pysimplex' at http://www.pythonpros.com/arw/pysimplex/ Pysimplex tries to be an engine to solve this general genre of problems. The tricky part is to figure out how to represent the traits and rules using the standard format. Ralph On (10/10/02 23:25), Bob Miller wrote: > 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() _______________________________________________ Eug-LUG mailing list [EMAIL PROTECTED] http://mailman.efn.org/cgi-bin/listinfo/eug-lug
