a Python snippet to solve Einstein’s Puzzle


/ Published in: Python
Save to your folder(s)

a Python snippet to solve Einstein’s Puzzle


Copy this code and paste it in your HTML
  1. #!/usr/bin/env python
  2. # -*- coding: utf-8 -*-
  3. #
  4. # einstein_puzzle.py
  5. #
  6. # Copyright 2012 jackyspy <[email protected]>
  7. #
  8. # This program is free software; you can redistribute it and/or modify
  9. # it under the terms of the GNU General Public License as published by
  10. # the Free Software Foundation; either version 2 of the License, or
  11. # (at your option) any later version.
  12. #
  13. # This program is distributed in the hope that it will be useful,
  14. # but WITHOUT ANY WARRANTY; without even the implied warranty of
  15. # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16. # GNU General Public License for more details.
  17. #
  18. # You should have received a copy of the GNU General Public License
  19. # along with this program; if not, write to the Free Software
  20. # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  21. # MA 02110-1301, USA.
  22. #
  23. #
  24.  
  25. from itertools import permutations
  26.  
  27. color = ['Green', 'White', 'Yellow', 'Blue', 'Red']
  28. national = ['English', 'Swedish', 'Norwegian', 'German', 'Dane']
  29. drink = ['Tea', 'Coffee', 'Milk', 'Beer', 'Water']
  30. cigar = ['PallMall', 'DunHill', 'Blends', 'BlueMaster', 'Prince']
  31. pet = ['Bird', 'Dog', 'Horse', 'Cat', 'Fish']
  32. choices = (color, national, drink, cigar, pet)
  33.  
  34. constraints=[
  35. ( 'Red', 'English', None, None, None ), # The Englishman lives in the red house.
  36. ( None, 'Swedish', None, None, 'Dog' ), # The Swede keeps dogs.
  37. ( None, 'Dane', 'Tea', None, None ), # The Dane drinks tea.
  38. ( 'Green', None, 'Coffee', None, None ), # The owner of the green house drinks coffee.
  39. ( None, None, None, 'PallMall', 'Bird' ), # The Pall Mall smoker keeps birds.
  40. ( 'Yellow', None, None, 'DunHill', None ), # The owner of the yellow house smokes Dunhills.
  41. ( None, None, 'Beer', 'BlueMaster', None ), # The man who smokes Blue Masters drinks bier.
  42. ( None, 'German', None, 'Prince', None ), # The German smokes Prince.
  43. ]
  44.  
  45. neighbors = [
  46. ( (3, 'Blends'), (4, 'Cat') ), # The Blend smoker has a neighbor who keeps cats.
  47. ( (3, 'DunHill'), (4, 'Horse') ), # The man who keeps horses lives next to the Dunhill smoker.
  48. ( (1, 'Norwegian'), (0, 'Blue') ), # The Norwegian lives next to the blue house.
  49. ( (3, 'Blends'), (2, 'Water') ), # The Blend smoker has a neighbor who drinks water.
  50. ]
  51.  
  52.  
  53. def find_iter(func, iterable):
  54. for i in iterable:
  55. if func(i):
  56. return i
  57.  
  58.  
  59. def select_item(curr_person, idx, selected_persons):
  60. person_len = len(curr_person)
  61. assert idx < person_len
  62.  
  63. # selected by the constraints already
  64. if curr_person[idx]:
  65. if idx == person_len - 1:
  66. yield tuple(curr_person)
  67. else:
  68. for i in select_item(curr_person, idx + 1, selected_persons):
  69. yield tuple(i)
  70. return
  71.  
  72. for s in choices[idx]:
  73. if find_iter(lambda x: x[idx] == s, selected_persons):
  74. # chosen by others
  75. continue
  76.  
  77. new_curr = curr_person[:]
  78. new_curr[idx] = s
  79.  
  80. cons = find_iter(lambda x: x[idx] == s, constraints)
  81. if cons:
  82. is_conflict = False
  83.  
  84. for i in range(person_len):
  85. if i < idx:
  86. # check if conflict with prior
  87. if cons[i]:
  88. is_conflict = True
  89. break
  90. elif i > idx:
  91. # set the value indicated by constraints
  92. if cons[i]:
  93. new_curr[i] = cons[i]
  94.  
  95. if is_conflict:
  96. continue
  97.  
  98.  
  99. if idx == person_len - 1:
  100. yield tuple(new_curr)
  101. else:
  102. for i in select_item(new_curr, idx + 1, selected_persons):
  103. yield tuple(i)
  104.  
  105.  
  106. def select_all():
  107. for a1 in select_item(['Red', 'English', None, None, None], 1, []):
  108. for a2 in select_item(['Green', None, 'Coffee', None, None], 1, [a1]):
  109. for a3 in select_item(['Yellow', None, None, 'DunHill', None], 1, [a1, a2]):
  110. for a4 in select_item(['Blue', None, None, None, None], 1, [a1, a2, a3]):
  111. for a5 in select_item(['White', None, None, None, None], 1, [a1, a2, a3, a4]):
  112. yield [a1, a2, a3, a4, a5]
  113.  
  114.  
  115. def check_result(res):
  116. def get_item(idx, val):
  117. return find_iter(lambda x: x[idx] == val, res)
  118.  
  119. def get_house(idx, val, house):
  120. return house[get_item(idx,val)]
  121.  
  122. def set_house(idx, val, house, house_id):
  123. item = get_item(idx, val)
  124.  
  125. if house[item]:
  126. return house[item] == house_id # check if conflict with prior
  127.  
  128. # if house_id used by other person, shout
  129. if house_id in house.values():
  130. return False
  131.  
  132. house[item] = house_id
  133. return True
  134.  
  135. def is_neighbor(cond1, cond2, house):
  136. house_id1 = get_house(cond1[0], cond1[1], house)
  137. house_id2 = get_house(cond2[0], cond2[1], house)
  138. return house_id1 - house_id2 in (1, -1)
  139.  
  140. def check_neighbors(neighbors, house):
  141. for cond1, cond2 in neighbors:
  142. if not is_neighbor(cond1, cond2, house):
  143. return False
  144. return True
  145.  
  146. house = {}
  147. for i in res:
  148. house[i] = 0 # init with house_id unset
  149.  
  150. if not set_house(2, 'Milk', house, 3): # The man in the center house drinks milk.
  151. return False
  152.  
  153. if not set_house(1, 'Norwegian', house, 1): # The Norwegian lives in the first house.
  154. return False
  155.  
  156. for i in range(1,5): # since green cannot be the last one
  157. house2 = house.copy()
  158.  
  159. if not set_house(0, 'Green', house2, i):
  160. continue
  161. if not set_house(0, 'White', house2, i + 1): # The green house is just to the left of the white one.
  162. continue
  163.  
  164. for unset_ids in permutations(set(range(1,6)) - set((1, 3, i, i + 1))): # get full permutations of rest house ids
  165. house3 = house2.copy()
  166.  
  167. # fill the houses without id one by one
  168. k = 0
  169. for j in res:
  170. if not house3[j]:
  171. house3[j] = unset_ids[k]
  172.  
  173. k += 1
  174. if k == len(unset_ids):
  175. break
  176.  
  177. if check_neighbors(neighbors, house3):
  178. return house3
  179.  
  180. return False
  181.  
  182.  
  183.  
  184. def main():
  185. for i in select_all():
  186. res = check_result(i)
  187. if res:
  188. print '='*20 + ' solved ' + '='*20
  189. for _, person in sorted((v,k) for k,v in res.items()):
  190. print person
  191.  
  192. if __name__ == '__main__':
  193. main()

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.