One of my coworkers posted a programming challenge of solving “triangle puzzle”.
Given above, start at the root then move done, examine left and right nodes, choose the max, then go down again. Please note that this is not a breadth first find max path problem seen at projecteuler-18. There is no backtracking, if we go left or right, higher possible sum could be potentially missed. For example, if we replace 8 in 3rd row and 5 in 4th row with 9, the result will still be the same – 27 and not 29.
clojure.zip has a build in support of turning nested vector into a zipper. So, the first step is to express our puzzle as a nested vector.
(require '[clojure.zip :as z])
(def nv [5
And here is the solution.
1 (defn left-node [node-loc]
2 (-> node-loc z/right z/down))
4 (defn right-node [node-loc]
5 (-> node-loc z/right z/right z/down))
7 (defn sum-path [rt-loc, cf]
8 (loop [rs (-> rt-loc z/down z/node)
9 cn (-> rt-loc z/down)]
10 (if-not (z/right cn)
12 (let [lv (z/node (left-node cn))
13 rv (z/node (right-node cn))]
14 (if (cf lv rv)
15 (recur (+ rs lv) (left-node cn))
16 (recur (+ rs rv) (right-node cn)))))))
Pretty evident what is going on here. We use two utility functions to get left and right node. sum-path accepts starting node and compare function, depth first walks the zipper comparing left and right node values.
(def zv (z/vector-zip nv))
; max path - returns 27
(sum-path zv >)
; min path - return 18
(sum-path zv <)