cs212 ยป

# Unit2 Code

Contents

## zebra.py

``````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))
``````

## cryptarithmetic.py

``````from __future__ import division
import string, re
import itertools
import time

def solve(formula):
"""Given a formula like 'ODD + ODD == EVEN', fill in digits to solve it.
Input formula is a string; output is a digit-filled-in string or None."""
for answer in (f for f in fill_in(formula) if valid(f)):

def fill_in(formula):
"Generate all possible fillings-in of letters in formula with digits."
letters = ''.join(set(l for l in formula if l in string.uppercase))
for digits in itertools.permutations('1234567890', len(letters)):
table = string.maketrans(letters, ''.join(digits))
yield formula.translate(table)

def valid(f):
"""Formula f is valid if and only if it has no
numbers with leading zero, and evals true."""
try:
return not re.search(r'\b0[0-9]', f) and eval(f) is True
except ArithmeticError:
return False

def faster_solve(formula):
"""Given a formula like 'ODD + ODD == EVEN', fill in digits to solve it.
Input formula is a string; output is a digit-filled-in string or None.
This version precompiles the formula; only one eval per formula."""
f, letters = compile_formula(formula)
for digits in itertools.permutations((1,2,3,4,5,6,7,8,9,0), len(letters)):
try:
if f(*digits) is True:
table = string.maketrans(letters, ''.join(map(str, digits)))
return formula.translate(table)
except ArithmeticError:
pass

def compile_formula(formula, verbose=False):
"""Compile formula into a function.   Also return letters found, as a str,
in same order as parms of function. For example, 'YOU == ME**2' returns
(lambda Y, M, E, U, O): (U+10*O+100*Y) == (E+10*M)**2), 'YMEUO' """
letters = ''.join(set(re.findall('[A-Z]', formula)))
parms = ', '.join(letters)
tokens = map(compile_word, re.split('([A-Z]+)', formula))
body = ''.join(tokens)
f = 'lambda %s: %s' % (parms, body)
if verbose: print f
return eval(f), letters

def compile_word(word):
"""Compile a word of uppercase letters as numeric digits.
E.g., compile_word('YOU') => '(1*U+10*O+100*Y)'
Non-uppercase words unchanged: compile_word('+') => '+'"""
if word.isupper():
terms = [('%s*%s' % (10**i, d))
for (i, d) in enumerate(word[::-1])]
return '(' + '+'.join(terms) + ')'
else:
return word

examples = """TWO + TWO == FOUR
A**2 + B**2 == C**2
A**2 + BE**2 == BY**2
X / X == X
A**N + B**N == C**N and N > 1
ATOM**0.5 == A + TO + M
GLITTERS is not GOLD
ONE < TWO and FOUR < FIVE
ONE < TWO < THREE
RAMN == R**3 + RM**3 == N**3 + RX**3
sum(range(AA)) == BB
sum(range(POP)) == BOBO
ODD + ODD == EVEN
PLUTO not in set([PLANETS])""".splitlines()

def test():
t0 = time.clock()
for example in examples:
print; print 13*' ', example
print '%6.4f sec:   %s ' % timedcall(faster_solve, example)
print '%6.4f tot.' % (time.clock()-t0)

def timedcall(fn, *args):
"Call function with args; return the time in seconds and result."
t0 = time.clock()
result = fn(*args)
t1 = time.clock()
return t1-t0, result

def average(numbers):
"Return the average (arithmetic mean) of a sequence of numbers."
return sum(numbers) / float(len(numbers))

def timedcalls(n, fn, *args):
"""Call fn(*args) repeatedly: n times if n is an int, or up to
n seconds if n is a float; return the min, avg, and max time"""
if isinstance(n, int):
times = [timedcall(fn, *args)[0] for _ in range(n)]
else:
times = []
total = 0.0
while total < n:
t = timedcall(fn, *args)[0]
total += t
times.append(t)
return min(times), average(times), max(times)

test()
``````

## mockstr.py

The following is Peter's mock string class mentioned in this question

