View Sort 3 numbers
import random
a,b,c = [random.randint(-100,100) for i in range(3)]
print a,b,c
#the actual solution
mx = max(a,max(b,c)) # max of a,b,c
mn = -max(-a,max(-b,-c)) # min of a,b,c, lol! :D
mid = a+b+c-mn-mx # middle term
print mn,mid,mx
View Adjacency List
import fileinput
# add_edge (u -> v) with weight w to graph g
def add_edge(graph,u,v,w):
if u in graph: #vertex u already in graph?
l = graph[u] #get list of neighbours
else:
graph[u] = l = list() #insert u into graph and assign an empty list of neighbours
l.append((v,w)) #append tuple (v,w) into the neighbour list
View Find first Gap - Linear
def find_first_gap_linear(lst):
for i in xrange(len(r)-1):
if r[i] + 1 != r[i+1]:
return r[i] + 1
return -1
View Find Gap - Binary Search
View Fermat Test
def fermatPass(n):
return n > 1 and ( n == 2 or ( n % 2 != 0 and pow( random.randint( 1, n - 1 ), n - 1, n ) == 1 ) )
def fermatTest(n,k = 10):
return all( fermatPass( n ) for i in xrange(k) )
View Miller Rabin Primality Test
def millerRabin(n, k = 5):
if n <= 3 or n % 2 == 0: return n == 2 or n == 3
d = n - 1
s = 0
while d > 0 and d % 2 == 0:
d = d / 2
s = s + 1
def millerRabinPass(a, s, d, n):
View Lucas Lehmer Primality Test
def lucasLehmerTest(p): #checks if 2^p - 1 is a prime (also called a mersenne prime)
if p % 2 == 0 and not isPrime(p): return False
s = 4
M = (1 << p) - 1
for _ in xrange(p - 2):
s = ((s * s) - 2) % M
return s == 0
def isPrime(n):
if n <= 3 or n % 2 == 0 or n % 3 == 0: return n == 2 or n == 3
View Stack with Min()
class StackMin extends Stack {
private Stack minStack;
public StackMin(int size) {
super(size);
minStack = new Stack(size);
}
@Override
View PriorityQueue
import random,Queue
pq = Queue.PriorityQueue()
for q in range(10):
p = random.randint(0,100)
print "Inserting %d with priority %d" % (q,p)
pq.put((p,q))
while not pq.empty():
print pq.get()
raw_input()
View pqueue
import heapq as hp
class pqueue:
def __init__(self, minheap = True):
self.heap = []
self.mul = 1 if minheap else -1
self.count = 0
def size(self):