Instantly share code, notes, and snippets.

# joyrexus/zebra.md

Last active March 3, 2017 21:01
Show Gist options
• Save joyrexus/5301901 to your computer and use it in GitHub Desktop.
Norvig's treatment of the zebra puzzle.

# Norvig's Treatment of the Zebra Puzzle

Here's Peter Norvig's treatment of the zebra puzzle from his CS212 course.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import itertools import time def imright(h1, h2): "House h1 is immediately right of h2 if h1-h2 == 1." return h1-h2 == 1 def nextto(h1, h2): "Two houses are next to each other if they differ by 1." return abs(h1-h2) == 1 def zebra_puzzle(): "Return a tuple (WATER, ZEBRA indicating their house numbers." houses = first, _, middle, _, _ = [1, 2, 3, 4, 5] orderings = list(itertools.permutations(houses)) # 1 return next((WATER, ZEBRA) for (red, green, ivory, yellow, blue) in c(orderings) if imright(green, ivory) for (Englishman, Spaniard, Ukranian, Japanese, Norwegian) in c(orderings) if Englishman is red if Norwegian is first if nextto(Norwegian, blue) for (coffee, tea, milk, oj, WATER) in c(orderings) if coffee is green if Ukranian is tea if milk is middle for (OldGold, Kools, Chesterfields, LuckyStrike, Parliaments) in c(orderings) if Kools is yellow if LuckyStrike is oj if Japanese is Parliaments for (dog, snails, fox, horse, ZEBRA) in c(orderings) if Spaniard is dog if OldGold is snails if nextto(Chesterfields, fox) if nextto(Kools, horse) ) def c(sequence): c.starts += 1 for item in sequence: c.items += 1 yield item def instrument_fn(fn, *args): c.starts, c.items = 0, 0 result = fn(*args) print('%s got %s with %5d iters over %7d items'%( fn.__name__, result, c.starts, c.items))