``````def _unmockstr(x):
"Secret function to convert mockstr back to str; leaves other objects unchanged."
return str.__str__(x) if isinstance(x, mockstr) else x

class mockstr(str):
"""An object that looks and acts like a str, but counts comparisons and accesses.
Obeys two rules:
(1) Any piece of a mockstr that is returned must be a mockstr (not a str)
(2) Any comparison or access increments num_comparisons or num_accesses
Despite these precautions, the class is Not secure against many simple attacks,
including map(ord, s) or str.__str__(s).
"""

## Track total number of comparisons and accesses to any mockstr objects
num_comparisons, num_accesses = 0, 0

def __getitem__(self, i):
"s[i] counts as 1 access."
mockstr.num_accesses += 1
return mockstr(_unmockstr(self)[i])

def __getslice__(self, start, end):
"s[i:i+n] counts as n accesses."
end = min(len(self), end)
mockstr.num_accesses += (end - start)
return mockstr(_unmockstr(self)[start:end])

## s1 == s2 counts as len(s1) comparisons (so s[i] == s[j] counts as 1).
def __eq__(self, other): return self._c() == _unmockstr(other)
def __ne__(self, other): return self._c() != _unmockstr(other)
def __ge__(self, other): return self._c() >= _unmockstr(other)
def __le__(self, other): return self._c() <= _unmockstr(other)
def __gt__(self, other): return self._c() >  _unmockstr(other)
def __lt__(self, other): return self._c() <  _unmockstr(other)

def _c(self):
"Secret method to convert to str, incrementing num_comparisons by len(self)."
mockstr.num_comparisons += len(self)
return _unmockstr(self)

def _a(self):
"Secret method to convert to str, incrementing accesses by len(self)."
mockstr.num_accesses += len(self)
return _unmockstr(self)

## Any piece of self returned by normal methods should be a mockstr, not a str.
def upper(self):        return mockstr(self._a().upper())
def lower(self):        return mockstr(self._a().lower())
def title(self):        return mockstr(self._a().title())
def capitalize(self):   return mockstr(self._a().capitalize())
def swapcase(self):     return mockstr(self._a().swapcase())
def strip(self):        return mockstr(self._a().strip())
def lstrip(self):       return mockstr(self._a().lstrip())
def rstrip(self):       return mockstr(self._a().rstrip())
def split(self, *args): return map(mockstr, self._a().split(*args))
def rsplit(self, *args):return map(mockstr, self._a().rsplit(*args))
def join(self, *args):  return mockstr(self._a().join(*args))
def __mod__(self, tup): return mockstr(self._a() % tup)

def __str__(self):
return '<mockstr %r of len %d at 0x%x>' % (_unmockstr(self), len(self), id(self))

__repr__ = __str__

@staticmethod
def reset(verbose=True):
"Reset counts to zero, and optionally, before resetting, print the counts."
if verbose: print 'mockstr: %d accesses and %d comparisons' % (
mockstr.num_accesses, mockstr.num_comparisons)
mockstr.num_accesses, mockstr.num_comparisons = 0, 0

##############################################################################

class test_mockstr:
"""## You can run this test with: python -m doctest mockstr.py
>>> s = mockstr('0123456789')
>>> len(s)
10
>>> s[0] == '0'
True
>>> s[-1] == '9'
True
>>> s.reset()
mockstr: 2 accesses and 2 comparisons
>>> s[0] == s[1]
False
>>> s.reset()
mockstr: 2 accesses and 1 comparisons

>>> sum(a == b for a in s for b in s)
10
>>> s.reset()
mockstr: 121 accesses and 100 comparisons

>>> items = list(s)
>>> sum(a == b for a in items for b in items)
10
>>> s.reset()
mockstr: 11 accesses and 100 comparisons

>>> s1, s2 = mockstr('this THAT').split()
>>> s.reset()
mockstr: 9 accesses and 0 comparisons
>>> s1[0] == s2[0]
False
>>> s.reset()
mockstr: 2 accesses and 1 comparisons
>>> s1[0].upper() == s2[0].upper()
True
>>> s.reset()
mockstr: 4 accesses and 1 comparisons
"""
``````