Skip to content

Instantly share code, notes, and snippets.

View st0le's full-sized avatar
💭
nohello

Gaurav Kamath st0le

💭
nohello
View GitHub Profile
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
@st0le
st0le / Adjacency List
Last active December 16, 2015 15:28
Representing Graphs in Python
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
@st0le
st0le / Find first Gap - Linear
Created April 26, 2013 03:31
Find first missing number in a strictly increasing array. (where X > A[0])
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
@st0le
st0le / Find Gap - Binary Search
Created April 26, 2013 05:00
Find Gap in Sorted Array - Binary Search
@st0le
st0le / Fermat Test
Last active December 16, 2015 17:40
Fermat Primality 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) )
@st0le
st0le / Miller Rabin Primality Test
Created April 27, 2013 05:37
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):
@st0le
st0le / Lucas Lehmer Primality Test
Last active December 16, 2015 17:40
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
@st0le
st0le / Stack with Min()
Created April 28, 2013 19:34
Stack with Min()
class StackMin extends Stack {
private Stack minStack;
public StackMin(int size) {
super(size);
minStack = new Stack(size);
}
@Override
@st0le
st0le / PriorityQueue
Created May 5, 2013 05:54
Using PriorityQueue from Queue Module
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()
@st0le
st0le / pqueue
Created May 5, 2013 20:32
min/max pqueue implementation with tie breaker
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):