word-squares.clj

(def words (string/split (slurp "/usr/share/dict/words") #"\n"))

(def words-trie 
  (reduce 
    (fn [trie word]
      (assoc-in trie (vec (cons (count word) word)) {}))
    {} words))

(defn keys-in [tree]
  (if (map? tree)
    (vec 
      (mapcat 
        (fn [[k v]]
          (let [sub (keys-in v)
                nested (map #(into [k] %) (filter (comp not empty?) sub))]
            (if (seq nested)
                nested
                [[k]])))
        tree)) []))

(defn continuations [cnt words]
  (let [index (count words)
        path (map #(get % index) words)
        trie (get-in words-trie (vec (cons cnt path)))
        options (map #(apply str (concat path %)) (keys-in trie))]
    (if (= cnt (inc (count words)))
      (map #(conj words %) options)
      (mapcat #(continuations cnt (conj words %)) 
        (filter
          (fn [word]
            (not (empty? 
              (for [idx (range (inc index) cnt) 
                    :let [letter (get word idx)]
                    :when (get-in words-trie 
                            (vec (concat (list cnt) 
                                         (map #(get % idx) words) 
                                         (list letter))))]
                true))))
          options)))))



(continuations 5 ["every" ])