Advertisement
cookchar

Maximum-Sum Path in a Number Triangle

Aug 26th, 2017
172
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.11 KB | None | 0 0
  1. tri = []
  2.  
  3. def loadTriangle():
  4.     while len(tri) > 0:
  5.         del tri[0]
  6.  
  7.     try:
  8.         load = open(input('Filename? -={ '), 'r')
  9.     except FileNotFoundError:
  10.         print('Error: File not found...')
  11.         return
  12.  
  13.     conts = load.read()
  14.     for line in conts.split('\n'):
  15.         temp = []
  16.  
  17.         for bit in line.split(' '):
  18.             temp.append(int(bit))
  19.  
  20.         tri.append(temp)
  21.  
  22.     for line in tri:
  23.         for bit in line:
  24.             print(bit, end = ' ')
  25.         print()
  26.  
  27. def maxPath():
  28.     line = len(tri) - 2
  29.     below = tri[line + 1]
  30.     Idxs = []
  31.     bIdxs = []
  32.     currSums = []
  33.  
  34.     while line >= 0:
  35.         current = tri[line]
  36.  
  37.         for i in range(len(current)):
  38.             choices = below[i:i+2]
  39.  
  40.             bIdxs.append(i + choices.index(max(choices)))
  41.  
  42.             currSums.append(current[i] + max(choices))
  43.  
  44.         line -= 1
  45.         below = currSums
  46.         Idxs.insert(0, bIdxs)
  47.         bIdxs = []
  48.         currSums = []
  49.  
  50.     line = 0
  51.     bigSum = 0
  52.     maxIdx = 0
  53.     while line < len(tri):
  54.         print(tri[line][maxIdx], end = '')
  55.         bigSum += tri[line][maxIdx]
  56.  
  57.         if line + 1 < len(tri):
  58.             maxIdx = Idxs[line][maxIdx]
  59.             print(' + ', end = '')
  60.  
  61.         line += 1
  62.  
  63.     print(' =', bigSum)
  64.  
  65.     return below[0]
  66.  
  67. loadTriangle()
  68. maxPath()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement