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
[9
[4
[0] [7]]
[6
[7] [1]]]
[6
[6
[7] [1]]
[8
[1] [5]]]])
And here is the solution.
1 (defn left-node [node-loc]
2 (-> node-loc z/right z/down))
3
4 (defn right-node [node-loc]
5 (-> node-loc z/right z/right z/down))
6
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)
11 rs
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 <)
It’s problem 18 from projecteuler.net. (http://projecteuler.net/index.php?section=problems&id=18)
You can see some other Clojure solutions here: http://clojure-euler.wikispaces.com/Problem+018.
i wrote this for the triangle problems in project euler. i wonder how the timing compares with the zipper method?
https://gist.github.com/713956
I did time mine versus last (posted by bibi) at http://clojure-euler.wikispaces.com/Problem+018. I concede – according to my crude timings euler’s is order of magnitude faster. Plus it is a thing of beauty, short and leveraging clojure core libraries to the max.
(defn merge-rows[a b]
(map + (map #(apply max %) (partition 2 1 a)) b))
(reduce merge-rows (reverse routes))
Try to change 8 and bottom 5 to 9.
Max should be
(+ 5 6 9 9)
29
but it’s not:
user=> (def nv [5 [9 [4 [0] [7]] [6 [7] [1]]] [6 [6 [7] [1]] [9 [1] [9]]]])
user=> (sum-path zv >)
27
I guess you found your own error :-) Modifying 3rd level 8 has no effect since this path is not chosen.
You wrote that goal is “find max path”. For triangle
(def routes
[[5]
[9 6]
[4 6 9]
[0 7 1 9]])
your solution gives wrong answer. (27 instead of 29)
Zippers + BFS doesn’t work in this case.
Clever solution to this problem is to go from bottom to top, eliminating all sums except maximum (see my gist solution).
I find your post trying to solve euler18 with zippers and very fast found an error in your code.
HTH,
Eduard
You are right. My problem statement is wrong. I will edit the post.
This problem is very similar to euler18,
here is my simple solution: https://gist.github.com/718088
You wrote a good example of zippers usage, thanks.