Project Euler Problem 18 looked harder than it was. At first, I thought some sort of sophisticated heuristic approach would be needed to keep track of the lowest-cost paths as it incrementally searched through the tree, using some basic graph theory.

However, on careful reading the problem doesn’t require you keep track of the elements path, just the total score up to that point. A remarkably simple solution thus presents itself: for each element, look at the two elements in the row above it, take the max of those two elements, and sum them to the original element.

My solution looked like:

(def triangle [[75]
               [95 64]
               [17 47 82]
               [18 35 87 10]
               [20  4 82 47 65]
               [19  1 23 75  3 34]
               [88  2 77 73  7 63 67]
               [99 65  4 28  6 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  4 68 89 53 67 30 73 16 69 87 40 31]
               [04 62 98 27 23  9 70 98 73 93 38 53 60  4 23]])

(defn row-maxsum [b a]
  (let [diff (- (count a) (count b))]
    (map #(if (> %1 %2)
                    (+ %1 %3)
                    (+ %2 %3))
                 (concat b (repeat diff 0))
                 (concat (repeat diff 0) b)
                 a)))

(defn euler-18 [triangle]
  (reduce max (reduce row-maxsum triangle)))

(euler-18 triangle)

That only took a moment (0.5ms) to solve on my computer, and the code is pretty short as well.

However, one of the smart people on clojure-euler presented an even shorter solution, which I reprint here:

;; Nice job, "bibi"!
(defn merge-rows[a b]
  (map + (map #(apply max %) (partition 2 1 a)) b))
 
(reduce merge-rows (reverse triangle))

Bibi’s solution is more elegant because it accomplishes the functionality of the if statement using apply max. Nice job!

Amazing how much work can be done in a little more than a hundred characters of code, isn’t it?