3 ms·
For comparison, here is my own solution in Python 3 to the Zebra Puzzle. To me this solution seems sorter and easier to understand: from itertools import per
by todd8 7y ago
For comparison, here is my own solution in Python 3 to the Zebra Puzzle. To me this solution seems sorter and easier to understand:
from itertools import permutations as perms
houses = range(1,6) # houses numbered 1,2,3,4,5
for Englishman, Spaniard, Ukrainian, Norwegian, Japanese in perms(houses):
if Norwegian != 1: continue # rule 10
for red, green, ivory, yellow, blue in perms(houses):
if Englishman != red: continue # rule 2
if green != ivory + 1: continue # rule 6
if Norwegian not in [blue-1,blue+1]: continue # rule 15
for coffee, tea, milk, oj, water in perms(houses):
if coffee != green: continue # rule 4
if Ukrainian != tea: continue # rule 5
if milk != 3: continue # rule 9
for oldgold, kools, chesterfields, luckys, parliaments in perms(houses):
if kools != yellow: continue # rule 8
if luckys != oj: continue # rule 13
if Japanese != parliaments: continue # rule 14
for dog, snails, fox, horse, zebra in perms(houses):
if Spaniard != dog: continue # rule 3
if oldgold != snails: continue # rule 7
if chesterfields not in [fox-1,fox+1]: continue # rule 11
if kools not in [horse-1, horse+1]: continue # rule 12
person = {Englishman: 'Englishman', Spaniard: 'Spainard',
Ukrainian: 'Ukrainian', Norwegian: 'Norwegian', Japanese: 'Japanese'}
print(f'{person[water]} drinks water')
print(f'{person[zebra]} owns the zebra')
- anewhnaccount2 7y agoEnumerating all solutions and checking will always be the simplest approach for find the set of inputs returning true for a decision problem. However, a constraint solver will not necessarily have to enumerate all solutions.
- todd8 7y agoYes it would take a long time to do it that way since there would be roughly 25 billion solutions to evaluate. My Python program doesn’t do this and runs very fast. Elapsed time for this program is approximately 0.03 seconds on my 2013 desktop and it finds all possible solution (in this case one). Normally, inner loops are executed more times than outer loops, but in this program the bodies of the inner loops are skipped (because of the continue statements) when constraints fail in the the outer loops. The five loop bodies are executed a total of 120, 2880, 1440, 1440, 960 times respectively (I put counters in each loop to determine this, all counters were initialized before any of the loops begin). I wrote this program (for a different version of this same problem) while waiting for my daughter to come downstairs to be driven to school one morning around five years ago. (See https://news.ycombinator.com/item?id=7734998 https://news.ycombinator.com/item?id=7734998)
- hjek 7y agoBrilliant! Cool to see the two paradigms side-by-side. If there was a similar puzzle that had more than one solution, would it be straight-forward to do that using for loops as well in Python? (Curious if you can do backtracking that way)
- todd8 7y agoYes, this approach does find every solution and it is using backtracking. See my other reply to a sibling comment.
- falsedan 7y agoThe deep nesting and negation of the tests made this look weird to me and harder to see how the main idea was exhaustive searching of all permutations. I think it's clearer when the constraints are separated from the searching: People = collections.namedtuple('People', ['Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese']) # etc. def rule_10(people): return people.Norwegian == 0 def rule_2(people, color): return people.Englishman == color.Red def rule_6(color): return color.Ivory - color.Green == 1 def rule_15(people, color): return abs(people.Norwegian - color.Blue) == 1 def rule_4(beverage, color): return beverage.Coffee == color.Green # etc. constraints = [ rule_1, rule_2, ... ] # etc. def inject(func, vars=locals): signature = inspect.signature(func) args_from = operator.attrgetter(signature.parameters.keys()) return func(*args_from(vars)) houses = range(0,5) for people in map(People._make, perms(houses)): for color in map(Color._make, perms(houses)): for beverage in map(Beverage._make, perms(houses)): for cigarette in map(Cigarette._make, perms(houses)): for pet in map(Pet._make, perms(houses)): if all(map(inject, constraints)): print(f'The {People._fields[beverage.Water]} drinks water') print(f'The {People._fields[pet.Zebra]} owns the zebra') sys.exit(0) print(f'Sorry, no idea who drinks water or owns a zebra') sys.exit(1) No pruning of the solution space but `all` will exit early if it can. You could change `inject` (terrible name) to pass the list of rules & call those whose signatures are fulfilled at the beginning of each for-loop, and return a list of the uncalled rules + the results of the called rules, and test the results with `all` & keep the uncalled rules handy for the next for-loop. I didn't do it because there's already too much boilerplate in the for-loops
- deleted 7y ago[deleted]