# Clojure Zipper Over Nested Vector

23 Nov

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 <)
```

### 9 Responses to “Clojure Zipper Over Nested Vector”

1. Strika November 24, 2010 at 10:23 #

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.

2. bhenry November 24, 2010 at 12:45 #

i wrote this for the triangle problems in project euler. i wonder how the timing compares with the zipper method?

 ;; for 18 and 67 in project euler (defn max-path-sum "give it a vector of vectors that form a triangle" ([t] (max-path-sum t (– (count t) 2) (t (dec (count t))))) ([t top bot] (if (> top 0) (max-path-sum t (dec top) (vec (let [row (t top)] (for [i (range top)] (+ (row i) (max (bot i) (bot (inc i)))))))) (+ (bot 0) ((t top) 0)))))

view raw
gistfile1.clj
hosted with ❤ by GitHub

• vitalyper November 28, 2010 at 18:15 #

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))

3. edbond November 25, 2010 at 17:47 #

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

• vitalyper November 28, 2010 at 18:25 #

I guess you found your own error :-) Modifying 3rd level 8 has no effect since this path is not chosen.

• edbond November 29, 2010 at 04:12 #

You wrote that goal is “find max path”. For triangle
(def routes
[[5]
[9 6]
[4 6 9]
[0 7 1 9]])

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

• vitalyper November 30, 2010 at 09:57 #

You are right. My problem statement is wrong. I will edit the post.

4. edbond November 27, 2010 at 16:57 #

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.