Nov

27

Project Euler: finding maximal sum of path in a graph

Filed Under hisabati, project euler by  

Problem 18 in Project Euler reminded me of shortest path algorithms in graph theory. The goal is to determine the maximal sum you can compute when traveling from the top to the bottom of a triangle.

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 5
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

If this were a shortest path problem, we would be computing the minimum sum when traveling down the triangle (and we would also have a fixed destination, rather than a set of them – details, details). As phrased, the problem does not actually require us to give the path that yields the maximal sum and that eases the requirements on our algorithm.

The first step of our solution is to read lists of integers from the input triangle string.

  1: def get_triangle_lists(triangleString):
  2:     listOfRowsString = triangleString.split('n')
  3:     listOfRows = []
  4:     for row in listOfRowsString:
  5:         currRow = [int(x) for x in row.split()]
  6:         listOfRows.append(currRow)
  7:     return listOfRows

Next, we compute the max sum.

  1: def max_sum_in_triangle(triangleString):
  2:     listOfLists = get_triangle_lists(triangleString)
  3:     numRows = len(listOfLists)
  4:     for index in range(0, numRows):
  5:         if(index == 0):
  6:             continue
  7:         currRow = listOfLists[index]
  8:         previousRow = listOfLists[index - 1]
  9:         for column in range(0, index+1):
 10:             if (column == 0):
 11:                 currRow[column] += previousRow[column]
 12:             elif(column == index):
 13:                 currRow[column] += previousRow[column - 1]
 14:             else:
 15:                 currRow[column] += max(previousRow[column - 1], previousRow[column])
 16:     return max(listOfLists[numRows - 1])

The motivation is simple. We go through the triangle, from top to bottom one row at a time (breadth-first). For each node, we set its value to the maximal sum that can be achieved by a valid path ending in that node. For the top node, the maximal sum is trivially the value of the node. For subsequent rows, each node can be reached from exactly one or two nodes from the previous row.  The outer nodes in a row are only reachable from the outer nodes from the previous row. This means that for these nodes, we always add the current node value to the previous outer node’s value ( Lines 10 to 13 of the code above). Nodes that are not outer nodes in the row are reachable from two nodes in the previous row (the node to the upper left and one to the upper right in the graphical representation).The maximal sum at the current node is therefore given by the value of the current node plus the higher value between those presented in the two nodes in the previous row (Line 15 of the code above).

When the algorithm finishes iterating through the rows, the maximal value can be read directly from the bottom row of the triangle (line 16 in the code above).

Comments

Comments are closed.