Algorithms for fun

algo.txt

print("hello")

A = [-1,1,10,0,-10,3.5]
def insertion_sort(A):
    len_A = len(A)
    for i in range(1,len_A):
        j = i
        while(j >0 and A[j-1] > A[j]):
            A[j-1],A[j] = A[j], A[j-1]
            j = j-1
    return A


def tHanoi(N):
    Beg = 1;
    Aux = 2;
    End = 3;
    
    def solve(N,Beg,Aux,End):
        if N==1: print(Beg," -> ", End)
        else:
            solve(N-1, Beg, End, Aux)
            solve(1, Beg, Aux, End)
            solve(N-1, Aux, Beg, End)
    solve(N,Beg,Aux,End)


def bsearch(A,val):
    if len(A)<=0:return False
    mid = int((0+len(A)-1)/2)
    if A[mid] == key:return True 
    if key < A[mid]:return bsearch(A[:mid],key)
    elif key > A[mid]:return bsearch(A[mid+1:],key)
A = sorted(A)
print(bsearch(A,val))

print(insertion_sort(A),10)

def merge(left,right):
    i,j = 0,0
    result = []
    while( i < len(left) and j < len(right)):
        if(left[i] < right[j])
            result.append(left[i])
            i++
        else: 
            result.append(right[j])
            j++
    result+= left[i:]
    result+= right[j:]
    return result
    
def mergeSort(A):
    if len(A) <= 1:return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:]))
    

#QuickSort
def partition(A,l,r,rand_pivot):
    
    A[rand_pivot],A[l] = A[l],A[rand_pivot]
    pivotElement = A[l]
    i = l + 1
    
    for j in range(l+1, r+1):
        if A[j] <= pivotElement:
            A[i],A[j] = A[j], A[i]
            i+=1
    
    A[l],A[i-1] = A[i-1], A[l]
    return i-1


def quickSort(A,l,r):
    if (l < r ) : 
        rand_pivot = random.randint(l, r)
        pivot = partition(A,l,r,rand_pivot)
        #Something fishy is going at pivot index
        quickSort(A,l,pivot-1)
        quickSort(A,pivot+1,r)
        
quickSort(A,0,len(A)-1)
#I still need to study about the pivot elements
#that is being produced here - 


#kth largest / smallest element
def quickSelect(A,l,r,k):
    if l == r:return A[l]
    pivotLoc = partition(A,l,r)
    if k == pivotLoc : return A[k]    
    else:
        if k < pivotLoc:
            return quickSelect(A,l,pivotLoc-1,k)
        if k > pivotLoc:
            return quickSelect(A,pivotLoc+1,r,k)
        
def qS(A,k):
    print(quickSelect(A,0,len(A)-1,k))

#bfs and dfs
graph = {'A': set(['B', 'G', 'D']),
         'B': set(['E','F']),
         'C': set(['H']),
         'D': set(['F']),
         'E': set(['G']),
         'F': set(['C']),
         'G': set(['']),
         'H': set([''])}

def bfs(graph,start):
    explored = []
    queue = [start]
    while queue:
        node = queue.pop(0)
        if node not in explored:
            explored.append(node)
            neighbours = sorted(graph[node])
            for neighbour in neighbours:
                if neighbour:queue.append(neighbour)
    return explored

def dfs(graph,start):
    explored = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in explored:
            explored.append(node)
            neighbours = sorted(graph[node])
            for neighbour in neighbours:
                if neighbour:stack.append(neighbour)
    return explored
    
#recursive dfs
explored = []
def dfs_recur(graph, start):
        if start == '': return 
        explored.append(start)
        neighbours = graph[start]
        for neighbour in neighbours:
            if neighbour not in explored:
                dfs_recur(graph,neighbour)

dfs_recur(graph_1,'A')
print(explored)

#simplified dijkstra
graph = {'s': {'v':1,'w':4 },
         'v': {'w':2,'t':6},
         'w': {'t':3},
         't': {}
         }

