<jupyter_start><jupyter_text>Greedy Algorithms<jupyter_code>test_adj_list = [[0, 5, 1.0], [5, 0, 1.0], [1, 7, 2.0], [2, 6, 2.0], [2, 7, 2.0], [6, 2, 2.0], [7, 1, 2.0], 
                 [7, 2, 2.0], [0, 6, 3.0], [1, 4, 3.0], [3, 9, 3.0], [4, 1, 3.0], [4, 5, 3.0], [4, 8, 3.0], 
                 [5, 4, 3.0], [5, 6, 3.0], [6, 0, 3.0], [6, 5, 3.0], [8, 4, 3.0], [9, 3, 3.0], [0, 2, 4.0], 
                 [2, 0, 4.0], [5, 7, 4.0], [7, 5, 4.0], [0, 3, 5.0], [3, 0, 5.0], [0, 9, 8.0], [2, 8, 8.0], 
                 [3, 4, 8.0], [4, 3, 8.0], [8, 2, 8.0], [9, 0, 8.0], [5, 8, 9.0], [8, 5, 9.0]]

import numpy as np
# Write kruskal's and prim's for the adj list above to find the MST

class Kruskals_MST:
    def __init__(self, adj_list):
        self.adj_list = sorted(adj_list, key = lambda x: x[2]) # sort the original adj list
        self.vertices = set([i[0] for i in adj_list] + [i[1] for i in adj_list]) # all vertices in a set format
        self.parent = np.arange(len(self.vertices))
        self.ranking = np.zeros(len(self.vertices))
        
        
    def MST(self):
        MST_list = []
        i = 0
        while len(MST_list) < len(self.vertices) - 1 and i < len(self.adj_list):
            edge = self.adj_list[i]
            u, v, w = edge
            if self.find_parent(u) != self.find_parent(v):
                MST_list.append(edge)
                self.union_by_rank(self.parent[u], self.parent[v])
            i+= 1
        return MST_list
            
            
    def find_parent(self, vertex):
        if self.parent[vertex] == vertex:
            return vertex
        else:
            return self.find_parent(self.parent[vertex])
        
        
    def union_by_rank(self, u, v):
        if self.ranking[u] > self.ranking[v]:
            self.parent[v] = u
        elif self.ranking[v] > self.ranking[u]:
            self.parent[u] = v
        else:
            self.parent[v] = u
            self.ranking[u] += 1

test_kruskals = Kruskals_MST(test_adj_list)        
results = test_kruskals.MST()
print(np.sum([i[2] for i in results]))
print(results)
        
def prims(vertex , adj_list):
    MST = []
    edges = []
    vertices = set([i[0] for i in adj_list] + [i[1] for i in adj_list])
    visited = [vertex]
    while len(MST) < len(vertices) - 1:
        for i in range(len(adj_list)):
            u, v, w = adj_list[i]
            if u == vertex and w != 0:
                edges.append(adj_list[i])
            
        min_edge = [None, None, np.inf]
        for i in range(len(edges)):
            if edges[i][2] < min_edge[2] and edges[i][1] not in visited:
                min_edge = edges[i]
                vertex = edges[i][1]
            
        MST.append(min_edge)    
        visited.append(vertex)
        edges.remove(min_edge)
    return MST   
            
results = prims(0, test_adj_list)        
print(results)  
print(np.sum([i[2] for i in results]))
# Create a directed graph to apply dijkstra's to find the SPT

import numpy as np
np.random.seed(0)
def test_graph(n): # n vertices
    test_graph_set = np.random.rand(n,n)*100
    # 0 the source so that the node is acyclic to itself 
    for i in range(n):
        test_graph_set[i][i] = np.inf
        # test_graph_set[i][:i] = np.inf  # unmark if a tree structure is needed
    test_graph_set = np.around(test_graph_set, decimals = 2)
    return test_graph_set

test_set = test_graph(10) 
print(test_set[:10][:10])
graph = test_set

# Dijkstra's algorithm to find the SPT:

import numpy as np
def dijkstras(source, graph):
    visited = [False] * len(graph)
    distances = [np.inf] * len(graph)
    distances[source] = 0
    # for all vertices do the following
    for i in range(len(graph)):
        min_dist = np.inf
        # find the min distance index if it is not visited
        for i in range(len(distances)):
            if visited[i] == False and distances[i] < min_dist:
                min_dist = distances[i]
                min_at_vertex = i
        visited[min_at_vertex] = True   
        #print(min_at_vertex, visited)
        # find the shortest path and save it to the distance array
        for i in range(len(distances)):
            if visited[i] == False and graph[min_at_vertex][i] > 0:
                if distances[i] > graph[min_at_vertex][i] + distances[min_at_vertex]:
                    distances[i] = graph[min_at_vertex][i] + distances[min_at_vertex]
        
    return np.around(distances, decimals = 2)
    
    
dijkstras(0, test_set)
# Activity Selection Problem
# Ex: Consider the following 3 activities sorted by finish time. start = {10, 12, 20} finish =  {20, 25, 30}
# The set of activities that can be executed by one person is in these indices: {0, 2}

s = [0, 1, 3, 5, 5, 8]
f = [2, 4, 6, 7, 9, 9]

