algorithm – Page 8 – ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

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]

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)

List power

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:

parsing tree

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

Technical Process

1. Clarifying the Question
2. Confirming Input
3. Test Cases
4. Brainstorming
5. Runtime Analysis
6. Coding
7. Debugging
8. Wrap-up

history of software bugs
http://archive.wired.com/software/coolapps/news/2005/11/69355?currentPage=all