1.  
2. import networkx as nx
3. import matplotlib.pyplot as plt  # Optional, for visualization
4. import sympy
5. import random
6. import string
7.  
8. # This function removes letters from a string
9. # For example 215bct as input returns 215
10. def exclude_alpha(input_string):
11.     result_string = ''.join(char for char in input_string if not char.isalpha())
12.     return result_string
13.  
14. # This function finds the maximum path and it's sum
15. def find_max_sum_path(graph, start_node):
16.     max_sum = float('-inf')
17.     max_sum_path = []
18.  
19.     def dfs(node, current_path, current_sum):
20.         nonlocal max_sum, max_sum_path
21.  
22.         current_path.append(node)
23.         current_sum += graph.nodes[node]['value']  # Assuming you have a 'value' attribute for nodes
24.  
25.         if current_sum > max_sum:
26.             max_sum = current_sum
27.             max_sum_path = current_path.copy()
28.  
29.         for neighbor in graph.successors(node):
30.             dfs(neighbor, current_path.copy(), current_sum)
31.     dfs(start_node, [], 0)
32.     return max_sum_path, max_sum
33.  
34.  
35.  
36. def is_not_prime(number):
37.     return not sympy.isprime(number)
38.  
39. # This function connects node to n1  and n2
40. def connect_edge_nodes(node, n1, n2):
41.     # Add the main node and the nodes to be connected
42.  
43.     node_excluded = exclude_alpha(node)
44.     if is_not_prime(int(node_excluded)):
45.         G.add_node(node, value=int(node_excluded))
46.     else:
47.         return
48.  
49.  
50.     n1_excluded = exclude_alpha(n1)
51.  
52.     if is_not_prime(int(n1_excluded)):
53.         G.add_node(n1,value=int(n1_excluded))
54.         G.add_edge(node, n1)
55.  
56.     n2_excluded = exclude_alpha(n2)
57.     if is_not_prime(int(n2_excluded)):
58.         G.add_node(n2, value=int(n2_excluded))
59.         G.add_edge(node, n2)
60.  
61. # This functions connects node to n1,n2 and n3
62. def connect_nodes(node, n1, n2, n3):
63.     # Add the main node and the nodes to be connected
64.  
65.     node_excluded = exclude_alpha(node)
66.     if is_not_prime(int(node_excluded)):
67.         G.add_node(node, value=int(node_excluded))
68.     else:
69.         return
70.  
71.     n1_excluded = exclude_alpha(n1)
72.     if is_not_prime(int(n1_excluded)):
73.         G.add_node(n1, value=int(n1_excluded))
74.         G.add_edge(node, n1)
75.  
76.     n2_excluded = exclude_alpha(n2)
77.     if is_not_prime(int(n2_excluded)):
78.         G.add_node(n2, value=int(n2_excluded))
79.         G.add_edge(node, n2)
80.  
81.     n3_excluded = exclude_alpha(n3)
82.     if is_not_prime(int(n3_excluded)):
83.         G.add_node(n3, value=int(n3_excluded))
84.         G.add_edge(node, n3)
85.    
86.  
87.  
88.  
89. # Open the file for reading
90. with open('triangle', 'r') as file:
91.     lines = file.readlines()
92.  
93. # Store the file content in a 2d array
94. triangle = [list(map(int, line.split())) for line in lines]
95.  
96. # Append 3 random letter to end of each element. This prevents adding same keys to the graph. (9ask and 9xyz will be different)
97. triangle = [[str(num) + ''.join(random.choices(string.ascii_lowercase, k=3)) for num in row] for row in triangle]
98.  
99.  
100.  
101. # Create a new directed graph
102. G = nx.DiGraph()
103.  
104.  
105. for i in range(len(triangle) - 1):
106.     for j in range(len(triangle[i])):
107.         # if this is first column we can only connect two edges
108.         if j == 0:
109.             connect_edge_nodes(triangle[i][j], triangle[i+1][j], triangle[i+1][j+1])
110.         # otherwise add 3 edges
111.         else:
112.             connect_nodes(triangle[i][j], triangle[i+1][j-1], triangle[i+1][j], triangle[i+1][j+1])
113.  
114.     print("\n")
115.  
116. # For printing the graph
117. pos = nx.spring_layout(G)  # Positions for all nodes
118. nx.draw(G, pos, with_labels=True, arrows=True)
119.  
120.  
121. start_node = triangle[0][0]
122. max_sum_path, max_sum = find_max_sum_path(G, start_node)
123. print("Max Sum Path:", max_sum_path)
124. print("Max sum: ", max_sum)
125.  
126.  
127. plt.show()
128.  
129.  
130.