Boggle solver

core.clj

(ns interview1.core
  (:require [clojure.set :as set]
            [clojure.string :as string])
  (:gen-class))


(def dice ["AAEEGN"
           "ELRTTY"
           "AOOTTW"
           "ABBJOO"
           "EHRTVW"
           "CIMOTU"
           "DISTTY"
           "EIOSST"
           "DELRVY"
           "ACHOPS"
           "HIMNQU"
           "EEINSU"
           "EEGHNW"
           "AFFKPS"
           "HLNNRZ"
           "DEILRX"])

(defn generate-dist []
  (vec (map vec (partition 4 (map #(rand-nth %) dice)))))

(defn adjacent-cells [i j]
  (let [new-cells (for [i1 (range -1 2)
                        j1 (range -1 2)]
                    [(+ i i1) (+ j j1)])]
    (set (filter (fn [[i1 j1]]
                   (and (>= i1 0)
                        (< i1 4)
                        (>= j1 0)
                        (< j1 4)
                        (not= [i j] [i1 j1])))
                 new-cells))))

(defn get-letter [coll i j]
  ((coll i) j))

(def dict
  (set (map #(.toUpperCase %)
            (string/split-lines (slurp "/usr/share/dict/words")))))

(defn prefix-in-dictionary [word]
  (some #(.startsWith % word) dict))

(defn in-dictionary [word]
  (some #(= % word) dict))

(defn find-words
  ([coll]
     (apply sorted-set
            (concat (let [starters (for [i (range 4) j (range 4)] [i j])]
                      (apply concat (map #(apply find-words coll %) starters))))))
  ([coll i j]
     (find-words coll i j "" #{}))
  ([coll i j word visited]
     (let [next-cells  (set/difference (adjacent-cells i j) visited)
           new-word    (str word (get-letter coll i j))
           new-visited (conj visited [i j])
           descend     #(apply concat (for [[i1 j1] next-cells
                                            :let [new-list (find-words coll i1 j1 new-word new-visited)]]
                                        new-list))]
       (when (prefix-in-dictionary new-word)
         (if (in-dictionary new-word)
           (cons new-word (descend))
           (descend))))))

(defn -main [& args]
  (let [dist (generate-dist)
        words (find-words dist)]
    (println "From distribution:" dist)
    (println "The list:")
    (doseq [word words]
      (println word))))