problem 81

"""
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

⎛⎝⎜⎜⎜⎜⎜⎜131201630537805673968036997322343427464975241039654221213718150111956331⎞⎠⎟⎟⎟⎟⎟⎟
Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.
"""
"""
from collections import defaultdict
import sys
sys.setrecursionlimit(3000)
class Graph:

  def __init__(self, input_file):
    self.graph = defaultdict(lambda: {})
    array = []
    with open(input_file) as file:
      for line in file:
        lines = line.split(',')
        array.append(lines)
    for i in  range(len(array)):
      for j in  range(len(array) - 1):  
        self.add_edge(array[i][j], array[i][j + 1])
    for x in  range(len(array)- 1):
      for k in  range(len(array)):
        self.add_edge(array[x][k], array[x + 1][k]) 
    print(self.graph)    
    
  def add_edge(self, node1, node2):
    self.graph[node1][node2] = int(node2)

  def nodes(self):
    return self.graph.keys()

  def neighbors(self, a):
    return self.graph[a]

  def shortest_path(self, start, end, visited):
    visited.add(start)

    if start == end:
      return 0
    # [c, e]
    neighbors_paths = [float('inf')]

    if end in self.graph[start]:
      neighbors_paths.append(self.graph[start][end])

    for neighbor in set(self.graph[start].keys()) - visited:
      neighbors_paths.append(self.shortest_path(neighbor, end, set(visited)) + self.graph[start][neighbor])
    return min(neighbors_paths)
      

start = '131'
end = '331'
#start = '131'
#end = '331'
graph  = Graph('test.txt')
print(graph.shortest_path(start, end, set()) + int(start))
#print(graph.weight('131', '673'))"""

          


def open_file(file_name):
  with open(file_name) as file:
    l = [[int(num) for num in line.split(',')] for line in file]
  return l

def shortest_path(all_nums, size):
  for i in range(1, size):
    all_nums[0][i] += all_nums[0][i - 1]
    all_nums[i][0] += all_nums[i - 1][0]
  for i in range(1, size):
    for j in range(1, size):
      all_nums[i][j] += min(all_nums[i - 1][j], all_nums[i][j - 1])  
  return all_nums[size - 1][size - 1]       

size = 80
all_nums = open_file('minimal_path.txt')   
print(shortest_path(all_nums, size)) 
for i in range(4,0,-1):
  print(i)