Solving “Who owns the Zebra” programmatically?

by

Here’s a solution in Python based on constraint-programming:

from constraint import AllDifferentConstraint, InSetConstraint, Problem

# variables
colors        = "blue red green white yellow".split()
nationalities = "Norwegian German Dane Swede English".split()
pets          = "birds dog cats horse zebra".split()
drinks        = "tea coffee milk beer water".split()
cigarettes    = "Blend, Prince, Blue Master, Dunhill, Pall Mall".split(", ")

# There are five houses.
minn, maxn = 1, 5
problem = Problem()
# value of a variable is the number of a house with corresponding property
variables = colors + nationalities + pets + drinks + cigarettes
problem.addVariables(variables, range(minn, maxn+1))

# Each house has its own unique color.
# All house owners are of different nationalities.
# They all have different pets.
# They all drink different drinks.
# They all smoke different cigarettes.
for vars_ in (colors, nationalities, pets, drinks, cigarettes):
    problem.addConstraint(AllDifferentConstraint(), vars_)

# In the middle house they drink milk.
#NOTE: interpret "middle" in a numerical sense (not geometrical)
problem.addConstraint(InSetConstraint([(minn + maxn) // 2]), ["milk"])
# The Norwegian lives in the first house.
#NOTE: interpret "the first" as a house number
problem.addConstraint(InSetConstraint([minn]), ["Norwegian"])
# The green house is on the left side of the white house.
#XXX: what is "the left side"? (linear, circular, two sides, 2D house arrangment)
#NOTE: interpret it as 'green house number' + 1 == 'white house number'
problem.addConstraint(lambda a,b: a+1 == b, ["green", "white"])

def add_constraints(constraint, statements, variables=variables, problem=problem):
    for stmt in (line for line in statements if line.strip()):
        problem.addConstraint(constraint, [v for v in variables if v in stmt])

and_statements = """
They drink coffee in the green house.
The man who smokes Pall Mall has birds.
The English man lives in the red house.
The Dane drinks tea.
In the yellow house they smoke Dunhill.
The man who smokes Blue Master drinks beer.
The German smokes Prince.
The Swede has a dog.
""".split("\n")
add_constraints(lambda a,b: a == b, and_statements)

nextto_statements = """
The man who smokes Blend lives in the house next to the house with cats.
In the house next to the house where they have a horse, they smoke Dunhill.
The Norwegian lives next to the blue house.
They drink water in the house next to the house where they smoke Blend.
""".split("\n")
#XXX: what is "next to"? (linear, circular, two sides, 2D house arrangment)
add_constraints(lambda a,b: abs(a - b) == 1, nextto_statements)

def solve(variables=variables, problem=problem):
    from itertools  import groupby
    from operator   import itemgetter

    # find & print solutions
    for solution in problem.getSolutionIter():
        for key, group in groupby(sorted(solution.iteritems(), key=itemgetter(1)), key=itemgetter(1)):
            print key, 
            for v in sorted(dict(group).keys(), key=variables.index):
                print v.ljust(9),
            print

if __name__ == '__main__':
    solve()

Output:

1 yellow    Norwegian cats      water     Dunhill  
2 blue      Dane      horse     tea       Blend    
3 red       English   birds     milk      Pall Mall
4 green     German    zebra     coffee    Prince   
5 white     Swede     dog       beer      Blue Master

It takes 0.6 seconds (CPU 1.5GHz) to find the solution.
The answer is “German owns zebra.”

To install the constraint module via pip:
pip install python-constraint

To install manually:

More Related Contents:

  1. XOR of three values
  2. Should a function have only one return statement?
  3. What is the difference between concurrency and parallelism?
  4. Can every recursion be converted into iteration?
  5. Why shouldn’t I use “Hungarian Notation”?
  6. Expression Versus Statement
  7. Are there any legitimate use-cases for “goto” in a language that supports loops and functions?
  8. Prefer composition over inheritance?
  9. Singletons: good design or a crutch? [closed]
  10. Conventions for exceptions or error codes [closed]
  11. Test loops at the top or bottom? (while vs. do while) [closed]
  12. Which, and why, do you prefer Exceptions or Return codes?
  13. How do I display the binary representation of a float or double?
  14. Buffered vs unbuffered IO
  15. Are circular class dependencies bad from a coding style point of view? [closed]
  16. What is the difference between Type and Class?
  17. Allen Holub wrote “You should never use get/set functions”, is he correct? [duplicate]
  18. What are the lesser known but useful data structures?
  19. Why is it recommended to have empty line in the end of a source file?
  20. What’s the best name for a non-mutating “add” method on an immutable collection? [closed]
  21. Are exceptions really for exceptional errors? [closed]
  22. What is a stack overflow?
  23. Generate colors between red and green for a power meter?
  24. Calculating a 2D Vector’s Cross Product
  25. What’s the shortest code to cause a stack overflow? [closed]
  26. Hash Code and Checksum – what’s the difference?
  27. In what situations is octal base used?
  28. When should a method be static?
  29. How to design extensible software (plugin architecture)? [closed]
  30. String Compare “Logic”

Leave a Comment