Skip to content

Instantly share code, notes, and snippets.

Last active March 3, 2017 21:01
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
Norvig's treatment of the zebra puzzle.
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment