Archive | November, 2010

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

Clojure Macro Average Time

22 Nov

In my previous post on binary search I wanted to evaluate performance of two implementations. Clojure provides dotimes and time. Wouldn’t it be nice if we can string them together, parse output from time and calculate average execution time. Checking source of time and poking around I discovered with-out-str macro. It is quite simple. It just dynamically rebinds default output stream *out* to java.io.StringWriter. Having this the rest is piece of cake.

 1 (use '[clojure.contrib.str-utils :only (re-split)])
 2 (defmacro time-avg
 3   "Captures time output, parses it and calculates average.
 4   Modeled after with-out-str. Example:
 5   (time-avg
 6      (dotimes [_ 5] (time (.run #(Thread/sleep (rand 100))))))"
 7   [& body]
 8   `(let [s# (java.io.StringWriter.)]
 9      (binding [*out* s#]
10        ~@body)
11      (let [strng# (str s#)
12            lns# (re-split #"\n" strng#)
13            flt-regex# #"\d+\.\d+"
14            lns-flts# (filter #(re-seq flt-regex# %) lns#)
15            flts# (map 
16              #(Float/parseFloat (first (re-seq flt-regex# %))) 
17              lns-flts#)
18            sum# (reduce + flts#)]
19        (println strng#)
20        (if (seq flts#)
21          (println "\"Average of" (count flts#) "run/s is" 
22               (/ sum# (count flts#)) "msecs\"")))))

Starting on line 11 we parse output using regexes, look for doubles, sum them up and print calculated average. The only thing I stumbled on was using suffix # in macro variable names.