Category: algorithm

what to do about them
-> Theoretical Computer Science

・Recognize
・Understand
・Navigate

minimum_devices = number of communication centers
for each assignment of (0,1) to the communication centers:
	if assignment is valid
		number_of_devices = number of "l"s in assignment
		minimum_devices = min(minimum_devices,number_of_devices)

largest_group = 0
for each assignment of (0, 1) to the genes:
	if assignment is valid:
		group_size = number of "1"s in assignment
		largest_group = max(largest_group, group size)

def shortest_dist_node(dist):
	best_node = 'undefined'
	best_value = 1000000
	for v in dist:
		if dist[v] < best_value:
			(best_node, best_value) = (v, dist[v])
	return best_node

def dijkstra(G,v):
	dist_so_far = {}
	dist_so_far[v] = 0
	final_dist = {}
	while len(final_dist) < len(G):
		w = shortest_dist_node(dist_so_far)
		final_dist[w] = dist_so_far[w]
		del dist_so_far[w]
		for x in G[w]:
			if x not in dist_so_far:
				dist_so_far[x] = final_dist[w] + G[w][x]
			elif final_dist[w] + G[w][x] < dist_so_far[x]:
				dist_so_far[x] = fianl_dist[w] + G[w][x]
	return fianl_dist

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

L = [2, 3, 2, 3, 2, 4]

def mean(L):
	total = 0
	for i in range(len(L)):
		total += L[i]
	return (0.0+total)/len(L)

print mean(L)

define max value on the list

def max(L):
	max_so_far = L[0]
	for i in range(len(L)):
		if L[i] > max_so_far: max_so_far = L[i]
    return max_so_far

def max(L)

search most popular name in US in 1995

f = open("yob1995.txt", "r")
maxname = "none"
maxval = 0
max2name = "none"
max2val = 0
for line in f:
	(name, sex, count) = line.rsplit(",")
	count = int(count)
	if sex == "F":
		if count > maxval:
			max2name = maxname
			max2val = maxval
			maxval = count
			maxname = name
		elif count > max2val:
			max2name = name
			max2val = count
print maxname, max2name
print maxval, max2val

L = [31, 45, 91, 51, 66, 82, 28, 33, 11, 89, 84, 27, 36]

def partition(L, v):
    smaller = []
    bigger = []
    for val in L:
    	if val < v: smaller += &#91;val&#93;
    	if val > v: bigger += [val]
    return smaller + [v] + bigger

print partition(L,84)

L = [31, 45, 91, 51, 66, 82, 28, 33, 11, 89, 84, 27, 36]

def partition(L, v):
    smaller = []
    bigger = []
    for val in L:
    	if val < v: smaller += &#91;val&#93;
    	if val > v: bigger += [val]
    return (smaller + [v] + bigger)

def top_k(L, k):
	v = L[random.randrange(len(L))]
	(left,middle,right) = partition(L, y)
	if len(left) == k: return left
	if len(left)+1 == k: return left+[v]
	if len(left) > k: return top_k(left,k)
	return left+[v]+top_k(right,k-len(left)-1)

print top_k(L,5)

time1 = time.time()
charG = {}
for char1 in characters:
	for book in marvelG[char1]:
		make_link(charG, char1, char2)
time2 = time.time()
print "time to compute strengths: ", time2-time1

time1 = time.time()
k = 10
heap = []
for char1 in charaters:
	for char2 in charG[char1]:
		if characters[char1] < characters&#91;char2&#93;:
			if len(heap) < k:
				insert_heap(heap, (charG&#91;char1&#93;&#91;char2&#93;,(char1, char2)))
			elif charG&#91;char1&#93;&#91;char2&#93; > val(heap[0]):

speed, weight lifespan brain
animals = [("dog", 46, 35, 13, 280),
			("elephant", 30, 3500, 50, 6250),
			("frog", 5, 0.5, 8, 3),
			("hippopotamus", 45, 1600, 45, 573),
			("horse", 40, 385, 30, 642),
			("human", 27, 80, 78, 2000),
			("lion", 50, 250, 30, 454),
			("mouse", 8, 0.025, 2, 0.625),
			("rabbit", 25, 4, 12, 40),
			("shark", 26, 230, 20, 92),
			("sparrow", 16, 0.024, 7, 2)]

def importance_rank(items, weight):
	names = [item[0] for item in items]
	scores = [sum([a*b for (a,b) in zip(item[1:], weights)]) for item in items]

	results = zip(scores,names)
	res2 = sorted(results)
	return res2

answer = importance_rank(animals, (2,3,7,1))

for i in range(len(answer)):
	print i, answer[i][1], "(", answer[i][0], ")"

def makeG(N):
	if n == 1:
		return <a single node>
	g1 = makeG(n / 2)
	g2 = makeG(n / 2)
	for i in range(log(n)):
		i1 = <random node from g1 without replacement>
		i2 = <random node from g2 without replacement>
		make_link(G, i1, i2)
	return G

def mark_component(G, node, marked):
	marked[node] = True
	total_marked = 1
	for neighbor in G[node]:
		if neighbor not in marked:
			total_marked += mark_component(G, neighbor, marked)
	return total_marked

def check_connection(G, v1, v2):
	marked = {}
	mark_component(G, v1, marked)

def make_line(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

def test():
	edges = [('a', 'g'),('a', 'd'),('g', 'c'),('g', 'd'),
			('b', 'f'),('f', 'e'),('e', 'h')]
	G = {}
	for v1, v2 in edges:
		make_link(G, v1, v2)
	assert check_connection(G, "a", "c") == True
	assert check_connection(G, 'a', 'b') == False

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

def clique(n):
G = {}

for i in the edges
for j in range(n):
if i

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