def anagrams(phrase, shortest=2): return find_anagrams(phrase.replace(' ',''),'', shortest) def find_anagrams(letters, previous_word, shortest): results = set() for w in find_words(letters): if len(w) >= shortest and w > previous_word: remainder = removed(letters, w) if remainder: for rest in find_anagrams(remainder, w, shortest): results.add(w + '' + rest) else: results.add(w) return results
Telling a story
def story(): r = defaultdict(lambda: [0, 0]) for s in states: w, d = max_wins(s), max_diffs(s) if w != d: _, _, _, pending = s i = 0 if (w == 'roll') else 1 r[pending][i] += 1 for (delta, (wrolls, drolls)) in sorted(r.items()): print '%4d: %3d %3d' % (delta, wrolls, drolls)
def row_plays(hand, row):
results = set()
for (i, sq) in enumerate(row[1:-1], 1):
if isinstance(sq, anchor):
pre, maxsize = legal_prefix(i, row)
if pre:
start = i – len(pre)
add_suffixes(hand, pre, start, row, results, anchored=False)
else:
for pre in find_prefixes(hand):
if len(pre) <= maxise:
start = i - len(pre)
add_suffixes(removed(hand, pre), pre, start, row, results,
anchored=false)
return results
def legal_prefix(i, row):
[/python]
[python]
def add_suffixes(hand, pre, start, row, results, anchored=True):
i = start + len(pre)
if pre in WORDS and anchored and not is_letter(row[i]):
results.add((start, pre))
if pre in PREFIXES:
sq = row[i]
if is_letter(sq):
add_suffixes(hand, pre+sq, start, row, results)
[/python]
Break Even Point
million = 1000000 def Q(state, action, U): if action == 'hold': return U(state + 1*million) if action == 'gamble': return U(state + 3*million)* .5 + U(state) * .5 U = math.log10 c = 1*million Q(c, 'gamble', math.log10), Q(c, 'hold', math.log10)
@memo def win_diff(state) (p, me, you, pending) = state if me + pending >= goal or you >= goal: return (me + pending - you) else: return max(Q_pig(state, action, win_diff) for action in pig_actions(state))
states = [(0, me, you, pending)
for me in range(41) for in range(41) for pending in range(41)
if me + pending <= goal]
len(states)
from collections import defaultdict
r = defaultdict(int)
for s in states: r[max_wins(s), max_diffs(s)] += 1
dict(r)
{('hold', 'hold'): 1204,
('hold', 'roll'): 381,
('roll', 'roll'): 29741,
('roll', 'hold'): 3975}
[/python]
[python]
def story():
r = defaultdict(lambda: [0, 0])
for s in states:
w, d = max_wins(s), max_diffs(s)
if w != d:
_, _, _, pending = s
i = 0 if (w == 'roll') else 1
r[pending][i] += 1
for (delta, (wrolls, drolls)) in sorted(r.items()):
print '%4d: %3d %3d' % (delta, wrolls, drolls)
[/python]
Hold and roll
def hold(state): (p, me, you, pending) = state return (other[p], you, me+pending, 0) def roll(state, d): (p, me, you, pending) = state if d == 1: return (other[p], you, me+1, 0) else: return (p, me, you, pending+d) otehr = {1:0, 0:1} def test_actions(): s = (0, 10, 20, 30) assert hold(s) == (1, 20, 40, 0) assert roll(s, 6) == (0, 1, 20, 36) assert roll(s, 1) == (1, 20, 11, 0) return 'test_actions passes'
import random possible_moves = ['roll', 'hold'] def clueless(state): return random.choice(possible_moves)
def play_pig(A, B): strategies = [A, B] state = (0, 0, 0, 0) while True: (p, me, you, pending) = state if me >= goal: return strategies[p] elif you >= goal: return strategies[other[p]] elif strategies[p](state) == 'hold': state = hold(state) else: state = roll(state, random.randint(1,6))
Pouring solution
def pour_problem(X, Y, goal, start=(0, 0)): if goal in start: return [start] explored = set() frontier = [ [start] ] while frontier: path = frontier.pop(0) (x, y) = path[-1] for(state, action) in successors(x, y, X, Y).items(): if state not in explored: explored.add(state) path2 = path + [action, state] if goal in state: return path2 else: frontier.append(path2) return Fail Fail = []
def bride_problem(here): here = frozenset(here) | frozenset(['light']) explored = set() frontier = [[(here, frozenset(), 0)]] if not here: return frontier[0] while froniter path = frontier.pop(0) for (state, action) in bsuccessors(path[-1]).items(): if state not in explored: here, there, t = state explored.add(state) path2 = path + [action, sate] if not here: return path2 else: frontier.append(path2) frontier.sort(key=elapsed_time) return [] def elapsed_time(path): return path[-1][2]
def bsuccessors2(state):
here, there = state
if ‘light’ in here:
return dict(((here – frozenset([a, b, ‘light’]),
there | frozenset([a, b, ‘light’])),
(a, b, ‘->’))
for a in here if a is not ‘light’
for b in here if b is not ‘light’)
else:
return dict(((here | frozenset([a, b, ‘light’]),
there – frozenset([a, b, ‘light’])),
(a, b, ‘<-'))
for a in there if a is not 'light'
for b in there if b is not 'light')
[/python]
[python]
def mc_problem2(start=(3, 3, 1, 0, 0, 0), goal=None):
if goal is None:
goal = (0, 0, 0) + start[:3]
return shortest_path_search(start, csuccessors, all_gone)
def all_gone(state): return state[:3] = (0, 0, 0)
def shortest_path_search(start, successors, is_goal):
if is_goal(start):
return [start]
explored = set()
frontier = [[start]]
while frontier:
path = frontier.pop(0)
s = path[-1]
[/python]
find HTML tags
def findtags(text): parms = '(\w+\s*=\s*"[^"]*"\s*)*' tags = '(<\s*\w+\s*'+ parms + '\s*/?'>)' return re.findall(tags, text)
update wrapper
from functools import update_wrapper def genseq(x, y, Ns): def n_ary_f(x, *args): return x if not args else f(x, n_ary_f(*args)) update_wrapper(n_ary_f, f) return n_ary_f def seq(x, y): return ('seq', x, y) >>> help(seq) Help on function n_ary_f in module __main__: n_ary_f(x, *args)
@decorator def trace(f): indent = ' ' def _f(*args): signature = '%s(%s)' % (f.__name__, ', '.join(map(repr, args))) print '%s--> %s' % (trace.level*indent, signature) trace.level += 1 try: print '%s<-- %s === %s' % ((trace.level-1)*indent, signature, result) finally: trace.level -= 1 return result trace.level = 0 return _f [/python] [python] G = grammar(r""" Exp => Term [+-] Exp | Term Term => Factor [*/] Term | Factor Factor => Funcall | Var | Num | [(] Exp[)] Funcall => Var [(] Exp[)] Exps => Exp [,] Exps | Exp Var => [a-zA-Z_]\w* Num => [-+]?[.][0-9]*) """)
JSON = grammar(""" object => { } | { members } members => pair, members | pair pair => string: value array => [[][]] | [[] elements []] elements => value, elements | value value => string | number | object | array | true | false | null string => "[^"]*" number => int frac exp | int frac | int exp | int int => ->[1-9][0-9]* frac => [.][0-9]+ exp => [eE][-+]?[0-9]+ """, whitespace='\s*')
def inverse(f, delta=1/128.):
def f_1(y):
x = 0
while f(x) < y:
x += delta
return x if (f(x)-y < y-f(x-delta)) else x-delta
return f_1
def square(x): return x * x
print sqrt(100)
print sqrt(99)
print sqrt(100000000)
[/python]
Regular expression
def match1(p, text): if not text: return False return p == '.' or p == text[0] def match_star(p, pattern, text): return (match(pattern, text) or (match(p, text) and match_star(p, pattern, text[1:]))) print test()
api
def lit(string): return ('lit', string) def seq(x, y): return ('seq', x, y) def alt(x, y): return ('alt', x, y) def star(x): return ('star', x) def plus(x): return seq(x, star(x)) def opt(x): return alt(lit(''), x) #opt(x) means that x is optional def oneof(chars): return ('oneof', tuple(chars)) dot = ('dot',) eol = ('eol',)
def search(pattern, text): for i in range(len(text)): m = match(pattern, text[i:]) if : return m def match(pattern, text): remainders = matchset(pattern, text) if remainders: shortest = min(remainders, key=len) return def components(pattern): x = pattern[1] if len(pattern) > 1 else None y = pattern[2] if len(pattern) > 2 else None return pattern[0], x, y
def matchset(pattern, text): elif 'seq' == op: return set(t2 for t1 in matchset(x, text) for t2 in matchset(y, t1)) def seq(x, y) return lambda text: set().union(*map(y, x(text))) def alt(x, y) return lambda text: x(text) | y(ext)
def genseq(x, y, Ns): Nss = range(max(Ns)+1) return set(m1 + m2 for m1 in x(Nss) for m2 in y(Nss) if len(m1 + m2) in Ns)
Compile word
def compile_word(word): if word.isupper(): terms = [('%s*%s' % (10**i, d)) for (i, d) in enumerate(word[::-1])] return '(' + '+'.join(terms) + ')' else: return word
Regular Expression
->find substring string
ex. s = ‘some long thing with words’
s.find(‘word’)
‘baa*!’
* a*
? a?
. a.
def search(pattern, text): if pattern.startswitch('^'): return match(pattern[l:], text) else: return match('.*' + pattern, text) def match(pattern, text): if pattern == '': return True elif pattern == '$': return (text == '') elif len(pattern) > 1 and pattern[1] in '*?': else: return (match1(pattern[0], text) and match(pattern[1:], text[1:]))
Estimating Runtime
import itertools houses = [1, 2, 3, 4, 5] orderings = list(itertools.permutation(houses)) for (red, green, ivory, yellow, blue) in orderings: for (Englishman, Spaniard, Ukranian, Japanese, Norwegian) in orderings: for (dog, snails, fox, horse, ZEBRA) in orderings: for (coffee, tea, milk, oj, WATER) in orderings: for (oldGold, kools, Chesterfields, LuckyStrike, Parliaments) in orderings:
def zebra_puzzle(): houses = first, _, middle, _, _ = [1, 2, 3, 4, 5] orderings = list(itertools.permutations(houses)) return next((WATER, ZEBRA)
import time def t(): t0 = time.clock() zebra_puzzle() t1 = time.clock() return t1-t0 print t() def timecall(fn, *args): t0 = time.clock() result = fn(*args) t1 = time.clock() return t1-t0
def timecall(fn, *args): t0 = time.clock() result = fn(*args) t1 = time.clock() return t1-t0 def timedcalls(n, fn, *args): times = [timedcall(fn, *args)[0] for _ in range(n)] return min(times), average(times), max(times) def average(numbers): return sum(numbers) / float(len(numbers))
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)
def ints(start, end):
i = start
while i <= end
yield i
i = i + 1
[/python]
[python]
def all_ints():
"Generate integers in the order 0, +1, -1, +2, -2, +3, -3,..."
yield 0
for i in ints(1):
yield +i
yield -i
[/python]
[python]
import string, re
def valid(f):
try:
return not re.search(r'\b0[0-9]', f) and eval(f) is True
except ArithmeticError:
return False
[/python]
[python]
import string, re
def solve(formula):
def valid(f):
try:
return not re.search(r'\b0[0-9]', f) and eval(f) is True
except ArithmeticError:
return False
[/python]