THMMY.gr

P = [0,1,5,8,9,10,17,17,18,20,21,23,25,27,27,28,29,30,32,34,35,37,38,38,38,40,41,42,43,45,45,46,47,50,51,52,55,56,58,65,65,67]

def cut_cable(P,n):
    c = [0] * (n+1)
    cuts = [(0,0)]*(n+1)
    next_cut = n
    for i in range(0, n+1):
        max_c_i = 0
        max_i = -1
        max_j = -1
        for j in range(0,i):
            if P[i-j] + c[j] > max_c_i:
                max_c_i = P[i-j] + c[j]
                max_i = i
                max_j = j
        c[i] = max_c_i
        cuts[i] = max_i-max_j, max_j
    #print("P[%d] gia %d kai %d" % (max_i, max_i-max_j, max_j))
    #print(cuts)
    
    print("\nTa kopsimata tha ginoun stis theseis")
    while True:
        print("%d," % (cuts[next_cut][0]), end='')
        next_cut = cuts[next_cut][1]
        if next_cut == 0:
            break
    print(" kai to megisto kerdos einai %d" % (c[n]))
    return c[n]

cut_cable(P,41)

import datatools
import graphtools
from string import ascii_lowercase as myletters
from copy import deepcopy

def huffman(C, f):
    n = len(C)
    Q = datatools.Heap(C, f)
    for i in range(0, n - 1):
        x = Q.extract_min()
        y = Q.extract_min()
        z = (x, y)
        f[z] = f[x] + f[y]
        Q.insert(z, f[z])
    return Q.extract_min()

def get_tree_codes(tree, codes = {}, prefix = ""):
    if len(tree) == 1:
        codes[tree] = prefix
    else:
        get_tree_codes(tree[0], codes, prefix + "0")
        get_tree_codes(tree[1], codes, prefix + "1")
    return codes

def create_dict(f, message):
    f = dict([(myletters[i], message.count(myletters[i])) for i in range(25)])
    f = {x:y for x,y in f.items() if y != 0}
    f[' '] = message.count(' ')
    return f

def get_tree_with_frequencies(tree, f, freqs = {}):
    if len(tree) == 1:
        freqs[tree] = f[tree]
    else:
        freqs[0], freqs[1] = {}, {}
        get_tree_with_frequencies(tree[0], f, freqs[0])
        get_tree_with_frequencies(tree[1], f, freqs[1])
    return freqs

mydict = 0
message = "this is an example message to be encoded"

mydict = create_dict(mydict,message)
mydict2 = deepcopy(mydict)

res = huffman(list(mydict2.keys()), mydict2)

dict_codes = get_tree_codes(res)

coded_message = ""
for i in range(len(message)):
    coded_message += dict_codes[message[i]]

print("--- Answer 1 ---")
print(mydict)
print()
print("--- Answer 2 ---")
print(res)
print()
print("--- Answer 3 ---")
print(dict_codes)
print()
print("--- Answer 4 ---")
print(coded_message)
print()
print("--- Answer 5 ---")
graphtools.plot_huffman_tree(get_tree_with_frequencies(res, mydict))

import dijkstra

graph = {
        'directed': True,
        'vertices': ['A', 'B', 'C', 'D', 'E'],
        'edges': [
            ('A', 'B', 10),
            ('A', 'C', 3),
            ('B', 'C', 1),
            ('B', 'D', 2),
            ('C', 'D', 8),
            ('C', 'E', 2),
            ('D', 'E', 7),
            ('E', 'B', 4),
            ('E', 'D', 9)
            ]
        }

all_shortest_paths_dj = {}

for i, u in enumerate(graph['vertices']):
    all_shortest_paths_dj[u] = {}
    for j, v in enumerate(graph['vertices']):
        all_shortest_paths_dj[u][v] = dijkstra.dijkstra_path(graph, u, v)

print(all_shortest_paths_dj)

import sys

def max(a,b):
    return a if (a > b) else b
        

def cutrope(price,n):
    if n<=0:
        return 0;
    
    max_val = -sys.maxsize-1
    
    for i in range(0,n):
        max_val=max(max_val,price[i]+cutrope(price,n-i-1));
    
    return max_val
    
    
    
def cutrope2(price,n):
    if n<=0:
        return 0;
    val=[0 for x in range(n)]
    max_val=price[n-1]
    
    for i in range(1,n):
        for j in range (1,n):
            if(n-i-j-1>=0):
                val=price[i]+price[n-i-j-1]
                if val>max_val:
                    max_val=val;
    return max_val    
    
    
price=[1,5,8,9,10,17,17,18,20,21,23,25,27,27,28,29,30,32,34,35,37,38,38,38,40,41,42,43,45,45,46,47,50,51,52,55,56,58,65,65,67]
n=len(price)
print("1: Maximum Obtainable Value is", cutrope(price, 5))
print("2: Maximum Obtainable Value is ", cutrope2(price, 5))
                

import huffman

def give_dict(message):
    letter_list=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"," "]
    message_list=list(message)
    
    f={}
    l=len(letter_list)
    for i in range(0,l):
        count=message_list.count(letter_list[i])
        if count>0:
            f[letter_list[i]]=count
    return f
    
def give_coded_message(message,codes):
    message_list=list(message)
    coded_message=""
    for i in range(0,len(message_list)):
        coded_message=coded_message+str(codes[message_list[i]])
        
    return coded_message
    
message = "this is an example message to be encoded"
f={}
f=give_dict(message)


q=huffman.huffman(list(f.keys()),f)
print("Tree\n" + str(q) + "\n")
codes=huffman.get_tree_codes(q,codes = {}, prefix = "")
print("Codes\n" + str(codes))
coded_message=give_coded_message(message,codes)
print("Coded message:\n" + str(coded_message))


tree_with_freq=huffman.get_tree_with_frequencies(q,f,freqs={})
import graphtools
graphtools.plot_huffman_tree(tree_with_freq)

import graphtools
import dijkstra
import floydwarshall

#MAIN PROGRAM 

graph = {
    'directed': True,
    'vertices': ['A', 'B', 'C', 'D', 'E'],
    'edges': [
        ('A', 'B', 10),
        ('A', 'C', 3),
        ('B', 'C', 1),
        ('B', 'D', 2),
        ('C', 'D', 8),
        ('C', 'E', 2),
        ('D', 'E', 7),
        ('E', 'B', 4),
        ('E', 'D', 9)
        ]
    }

all_shortest_paths = floydwarshall.floydwarshall_paths(graph)

for a in range(0, len(D)):
       print("\t".join(str(D[a][b]) for b in range(0, len(D))))

print("Floyd: "+ str(all_shortest_paths['A']['B']))



shortest_paths = {}
for i, u in enumerate(graph['vertices']):
        shortest_paths[u] = {}
        for j, v in enumerate(graph['vertices']):
            shortest_paths[u][v] = dijkstra.dijkstra_path(graph, u, v)
        



print("Djkstra: "+ str(shortest_paths['A']['B']))

if(all_shortest_paths==shortest_paths):
    graphtools.plot_graph(graph, path = all_shortest_paths['A']['B'])
    graphtools.plot_graph(graph, path = shortest_paths['A']['B'])
    print("ALL SHORTEST PATHS ARE EQUAL")
else:
    graphtools.plot_graph(graph, path = all_shortest_paths['B']['E'])
    graphtools.plot_graph(graph, path = shortest_paths['B']['E'])
    print("THEY ARE NOT EQUAL")
    print("Floyd:\n"+str(all_shortest_paths))
    print("Dijkstra:\n"+str(shortest_paths))