Archive | October, 2010

Clojure code with Vim in WordPress

31 Oct

As of now WordPress doesn’t support pretty print of clojure code.
But fear not… To embed nicely formatted line-numbered code into default WordPress blog using vim.

  1. Open your file in vim.
    :set number
  2. Visually select code.
  3. Select html between

  4. Paste it in your blog (in HTML view) inside

  5. Don’t switch to Visual view. Save/update your post.

That is it. Here is a sample.

2011-01-13 Update
Default format of TOhtml changed in recent version of Vim (7.3.46 for Windows). It uses css styles from page header element. To get inline styles:

   :let g:html_use_css = 0

Clojure Binary Search

20 Oct

Embarking on “killing two birds with one stone” (play with clojure and brush up on algorithms) adventure, here is my humble implementation of binary search. Without consulting outside sources after about 10 hours in total (my train commute is about an hour each way) the best I could do was:

 1 (defn indexed [coll] (map vector (iterate inc 0) coll))
 2 (defn 
 3   #^{:test (fn [] (tst bin-srch-indx))}
 4   bin-srch-indx [coll el]
 5   (loop [vc-indx (vec (indexed coll))]
 6     (let [sz (count vc-indx), mi (quot sz 2),
 7          ce (get vc-indx mi), [idx v] ce]
 8       (cond
 9         (< el (first coll)) nil
10         (> el (last coll)) nil
11         (and (= mi 0) (or (> el v) (< el v))) nil
12         (= el v) idx
13         (> el v) (recur (subvec vc-indx mi sz))
14         (< el v) (recur (subvec vc-indx 0 mi))))))

indexed on line 1 is an interesting by itself. I came across it in Programming Clojure by Stuart Halloway. It creates new lazy sequence by calling vector with pair of first, then second, etc. items in (iterate (inc 0)) and passed in collection until latter collection is exhausted. bin-srch-indx converts input sequence into a vector, uses cond to catch edge cases and finally uses clojure’s recur and subvec to half the searched collection. On line 3 there is an example of closure to hook in clojure’s build-in test facility. We will talk about test function later.

Unsatisfied with above, I thought there might be a better algorithm for binary search – time to enlist help of Wikipedia. Here is a faster version which doesn’t use subvec but manipulates boundaries.

 1 (defn 
 2   #^{:test (fn [] (tst bin-srch))}
 3   bin-srch [coll el]
 4     (let [v (vec coll)]
 5       (loop [li (int 0), ri (int (count v))]
 6         (if (= (get v 0) el)
 7           0
 8           (let [p (int (/ (- ri li) 2))]
 9             (if
10               (> p 0)
11                 (let [next-p (int (+ li p)),
12                      ce (get v next-p)]
13                   (cond
14                     (= ce el) next-p
15                     (> ce el) (recur li next-p)
16                     (< ce el) (recur next-p ri)))
17               nil))))))

Being a diligent developer, I included test function to prove that code works.

      [ub1 99999
      ub2 (+ ub1 1)
      tc1 (range 10 ub1 1)
      tc2 (conj tc1 ub2)
      tc3 [11 13 15]
      pli 1
      pui 98
      dc 500
      pcol (take 100 (drop dc primes))]
        (assert (= nil (f tc1 1)))
        (assert (= nil (f tc1 (+ ub2 1))))
        (for [i (range 10 (+ ub1 1) 1)] 
          (assert (= (- i 10) (f tc1 i))))
        (for [i (range 10 (+ ub2 1) 1)] 
          (assert (= (- i 10) (f tc2 i))))
        (assert (= nil (f tc3 14)))
        (assert (= pli
           (f pcol (first (take 1 
              (drop (+ dc pli) primes))))))
        (assert (= pui
           (f pcol (first (take 1 
              (drop (+ dc pui) primes))))))))

Above sets up some test data and using assert verifies results. So, in your friendly REPL you can try:

user=> (use '[clojure.contrib.lazy-seqs :only (primes)])
user=> (test bin-srch)
user=> (test bin-srch-indx)
user=> (bin-srch (take 100 primes) 11)

Also, here is a complete file bin-srch.clj. Since WordPress upload attachment gods don’t like clj extension, I had to use doc file extension. By the way, I don’t think it would hard to distinguish between text and binary files during upload and allow former. Let’s pray together: Hare WordPress upload attachment gods…:-)

In the next post we will take look how, with a help of clojure macro, we can measure running time of two implementations above.