def dj(graph, start):

    dist = {}
    prev = {}
    for key in graph.keys():
        dist[key] = float('inf')
        prev[key] = None
        
    dist[start] = 0
    prev[start] = (None,0)
    while dist.keys():
        u = min(dist, key = dist.get)
        print("min key is ",u)
        print(dist)
        
        for v in graph[u]:
            alt = dist[u] + graph[u][v]
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = (u,alt)
        dist.pop(u)
        
    return prev
        
print(dj(graph,'s'))
#It can be improvised - but lets see.

##################################
#Kosaraju's algorithm#
from collections import defaultdict
class Graph:
    def __init__(self,vertices):
        self.V = vertices
        self.graph = defaultdict(list)
        self.stack = []
    def addEdge(self,u,v):
        self.graph[u].append(v)

    def dfs(self,gr,u,visited):
        if u is None:return
        visited.append(u)   
        print(u)
        neighbors = gr[u]
    
        for neighbor in neighbors:
            if neighbor not in visited:
                self.dfs(gr, neighbor, visited)
        self.stack.append(u)

    def graphT(self):
        g = Graph(self.V)
        for i in self.graph:
            for j in self.graph[i]:
                g.addEdge(j,i)
        return g
    
    def scc(self,u): 
        visited = []
        
        for u in range(0,self.V):
            if u not in visited:
                self.dfs(self.graph,u,visited)
        print(self.stack)
        
        gT = self.graphT()
        
        visited = []
        while self.stack:
            u = self.stack.pop()
            if u not in visited:
                gT.dfs(gT.graph,u,visited)
                print("")
        print(visited)

g = Graph(9)
g.addEdge(0,1)
g.addEdge(1,2)
g.addEdge(2,3)
g.addEdge(2,4)
g.addEdge(3,0)
g.addEdge(4,5)
g.addEdge(5,6)
g.addEdge(6,4)
g.addEdge(7,6)
g.addEdge(7,8)
g.addEdge(8,None)

g.scc('0')

###########################################
#Kosaraju's algorithm minimized and cleaned#
from collections import defaultdict

graph = defaultdict(list)

def addEdge(graph,u,v):
    graph[u].append(v)

vertices = 9
addEdge(graph,1,2)
addEdge(graph,0,1)
addEdge(graph,1,2)
addEdge(graph,2,3)
addEdge(graph,2,4)
addEdge(graph,3,0)
addEdge(graph,4,5)
addEdge(graph,5,6)
addEdge(graph,6,4)
addEdge(graph,7,6)
addEdge(graph,7,8)
addEdge(graph,8,None)
print(graph.keys())


#Graph reversal
def graphT(graph):
    g = defaultdict(list)
    for i in graph:
        for j in graph[i]:
            addEdge(g,j,i)
    return g

gT = graphT(graph)


#Depth first search
stack = []
visited = []
def dfs(gr,u):
    if u is None:return
    visited.append(u)
    neighbors = gr[u]
    for neighbor in neighbors:
        if neighbor not in visited:
            dfs(gr, neighbor)
    stack.append(u)


#Run DFS on each of the vertices
for u in range(0,vertices):
    if u not in visited:
        dfs(graph,u)

visited = []

#Get elements from the stack
#and do a DFS on each of the
#elements
while stack:
    u = stack.pop()
    if u not in visited:
        dfs(gT,u)
print(visited)


##############################
#heapsort
def heapify(arr,n,i):
   largest = i
   l = 2 *i +1 
   r = 2 *i + 2
   
   if l < n and arr[largest] < arr[l]:
       largest = l 

   if r < n and arr[largest] < arr[r]:
        largest = r
   
   if largest != i:
       arr[i], arr[largest] = arr[largest],arr[i]
       
       heapify(arr,n,largest)
       
def heapsort(arr):
    n = len(arr)
    for i in range(n,-1,-1):
        heapify(arr,n,i)

    for i in range(n-1,0,-1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr,i,0)
    return arr
##################################################
#Things need to be done
def bst(A,key):
    if len(A)<=0:return False
    mid = int((0+len(A)-1)/2)
    if A[mid] == key:return True 
    if key < A[mid]:return bst(A[:mid],key)
    elif key > A[mid]:return bst(A[mid+1:],key)
    

