joly solution for 4clojure #101

joly-4clojure-solution101.clj

;; joly's solution to Levenshtein Distance
;; https://4clojure.com/problem/101

;; Slow, but finishes fast enough for test problems.
;; None of the self-memoized versions worked without
;; using def, but memoizing this version gave a
;; speedup from 2500 msec -> 10 msec.

(fn lev [s t]
    (cond
      (empty? s) (count t)
      (empty? t) (count s)
      :else
        (let [ns (rest s)
              nt (rest t)]
          (if (= (first s) (first t))
            (lev ns nt)
            (min
              (inc (lev s nt))
              (inc (lev ns t))
              (inc (lev ns nt)))))))

(let [mem (atom {})](fn lev [s t]
%28cond
%28empty? s%29 %28count t%29
%28empty? t%29 %28count s%29
:else %28if-let [e %28find @mem [s t]%29]
%28val e%29
%28let [ns %28rest s%29
nt %28rest t%29
ret %28if %28= %28first s%29 %28first t%29%29
%28lev ns nt%29
%28min %28inc %28lev s nt%29%29
%28inc %28lev ns t%29%29
%28inc %28lev ns nt%29%29%29%29]
%28swap! mem assoc [s t] ret%29
ret%29%29%29))