Category: algorithm

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]

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

Binary Tree

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree(object):
    def __init__(self, root):
        self.root = Node(root)

    def search(self, find_val):
        return self.preorder_serach(tree.root, find_val)

    def print_tree(self):
        return self.preorder_print(tree.root, "")[:-1]

    def preorder_search(self, start, find_val):
        if start:
            if start.value == find_val:
                return True
            else
                return self.preorder_search(start.left, find_val) or self.preorder_search(start.right, find_val)
            return False                

    def preorder_print(self, start, traversal):
        if start:
            traversal += (str(start.value) + "-")
            traversal = self.preorder_print(start.left, traversal)
            traversal = self.preorder_print(start.right, traversal)
        return traversal

Binary Search Tree

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST(object):
    def __init__(self, root):
        self.root = Node(root)

    def insert(self, new_val):
        self.insert_helper(self.root, new_val)

    def insert_helper(self, current, new_val):
        if current_value < new_val:
            if current.right:
                self.insert_helper(current.right, new_val)
            else:
                current.right = Node(new_val)

        else:
            if current.left:
                self.insert_helper(current.left, new_val)
            else:
                current.left = Node(new_val)

    def search(self, find_val):
        return self.search_helper(self.root, find_val)

    def search_helper(self, current, find_val):
        if current:
            if current.value == find_val:
                return True
            elif current.value < find_val:
                return self.search_helper(current.right, find_val)
            else:
                return self.search_helper(current.left, find_val)
        return False

graph(network): how things is connect one another which is similar to tree.

0[0, 1, 0, 0]
1[1, 0, 1, 1]
2[0, 1, 0, 1]
3[0, 1, 1, 0]

binary search

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
        return found

recursion

function recursive(input):
    if input <= 0
        return input
    else
        output = recursive(input - 1)
        return output

fib

function getFib(position){
    if (position == 0) { return 0; }
    if (position == 1) { return 1; }
    var first = 0,
        second = 1,
        next = first + second;
    for (var i = 2; i < position; i++){
        first = second;
        second = next;
        next = first + second;
    }
    return next;
}

def get_fib(position):
    if position == 0 or position == 1:
        return position
    return get_fib(position -1) + get_fib(position -2)

margin sort efficiency
log(n)
1, 4(log n1),8(log n3), 16(log n4)

ease yourself by commic
https://xkcd.com/1185/

margin sort text
http://algs4.cs.princeton.edu/22mergesort/

quick sort

def quicksort(array):
    if len(array) < 1:
        return array
    pivot = array[0]
    left = []
    right = []
    for x in range(1, len(array)):
        if array[x] <= pivot:
            left.append(array[x])
        else:
            right.append(array[x])
        left = quicksort(left)
        right = quicksort(right)
        foo = [pivot]
        return left + foo + right

list: A B C
set: C A B

Jaccard index

The Jaccard index, also known as the Jaccard similarity coefficient (originally coined coefficient de communauté by Paul Jaccard), is a statistic used for comparing the similarity and diversity of sample sets.

Jaccard(A,B)=|A∩B| / |A∪B|