From Medine , 8 Months ago, written in Python.
Embed
Hits: 412
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)):
46.     else:
47.         return
48.
49.
50.     n1_excluded = exclude_alpha(n1)
51.
52.     if is_not_prime(int(n1_excluded)):
55.
56.     n2_excluded = exclude_alpha(n2)
57.     if is_not_prime(int(n2_excluded)):
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)):
68.     else:
69.         return
70.
71.     n1_excluded = exclude_alpha(n1)
72.     if is_not_prime(int(n1_excluded)):
75.
76.     n2_excluded = exclude_alpha(n2)
77.     if is_not_prime(int(n2_excluded)):
80.
81.     n3_excluded = exclude_alpha(n3)
82.     if is_not_prime(int(n3_excluded)):
85.
86.
87.
88.
89. # Open the file for reading
90. with open('triangle', 'r') as file:
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.