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))