def activity_selection(s , f): 
    s.sort()
    f.sort()
    # The first activity is always selected since we will check if s[i] > f[j] for later activites
    activities = [0]
    i = 0  
    j = 0
    n = len(s)
    while i < n and j < n:
        if s[i] >= f[j]: # to start a new activity, the previous activity has to be finished. 
            activities.append(i) 
            j = i 
        i += 1
    return activities


activity_selection(s , f) 

# Find the Minimum Number of Platforms Required for a Railway / Bus Station
# Inbound = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}    
# Outbound = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
# Output: 3.There are at-most three trains at a time (time between 11:00 to 11:20)  
# 9:40 train is there until 12 , 9:50 train is there until 11:20, 11:00 train is the third train entering

def find_min_platform_needed(arr, dep): 
    assert(len(arr)== len(dep))
    n = len(arr)
    arr.sort() 
    dep.sort() 
    plat_needed = 0  # current number of platforms needed through first train to last train 
    min_platforms_needed = 0
    i = 0
    j = 0
    while (i < n and j < n): 
        if (arr[i] < dep[j]): 
            plat_needed+=1
            i+=1 
            if (plat_needed > min_platforms_needed):  
                 min_platforms_needed = plat_needed   
        else: 
            plat_needed-=1
            j+=1
          
    return min_platforms_needed # the minimum number of platforms to cover all these trips
  
# driver code 
  
arr = [900, 940, 950, 1100, 1500, 1800] 
dep = [910, 1200, 1120, 1130, 1900, 2000] 
find_min_platform_needed(arr, dep) 

# Remove Minimum coins such that absolute difference between any number of coins in the piles is less than K
# {1, 5, 1, 2, 5, 1}, there are 6 piles each containing the number of coins such as first pile has one, second five
# find the number of coins need to be removed such that the max difference between any pile will be K=3
# answer: remove 1 coin from two piles which are originally containing 5 coins. So, total 2 coins will suffice.

def minimum_coins(array, k):
    n = len(a)
    total_coins_to_remove = 0  
    smallest_coin_pile = min(a)
    for i in range(n): 
        diff = a[i] - smallest_coin_pile
        if (diff > k): 
            total_coins_to_remove += (diff - k) 
    return total_coins_to_remove
  
a = [1, 5, 1, 2, 5, 1]
k = 3
print(minimum_coins(a,k))


def number_of_coins_to_shave_off(array, k):
    min_of_the_array = min(array)
    largest_coin_allowed = min_of_the_array + k
    total_coins_to_be_removed = 0
    for i in range(len(array)):
        if array[i] > largest_coin_allowed:
            diff = array[i] - largest_coin_allowed
            total_coins_to_be_removed += diff  
    return total_coins_to_be_removed

print(number_of_coins_to_shave_off(a, k))
# how many toys can you buy with the prices cost = { 1, 12, 5, 111, 200, 1000, 10, 9, 12, 15 } with K dollars

def number_of_toys_for_K_dollars(array , K):
    count = 0
    sum_total = 0
    sorted_array = sorted(array)
    for i in range(len(sorted_array)):
        cost_of_current_item = sorted_array[i]
        remaining_money_in_pocket = K - sum_total
        if cost_of_current_item < remaining_money_in_pocket:
            count += 1
            sum_total += cost_of_current_item
    return count

test_array = [1, 12, 5, 111, 200, 1000, 10, 9, 12, 15]
print(sorted(test_array))
K = 50
print(number_of_toys_for_K_dollars(test_array, K))
        
    
def max_number_of_toys_for_K_dollars(array, K):
    sorted_array = sorted(array)
    sums = 0
    sum_array = []
    for i in range(len(sorted_array)):
        sums += sorted_array[i]
        sum_array.append(sums)
        if sum_array[i] > K: 
            return i
    
print(max_number_of_toys_for_K_dollars(test_array, K))
    
# Maximum difference if the items of the array can be increased or decreased by k units
# Input {1, 10, 14, 14, 14, 15} , k = 6  Output: Maximum difference is 5

def max_dif_in_array_with_k_add_or_subs(array, k):
    max_val = max(array)
    min_val = min(array)
    if max_val - min_val < k: return
    sorted_array = sorted(array)
    for i in range(len(array)):
        if min_val <= array[i] - k:  
            array[i] -= k
        elif max_val >= array[i] + k:
            array[i] += k
    return max(array) - min(array), array


test_array = [1, 10, 14, 14, 14, 15]
max_dif_in_array_with_k_add_or_subs(test_array, 6)

# finding the min product value of two vectors if elements of both arrays are allowed to be shuffled:
import numpy as np
a = np.array([3, 1, 1])
b = np.array([6, 5, 4])
# sort both arrays and reverse one of them to get the least value for scalar value for their multiplication.
a_sorted = np.sort(a)
a_rev_sorted = list(reversed(a_sorted))
b_sorted = np.sort(sorted(b))
print(np.dot(a_rev_sorted , b_sorted))<jupyter_output>23
{'fraction_non_alphanumeric': 0.118698679970897, 'fraction_numerical': 0.04396632366697849, 'mean_word_length': 2.3952011291460833, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '198752', 'license': 'MIT', 'n_tokens_mistral': 3777, 'n_tokens_neox': 3414, 'n_words': 1058, 'path': 'Greedy_Algorithms_Implimentation.ipynb', 'repo_name': 'volkansonmez/Must_Do_For_a_Coder', 'size': '9621'}