Boggle in Clojure

boggle.clj

(ns boggle.core
  (:require [clojure.java.io :as io]
            [clojure.string :as st]))

(defprotocol ITrie
  (next? [this letter])
  (insert [this word])
  (subtree [this letter])
  (terminal? [this]))

(declare nil-tree)
(deftype LetterTrie [t? children]
  ITrie
  (next? [this letter]
    (contains? children letter))
  (insert [this word]
    (if (nil? word)
      (LetterTrie. true children)
      (let [letter (first word)
            child  (or (children letter) nil-tree)]
        (LetterTrie. t? (assoc children letter (insert child (next word)))))))
  (subtree [this letter]
    (children letter))
  (terminal? [this] t?)
  Object
  (toString [this]
    (str "t?:" t? " -> " children)))

(def nil-tree (LetterTrie. false {}))

(defn create-tree [words] (reduce insert nil-tree words))

(def default-dict
  (with-open [rdr (io/reader "/usr/share/dict/words")]
    (->> rdr
         line-seq
         (filter (comp (partial <= 3) count))
         (map st/lower-case)
         create-tree)))

(defn expand
  [size [x y]]
  (for [x' (range (dec x) (+ x 2))
        y' (range (dec y) (+ y 2))
        :when (and (not= [x y] [x' y']) (< -1 x' size) (< -1 y' size))]
    [x' y']))

(defn- rand-char [] ((vec (map char (range 97 123))) (rand-int 26)))
(defn random-board
  [size]
  (->> (repeatedly (* size size) rand-char)
       (partition size)
       (map vec)
       vec))

(def test-board
  [[\t \e \s \t]
   [\i \n \g \t]
   [\h \e \s \o]
   [\l \v \e \r]])

(defn search
  [board dict cursor visited word words]
  (let [letter (get-in board cursor)]
    (when (next? dict letter)
      (when (terminal? dict)
        (swap! words #(conj % word)))
      (doseq [cursor' (expand (count board) cursor)
              :when (not (contains? visited cursor'))]
        (search board
                (subtree dict letter)
                cursor'
                (conj visited cursor)
                (str word letter)
                words)))))

(defn solve
  [board dict]
  (let [words (atom #{})]
    (doseq [i (range (count board))
            j (range (count (first board)))
            :let [start [i j]]]
      (search board dict start #{} "" words))
    @words))

(defn -main
  []
  (println (solve test-board default-dict)))