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

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)

This problem is best solved by starting at the base and working up. Increment the number above each pair of nodes by the largest of the two nodes, and continue until you reach the top.

(defconstant +triangle+ 
  '(
    (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)))

(defun bottom-two-rows (triangle)
  "Returns the bottom two rows of a triangle"
  (list (car (last (butlast triangle)))
         (car (last triangle))))

(defun first-node-and-stems (triangle)
  "Given two rows of a triangle, returns the first node and the
first node's stems.
Example: (first-node-and-stems '((2 4 6) (8 5 9 3))) => 2 8 5"
  (let ((node (caar triangle))
          (left-stem (first (cadr triangle)))
          (right-stem (second (cadr triangle))))
    (values node left-stem right-stem)))

(defun max-node (node left-stem right-stem)
  (max (+ node left-stem)
           (+ node right-stem)))

(defun sum-stems (rows)
  "Given two adjacent rows of a triangle, returns a list of the
maximum total of the stems for each node.
Example: (sum-stems '((2 4 6) (8 5 9 3))) => (10 13 15)"
  (when (first rows)
    (multiple-value-bind (node left-stem right-stem)
        (first-node-and-stems rows)
      (cons (max-node node left-stem right-stem)
                (sum-stems (mapcar #'cdr rows))))))

(defun max-route (triangle)
  "Returns the sum of the route that produces the maximum total of
the given triangle"
  (if (= (length triangle) 2)
      (multiple-value-bind (node left-stem right-stem)
           (first-node-and-stems triangle)
        (max-node node left-stem right-stem))
      (max-route (append (butlast (butlast triangle))
                                      (list (sum-stems
                                             (bottom-two-rows triangle)))))))

(defun euler-18 ()
  (max-route +triangle+))