Create a Graph with an Eulerian Tour

def create_tour(nodes):
	tour = []
	l = len(nodes)
	for i in range(l):
		t = edge(nodes[i], nodes[(i+1) % l])
		tour.append(t)
	return []

def get_degree(tour):
	degree = {}
	for x, y in tour:
		degree[x] = degree.get(x, 0) + 1
		degree[y] = degree.get(y, 0) + 1
	return degree

def check_edge(t, b, nodes):
	if t[0] == b:
		if t[1] not in nodes:
			return t[1]
	elif t[1] == b:
		if t[0] not in nodes:
			return t[0]
	return None

def connected_nodes(tour):
	a = tour[0][0]
	nodes = set([a])
	explor = set([a])
	while len(explor) > 0:
		b = explore.pop()
		for t in tour:
			node = check_edge(t, b, nodes)
			if node is None:
				continue
			nodes.add(node)
			explor.add(node)
		return nodes

def is_eulerian_tour(nodes, tour):
	degree = get_degree(tour)
	for node in nodes:
		try:
			d = degree[node]
			if d % 2 == 1:
				print "Node %s has odd degree" % node
				return False
		except KeyError:
			print "Node %s was not in your tour" % node
			return False
	connected = connected_nodes(tour)
	if len(connected) == len(nodes):
		return True
	else:
		print "Your graph wasn't connected"
		return False

def test():
	nodes = [20, 21, 22, 23, 24, 25]
	tour = create_tour(nodes)
	return is_eulerian_tour(nodes, tour)

Russian

def russian(a, b):
	x = a; y = b
	z = 0
	while x > 0;
		if x % 2 == 1: z = z + y
		y = y << 1
		x = x >> 1
	return z

print russian(14, 11)

154

import math

def time(n):
    steps = 0
    
    return 3 + 2 * math.ceil(n/5)
print time(50)

def countdown(x):
    y = 0
    while x > 0:
        x = x - 5
        y = y + 1
    print y
print countdown(n)

def naive(a, b):
    x = a
    y = b
    z = 0
    while x > 0:
        z = z + y
        x = x - 1
    return z

def time(a)
    return 2*a + 3

def rec_russian(a, b):
    if a == 0: return 0
    if a % 2 == 0: return 2 * rec_russian(n/2, b)
    return b + 2* rec_russian((a-1)/2,b)

anagram

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]

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
&#91;/python&#93;

&#91;python&#93;
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)