Clojure Zipper Over Nested Vector

23 Nov

One of my coworkers posted a programming challenge of solving “triangle puzzle”.

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.

Solution

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 <)
About these ads

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?

    https://gist.github.com/713956

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

        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

      • 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.

Trackbacks/Pingbacks

  1. links for 2010-11-24 « Blarney Fellow - November 24, 2010

    [...] Clojure Zipper Over Nested Vector « On Software and Life (tags: clojure zipper fp tree recursion search) [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: