Facebook
From Medine , 8 Months ago, written in Python.
Embed
Download Paste or View Raw
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)):
  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.