Levenstein Edit distance

(defmacro aget2l [a i j]
  `(aget ^"[J" (aget ~a ~i) ~j))

(defmacro aset2l [a i j v]
  `(aset-long ^"[J" (aget ~a ~i) ~j ~v))

(defn distance [^String w1 ^String w2]
  (let [c1 (.length w1) c2 (.length w2)
        matrix ^"[[J" (make-array Long/TYPE (unchecked-inc-int c1) (unchecked-inc-int c2))]
    (dotimes [n (unchecked-inc-int c1)] (aset2l matrix n 0 n))
    (dotimes [n (unchecked-inc-int c2)] (aset2l matrix 0 n n))
    (dotimes [x c1]
      (dotimes [y c2]
        (as-> (min
                (aget2l matrix x (unchecked-inc-int y))
                (aget2l matrix (unchecked-inc-int x) y)
                (aget2l matrix x y)) m
              (if (= (.charAt w1 x)
                     (.charAt w2 y)) m (unchecked-inc-int m))
              (aset2l matrix x y m))))
    (aget2l matrix c1 c2)))

(defn distance2 [w1 w2]
  (cond
    (empty? w1) (count w2)
    (empty? w2) (count w1)
    :otherwise (min (+ (distance (rest w1) (rest w2))
                       (if (= (first w1) (first w2)) 0 1))
                    (+ 1 (distance (rest w1) w2))
                    (+ 1 (distance w1 (rest w2))))))



(defn create-graph [words]
  (reduce (fn [graph [w1 w2]] (update graph w1 conj w2))
          {}
          (for [w1 words w2 words
                :when (and (not= w1 w2) (= (distance w1 w2) 1))]
            [w1 w2])))

(defn max-coll [coll-of-coll]
  (reduce (fn [max c] (if (> (count c) (count max)) c max)) [] coll-of-coll))

(defn find-max-path [graph seen node]
  (if-let [nodes-to-visit (seq (filter (complement (set seen)) (graph node)))]
    (->> nodes-to-visit
         (map (fn [n] (find-max-path graph (conj seen node) n)))
         max-coll)
    (conj seen node)))

(defn word-chain? [words]
  (let [graph (create-graph words)
        paths (for [w words] (find-max-path graph [] w))]
    (boolean (some #(= (count words) (count %)) paths))))

(assert (= false (word-chain? #{"cot" "hot" "bat" "fat"})))
(assert (= false (word-chain? #{"share" "hares" "hare" "are"})))
(assert (= false (word-chain? #{"to" "top" "stop" "tops" "toss"})))
(assert (= true (word-chain? #{"hat" "coat" "dog" "cat" "oat" "cot" "hot" "hog"})))
(assert (= true (word-chain? #{"share" "hares" "shares" "hare" "are"})))
(assert (= true (word-chain? #{"spout" "do" "pot" "pout" "spot" "dot"})))
(assert (= true (word-chain? #{"dot" "det" "dit" "dito" "doto" "dto" "adot" "adote" "adoce"})))