Problem 018: Maximum Path Sum I

From Project Euler:

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)

We could brute force this one or even solve it by hand, but since Problem 67 is much more complex we might as well solve this one now. An easy dynamic programming solution is just to start from the bottom and work our way up. Starting from the second-to-last row, for each index $i$ determine whether a left or a right is best by taking the max of the values in spots $i$ and $i + 1$ in the next row, and adding that to our current element.

The code is pretty straight-forward:

(defn collapse [row1 row2]
    (assert (== (+ 1 (count row1)) (count row2)))
    (->> (range (count row1))
         (map #(+ (nth row1 %)
                  (max (nth row2 %)
                       (nth row2 (+ % 1)))))))

(defn solve [rows]
  (assert (> (count rows) 0))
  (loop [current-row (- (count rows) 2)
         _rows rows]
    (if (== current-row -1)
      (first (first _rows))
      (recur (- current-row 1)
             (assoc _rows
                    current-row
                    (collapse (nth _rows current-row)
                              (nth _rows (+ current-row 1))))))))

And it runs really fast:

rob@alien ~/code/euler/clj-euler $ lein run
Processing...
1074
"Elapsed time: 4.771813 msecs"