#print(bst(A,0))


A = [40,60,10,30,20,50,100]
A = heapsort(A)
print(A)
class Node:
    def __init__(self,key):
        self.val = key
        self.left = None
        self.right = None

def insert_1(root, node):
    if root is None:
        root = node
    
    else:
        if root.val < node.val:
            if root.right is None:
                root.right = node
            else: insert(root.right, node)
        
        else:
            if root.left is None:
                root.left = node
            else:
                insert(root.left, node)

def insert(node, key):
    if node is None:
        return(Node(key))
    if  key < node.val:
        node.left = insert(node.left, key)
    if key >= node.val:
        node.right = insert(node.right, key)
    return node

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)
r = None
r = insert(r,4)
r = insert(r,0.5)
r = insert(r,10)
r = insert(r,-1)
r = insert(r,0)

r = insert(r,140)
inorder(r)
def minVal(root):
    if root == None:return None
    #if root.left == None:return root.val
    if root.left == None:return root
    return minVal(root.left)

def maxVal(root):
    if root == None:return None
    #if root.right == None:return root.val
    if root.right == None:return root
    return minVal(root.right)

#print("Minimum value is: ")
#print(minVal(r))


    
def bst(root,key):
    if root == None:return Node(None)
    if root.val == key: return root
    if key < root.val:return bst(root.left,key)
    elif key > root.val:return bst(root.right,key)

def successor(root,key):
   
    node = bst(root,key)
    if node.right != None:
        return minVal(node.right)
    #successor node is the key 
    #that is being looked for
    succ = node
    
    if succ.val == None:return None
    
    if node.right is None:
        while root: 
            #this is similar to binary search
            #expect when the key is found 
            #break is called 
            if node.val > root.val:
                root = root.right
            elif node.val < root.val:
                succ = root
                root = root.left
            
            else: break
                
    return succ.val

def predecessor(root,key):
   
    node = bst(root,key)
    if node.left != None:
        return maxVal(node.left)
    #predecessor node is the key 
    #that is being looked for
    pred = node
    
    if pred.val == None:return None
    
    if node.left is None:
        while root: 
            #this is similar to binary search
            #expect when the key is found 
            #break is called 
            if node.val > root.val:
                pred = root
                root = root.right
            elif node.val < root.val:
                root = root.left
            
            else: break
                
    return pred.val



print("Predecessor is:")
#print(minVal(n.right))
p = (predecessor(r,6))
print(p)


def delete(root,key):
    if root == None:return root
    if key < root.val:
        root.left = delete(root.left, key)
    elif key> root.val:
        root.right = delete(root.right,key)
    else:
        print("Meeeee")
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp
        temp = minVal(root.right)
        
        root.val = temp.val
        root.right = delete(root.right, temp.val)
        
    return root

foo = delete(r,30)
inorder(foo)   
  
  
########################################################
#karatsuba
from math import *

def karat(x,y):
    
    if len(str(x)) == 1 or len(str(y)) == 1:
        return x*y

    m = max(int(log10(x)+1), int(log10(y)+1))
    
    m2 = m//2
    a, b = divmod(x,10**m2)
    c, d = divmod(y,10**m2)
    
    
    z0 = karat(b,d)
    z1 = karat((a+b),(c+d))
    z2 = karat(a,c)
    
    return (z2*10**(2*m2))+((z1-z2-z0)*10**(m2))+(z0)

#####################################################
#Counting inversion
def mergeCount(left,right, countInv):
    i,j = 0,0
    result = []
    while( i < len(left) and j < len(right)):
        if(left[i] < right[j]):
            result.append(left[i])
            i+=1
        else: 
            countInv.append(len(left)-i)
            result.append(right[j])
            j+=1
    result+= left[i:]
    result+= right[j:]
    return result

countInv = []
def mergeSortCount(A):
    if len(A) <= 1:return A
    m = len(A)//2
    return mergeCount(mergeSortCount(A[:m]),mergeSortCount(A[m:]), countInv)