Category: algorithm

def count(n):
	return n * (n-1)

def clique(n):
	print "in a clique..."
	for j in range(n):
		for i in range(j):
			print i, "is friends with", j

product is divisible by 5.
361 636 277 129 434 577 796 596 727 566
156 109 714 716 546 979 366 766 137 243
331 999 922 304 657 314 634 303 677 597
363 174 431 193 361 677 403 926 279 692
749 401 346 202 763 314 333 244 796 697
674 651 517 349 337 667 617 464 379 793
542 464 962 146 946 199 302 699 606 126
519 203 137 517 146 724 696 699 747 663
126 247 469 953 396 502 562 647 364 214
346 646 331 426 763 291 557 764 939 656
753 561 797 224 537 361 263 493 196 162
362 102 629 936 663 279 966 241 907 677
945 416 122 563 667 394 654 592 977 177
666 199 463 561 954 924 991 363 754 754
199 451 796 566 629 651 517 167 704 749
622 299 466 559 973 243 639 276 603 753

def make_link(G, node1, node2):
	if node1 not in G:
		G[node1] = {}
	(G[node1])[node2] = 1
	if node2 not in G:
		G[node2] = {}
	(G[node2])[node2] = 1
	return G

a_ring = {}

n = 5

for i in range(n):
	make_link(a_ring, i, (i+1)%n)
print len(a_ring)
print sum(len(a_ring[node]) for node in a_ring.keys())/2
print a_ring

import math

def make_link(G, node1, node2):
	if node1 not in G:
		G[node1] = {}
	(G[node1])[node2] = 1
	if node2 not in G:
		G[node2] = {}
	(G[node2])[node1] = 1
	return G

G = {}

n = 256
side = int(math.sqrt(n))

for i in range(side):
	for j in range(side):
		if i < side-1: make_link(G, (i,j), (i+1, j))
		if j < side-1: make_link(G, (i,j), (i, j+1))

print len(G)
print sum([len(G[node]) for node in G.keys()])/2

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)

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)

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

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]

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]

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]

def findtags(text):
	parms = '(\w+\s*=\s*"[^"]*"\s*)*'
	tags = '(<\s*\w+\s*'+ parms + '\s*/?'>)'
	return re.findall(tags, text)

ta_data = [('peter', 'usa', 'cs262'),
			('Andy', 'usa', 'cs212'),
			('Sarah', 'England', 'cs101'),
			('Gundega', 'Latvia', 'cs373'),
			('Job', 'usa', 'cs387'),
			('Sean', 'usa', 'cs253')]

ta_facts = [name + ' lives in ' + country + ' and is the TA for ' +
			course for name, country, course in ta_data]

for row in ta_facts:
	print  row

ta_data = [('peter', 'usa', 'cs262'),
			('Andy', 'usa', 'cs212'),
			('Sarah', 'England', 'cs101'),
			('Gundega', 'Latvia', 'cs373'),
			('Job', 'usa', 'cs387'),
			('Sean', 'usa', 'cs253')]

ta_facts = [name + ' lives in ' + country + ' and is the TA for ' +
			course for name, country, course in ta_data]
remote_ta_facts = [name + ' lives in ' + country + ' and is the TA for ' +
			course for name, country, course in ta_data if country != 'usa']

ta_300 = [name + 'is the TA for ' course for name, country, course in ta_data if course.finde('cs3') != -1]

for row in ta_facts:
	print  row

import itertools

def best_hand(hand):
	return max(itertools.combinations(hand, 5), key=hand_rank)

def test_best_hand():
	assert (sorted(best_hand("6c 7c 8c 9c tc sc js".split()))
		==['6c', '7c', '8c', '9c', 'tc'])
	assert (sorted(best_hand("td tc th 7c 7d 8c 8s".split()))
		==['8c', '8s', 'tc', 'td', 'th'])
	assert (sorted(best_hand("td tc th 7c 7d 7s 7h".split()))
		==['7c', '7d', '7h', '7s', 'td'])
	return 'test_best_hand passes'

print test_best_hand

booge[1].add('red')
booge[1].color='red'
red = 1

houses = [1, 2, 3, 4, 5]
orderings = F(houses)
for(red, green, ivony, yellow, blue) in orderings:

hello my luft ballons
[(“word-element”, “hello”),
(“word-element”,”my”),
(“javascript-element”), “document.write(99);”)
(“word-elment”, “luftballons”),
]

def interpret(trees):
	for tree in trees:
		treetype = tree[0]
		if treetype == "word-element":
			graphics.word(node[1])
		elif treetype == "javascript-element":
			jstext = tree[1]
			jslexer = lex.lex(module=jstokens)
			jsparser = yacc.yacc(module=jsgrammar)
			jstree = jsparser.parse(jstext,lexer=jslexer)
			result = jsinterp.interpret( jstree )
			graphics.word( result )

def env_lookup(vname, env):
	if vname in env[1]:
		return (env[1])[vname]
	elif env[0] == None:
		return None
	else:
		return env_lookup(vname, env[0])

var a = 1;
function mistletue(baldr){
	baldr = baldr + 1;
	a = a + 2;
	baldr = baldr + a;
	return baldr;
}
write (mistletue(5));

def optimize(tree):
	etype = tree[0]
	if etype == "binop":
		a = tree[1]
		op = tree[2]
		b = tree[3]
		if op == "*" and b == ("number","1"):
			return a
		return tree

def remove_html_markup(s):
	tag = False
	out = ""

	for c in s:
		if c == '<':
			tag = True
		elif c == '>':
			tag = False
		elif not tag:
			out = out + c

	return out
print remove_html_markup("<b>foo</b>")