Advertisement
Guest User

My Python solution for the Zebra Puzzle

a guest
Oct 24th, 2014
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 6.72 KB | None | 0 0
  1. """Solves the Zebra puzzle. Maurice Makaay, 2014"""
  2. from itertools import permutations
  3.  
  4.  
  5. def solution():
  6.     result = solve_puzzle()
  7.     water_drinker = result.get("Beverage", "Water")["Person"]
  8.     zebra_owner = result.get("Mutt", "Zebra")["Person"]
  9.     return "It is the %s who drinks the water.\n" % water_drinker + \
  10.            "The %s keeps the zebra." % zebra_owner
  11.  
  12.  
  13. def solve_puzzle():
  14.     properties = create_properties()
  15.     ruleset = create_ruleset()
  16.     return Resolver(properties, ruleset).find_solution()
  17.  
  18.  
  19. def create_properties():
  20.     return [
  21.         Properties("Person", (
  22.             "Englishman",
  23.             "Spaniard",
  24.             "Ukranian",
  25.             "Japanese",
  26.             "Norwegian"
  27.         )),
  28.         Properties("Color", (
  29.             "Red",
  30.             "Green",
  31.             "Ivory",
  32.             "Yellow",
  33.             "Blue"
  34.         )),
  35.         Properties("Beverage", (
  36.             "Coffee",
  37.             "Tea",
  38.             "Milk",
  39.             "Orange Juice",
  40.             "Water"
  41.         )),
  42.         Properties("Smoke", (
  43.             "OldGold",
  44.             "Kools",
  45.             "Chesterfields",
  46.             "Lucky Strike",
  47.             "Parliaments"
  48.         )),
  49.         Properties("Mutt", (
  50.             "Dog",
  51.             "Snails",
  52.             "Fox",
  53.             "Horse",
  54.             "Zebra"
  55.         ))
  56.     ]
  57.  
  58.  
  59. def create_ruleset():
  60.     return [
  61.         The.Englishman.lives_in(The.Red.house),
  62.         The.Spaniard.owns(The.Dog),
  63.         Coffee.is_drunk_in(The.Green.house),
  64.         The.Ukranian.drinks(Tea),
  65.         The.Green.house.is_to_the_right_of(The.Ivory.house),
  66.         The.OldGold.smoker.owns(Snails),
  67.         Kools.are_smoked_in(The.Yellow.house),
  68.         Milk.is_drunk_in_the_middle_house(),
  69.         The.Norwegian.lives_in_the_first_house(),
  70.         Chesterfields.are_smoked_next_to(The.Fox),
  71.         Kools.are_smoked_next_to(The.Horse),
  72.         The.LuckyStrike.smoker.drinks(OrangeJuice),
  73.         The.Japanese.smokes(Parliaments),
  74.         The.Norwegian.lives_next_to(The.Blue.house)
  75.     ]
  76.  
  77.  
  78. class The(object):
  79.     """This class is used to write (freakishly) readable rules.
  80.    When accessing 'The.thing', the global variable 'thing' is returned.
  81.    """
  82.     def __getattr__(self, key):
  83.         return globals()[key]
  84.  
  85. The = The()
  86.  
  87.  
  88. class Property(object):
  89.     """Describes a property for the puzzle and is used to produce
  90.    rules for that property.
  91.    """
  92.     def __init__(self, name):
  93.         self.name = name
  94.         self.reset()
  95.  
  96.     def reset(self):
  97.         self.house_nr = None
  98.  
  99.     def bind_to_house(self, house_nr):
  100.         self.house_nr = house_nr
  101.  
  102.     def is_bound_to_house(self):
  103.         return self.house_nr is not None
  104.  
  105.     def is_in_the_first_house(self):
  106.         def rule():
  107.             if self.is_bound_to_house():
  108.                 return self.house_nr == 1
  109.         return rule
  110.  
  111.     def is_in_the_middle_house(self):
  112.         def rule():
  113.             if self.is_bound_to_house():
  114.                 return self.house_nr == 3
  115.         return rule
  116.  
  117.     def is_next_to(self, other):
  118.         def rule():
  119.             if self.is_bound_to_house() and other.is_bound_to_house():
  120.                 return abs(self.house_nr - other.house_nr) == 1
  121.         return rule
  122.  
  123.     def is_to_the_right_of(self, other):
  124.         def rule():
  125.             if self.is_bound_to_house() and other.is_bound_to_house():
  126.                 return self.house_nr == other.house_nr + 1
  127.         return rule
  128.  
  129.     def is_same_house_as(self, other):
  130.         def rule():
  131.             if self.is_bound_to_house() and other.is_bound_to_house():
  132.                 return self.house_nr == other.house_nr
  133.         return rule
  134.  
  135.     def __getattr__(self, attribute):
  136.         """Provide access to virtual properties and methods
  137.        that are used for writing readable rules.
  138.        """
  139.         if attribute in ('house', 'smoker'):
  140.             return self
  141.         if attribute.endswith("to_the_right_of"):
  142.             return self.is_to_the_right_of
  143.         if attribute.endswith("middle_house"):
  144.             return self.is_in_the_middle_house
  145.         if attribute.endswith("first_house"):
  146.             return self.is_in_the_first_house
  147.         if attribute.endswith("next_to"):
  148.             return self.is_next_to
  149.         return self.is_same_house_as
  150.  
  151.  
  152. class Properties(list):
  153.     """A collection of properties of a given type (persons, colors, etc.)."""
  154.     def __init__(self, property_type, names):
  155.         super(Properties, self).__init__()
  156.         self.property_type = property_type
  157.         for name in names:
  158.             p = Property(name)
  159.             self.append(p)
  160.             # Make the property available as a global variable, which
  161.             # can be used for writing the rules in a really clear way.
  162.             globals()[name.replace(' ', '')] = p
  163.  
  164.     def reset(self):
  165.         for property_ in self:
  166.             property_.reset()
  167.  
  168.  
  169. class Resolver(object):
  170.     """Resolves the ruleset puzzle solution."""
  171.     def __init__(self, properties, ruleset):
  172.         self.properties = properties
  173.         self.ruleset = ruleset
  174.  
  175.     houses_permutations = list(permutations([1, 2, 3, 4, 5]))
  176.  
  177.     def find_solution(self, idx=0):
  178.         """Solves the puzzle by recursively searching for property
  179.        permutations for which the ruleset is satisfied, until
  180.        satisfying permutations are found for all sets of properties.
  181.        """
  182.         properties = self.properties[idx]
  183.         for houses_permutation in self.houses_permutations:
  184.             for property_, house in zip(properties, houses_permutation):
  185.                 property_.bind_to_house(house)
  186.             if not any(rule() is False for rule in self.ruleset):
  187.                 # No more property sets. We found the solution!
  188.                 if idx + 1 == len(self.properties):
  189.                     return Solution(self.properties)
  190.                 # Recurse into the next property set.
  191.                 result = self.find_solution(idx + 1)
  192.                 if result:
  193.                     return result
  194.         properties.reset()
  195.  
  196.  
  197. class Solution(dict):
  198.     """Describes the solution for the puzzle."""
  199.     def __init__(self, properties):
  200.         super(Solution, self).__init__()
  201.         for house_nr in range(1, 6):
  202.             self[house_nr] = {"House": house_nr}
  203.         for p in properties:
  204.             for property_ in p:
  205.                 self[property_.house_nr][p.property_type] = property_.name
  206.  
  207.     def get(self, property_type, name):
  208.         """Returns a dict containing all data for the house that relates
  209.        to the provided property type and name.
  210.        """
  211.         return next(
  212.             data for house_nr, data in self.items()
  213.             if data[property_type] == name
  214.         )
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement