4clojure 101

gistfile1.clj

;Levenshtein Distance - Hard
;Given two sequences x and y, calculate the <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Levenshtein_distance">Levenshtein distance</a> of x and y, i. e. the minimum number of edits needed to transform x into y.  The allowed edits are:<br/><br/>- insert a single item<br/>- delete a single item<br/>- replace a single item with another item<br/><br/>WARNING: Some of the test cases may timeout if you write an inefficient solution!
;tags - seqs
;restricted - 
(ns offline-4clojure.p101
  (:use clojure.test))

(def __
  (fn [s t]
    (let [m (count s)
          n (count t)
          a (to-array-2d (for [i (range (inc m))
                               ]
                           (repeat (inc n) nil)))
          lookup (fn [i j]
                   (aget (aget a i) j))
          set (fn [i j val]
                (aset (aget a i) j val))
          ]
      (do (doseq [i (range (inc m))]
            (set i 0 i))
          (doseq [j (range (inc n))]
            (set 0 j j))
          (doseq [j (range 1 (inc n))
                  i (range 1 (inc m))
                  ]
            (if (= (nth s (dec i))
                   (nth t (dec j)))
              (set i j (lookup (dec i) (dec j)))
              (set i j (+ 1 (min (lookup (dec i) j)
                                 (lookup i (dec j))
                                 (lookup (dec i) (dec j)))))))
          (lookup m n))))
  )
                          
              
    
      )
(defn -main []
  (time
   (and
    (= (__ "kitten" "sitting") 3)
    (= (__ "closure" "clojure") (__ "clojure" "closure") 1)
    (= (__ "xyx" "xyyyx") 2)
    (= (__ "" "123456") 6)
    (= (__ "Clojure" "Clojure") (__ "" "") (__ [] []) 0)
    (= (__ [1 2 3 4] [0 2 3 4 5]) 2)
    (= (__ '(:a :b :c :d) '(:a :d)) 2)
    (= (__ "ttttattttctg" "tcaaccctaccat") 10)
    (= (__ "gaattctaatctc" "caaacaaaaaattt") 9)
    )))