import networkx as nx
import matplotlib.pyplot as plt  # Optional, for visualization
import sympy
import random
import string

# This function removes letters from a string
# For example 215bct as input returns 215
def exclude_alpha(input_string):
    result_string = ''.join(char for char in input_string if not char.isalpha())
    return result_string

# This function finds the maximum path and it's sum
def find_max_sum_path(graph, start_node):
    max_sum = float('-inf')
    max_sum_path = []

    def dfs(node, current_path, current_sum):
        nonlocal max_sum, max_sum_path

        current_path.append(node)
        current_sum += graph.nodes[node]['value']  # Assuming you have a 'value' attribute for nodes

        if current_sum > max_sum:
            max_sum = current_sum
            max_sum_path = current_path.copy()

        for neighbor in graph.successors(node):
            dfs(neighbor, current_path.copy(), current_sum)
    dfs(start_node, [], 0)
    return max_sum_path, max_sum



def is_not_prime(number):
    return not sympy.isprime(number)

# This function connects node to n1  and n2
def connect_edge_nodes(node, n1, n2):
    # Add the main node and the nodes to be connected

    node_excluded = exclude_alpha(node)
    if is_not_prime(int(node_excluded)):
        G.add_node(node, value=int(node_excluded))
    else:
        return


    n1_excluded = exclude_alpha(n1)

    if is_not_prime(int(n1_excluded)):
        G.add_node(n1,value=int(n1_excluded))
        G.add_edge(node, n1)

    n2_excluded = exclude_alpha(n2)
    if is_not_prime(int(n2_excluded)):
        G.add_node(n2, value=int(n2_excluded))
        G.add_edge(node, n2)

# This functions connects node to n1,n2 and n3
def connect_nodes(node, n1, n2, n3):
    # Add the main node and the nodes to be connected

    node_excluded = exclude_alpha(node)
    if is_not_prime(int(node_excluded)):
        G.add_node(node, value=int(node_excluded))
    else:
        return

    n1_excluded = exclude_alpha(n1)
    if is_not_prime(int(n1_excluded)):
        G.add_node(n1, value=int(n1_excluded))
        G.add_edge(node, n1)

    n2_excluded = exclude_alpha(n2)
    if is_not_prime(int(n2_excluded)):
        G.add_node(n2, value=int(n2_excluded))
        G.add_edge(node, n2)

    n3_excluded = exclude_alpha(n3)
    if is_not_prime(int(n3_excluded)):
        G.add_node(n3, value=int(n3_excluded))
        G.add_edge(node, n3)
    



# Open the file for reading
with open('triangle', 'r') as file:
    lines = file.readlines()

# Store the file content in a 2d array
triangle = [list(map(int, line.split())) for line in lines]

# Append 3 random letter to end of each element. This prevents adding same keys to the graph. (9ask and 9xyz will be different)
triangle = [[str(num) + ''.join(random.choices(string.ascii_lowercase, k=3)) for num in row] for row in triangle]



# Create a new directed graph
G = nx.DiGraph()


for i in range(len(triangle) - 1):
    for j in range(len(triangle[i])):
        # if this is first column we can only connect two edges
        if j == 0:
            connect_edge_nodes(triangle[i][j], triangle[i+1][j], triangle[i+1][j+1])
        # otherwise add 3 edges
        else:
            connect_nodes(triangle[i][j], triangle[i+1][j-1], triangle[i+1][j], triangle[i+1][j+1])

    print("\n")

# For printing the graph
pos = nx.spring_layout(G)  # Positions for all nodes
nx.draw(G, pos, with_labels=True, arrows=True)


start_node = triangle[0][0]
max_sum_path, max_sum = find_max_sum_path(G, start_node)
print("Max Sum Path:", max_sum_path)
print("Max sum: ", max_sum)


plt.show()