Maximum Path Sum I

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 4
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

NOTE: As there are only \(16384\) routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

Let’s make it easier

We could indeed try to brute-force it, but I did not come up with any elegant brute-force in terms of implementation, so I’ve decided to instead think about solving this problem the ‘intended way’. As usual, let’s think about a nice algorithm that will save us from the necessity of checking all these possibilities. The small triangle will be perfect to plan it.

3
7 4
2 4 6
8 5 9 3

Instead of plotting a route from the top, we could try to do it from the bottom. Can we do something with the last row? Not really. We can’t take the maximum since we don’t know what’s ahead of us, exactly as if we started from the top.

Moving to the row before last, that is, \(2 4 6\), we notice that each of those numbers have exactly two children-numbers. For \(2\), that will be \(8\) and \(5\), for 4, it is \(5\) and \(9\), and so on. If our question was to find the best path for those small sub-problems, with 3-number triangles, then naturally we’d simply pick the bigger children. We can then add it to the parent. That’s how the triangle now looks like:

3
7 4
10 13 15

We can do the same folding to the next row. Just need to pick the “bigger” children. Eventually we’ll end up with that:

3
20 19

And then we fold it once again, leaving us with a single value: \(23\). That’s the maximum path sum.

Solution

For a big triangle, the algorithm remains exactly the same. A natural way to implement it is to mutate the arrays that represent the subsequent rows.

object Euler018M extends EulerApp {
  override def execute(): Int = {
    val dataArray: Array[Array[Int]] = prepareData()
    var rowIndex = dataArray.length - 2

    while (rowIndex >= 0) {
      dataArray(rowIndex).zipWithIndex.foreach { case (value, columnIndex) =>
        val childrenRow = dataArray(rowIndex + 1)
        val maxChildValue = Math.max(childrenRow(columnIndex), childrenRow(columnIndex + 1))
        dataArray(rowIndex)(columnIndex) = dataArray(rowIndex)(columnIndex) + maxChildValue
      }
      rowIndex -= 1
    }

    dataArray.head.head
  }

  private def prepareData(): Array[Array[Int]] =
    loadFileAsLines().toArray.map(_.split(" ").map(_.toInt).toArray)
}

Very straightforward to implement, as it closely follows what we did on paper with the small triangle, but unfortunately it mutates both the dataArray and the rowIndex.

For an immutable solution, we need to fold our triangle from the bottom. We can represent it as a List[List[Int]] and reverse it so we start from the end.

val reversedData = prepareData().reverse
reversedData.tail.foldLeft(reversedData.head) { case (previousRow, currentRow) => ... }

This part starts from the second row (.tail), while the first one goes into the accumulator. Since we always have two rows available, all we need to do is pick the bigger child and build the next accumulator, which will be our new previousRow. Here’s the complete solution:

object Euler018 extends EulerApp {
  override def execute(): Int = {
    val reversedData = prepareData().reverse
    reversedData.tail
      .foldLeft(reversedData.head) { case (previousRow, currentRow) =>
        currentRow.zipWithIndex.map { case (element, index) =>
          element + Math.max(previousRow(index), previousRow(index + 1))
        }
      }
      .head
  }

  private def prepareData(): List[List[Int]] =
    loadFileAsLines().map(_.split(" ").map(_.toInt).toList)
}

That’s it! Very concise, fully functional and with a similar run time.