Solution to the telephone number search problem

challenge.clj

(ns euler.challenge
  (:use euler.dfs))

(def numbers-to-letters
  {2 ["a" "b" "c"]
   3 ["d" "e" "f"]
   4 ["g" "h" "i"]
   5 ["j" "k" "l"]
   6 ["m" "n" "o"]
   7 ["p" "q" "r" "s"]
   8 ["t" "u" "v"]
   9 ["w" "x" "y" "z"]})

(def word-set
  (into
    #{}
    (clojure.string/split
      (slurp "src/euler/word_list.txt")
      #"\r\n")))

(defn potential-strings [numbers]
  (set (map :letters-so-far
    (dfs-all
      {:letters-so-far "" :remaining-numbers numbers}
      (fn [node]
        (let [rest-numbers (rest (:remaining-numbers node))
              letters-to-add (get numbers-to-letters (first (:remaining-numbers node)))]
          (map (fn [letter] {:letters-so-far (str (:letters-so-far node) letter) :remaining-numbers rest-numbers}) letters-to-add)))
      #(empty? (:remaining-numbers %))))))


(defn drop-string [to-drop string]
  (clojure.string/replace-first string to-drop ""))

(defn prefixes [string]
  (map #(apply str (take % string)) (range 1 (inc (count string)))))

(defn made-of-words? [string]
  (dfs
    string
    (fn [node]
      (let [prefixes (prefixes node)
            word-prefixes (filter #(contains? word-set %) prefixes)
            ]
        (map #(drop-string % node) word-prefixes)))
    empty?))

(defn word-breakdowns [numbers]
  (filter made-of-words? (potential-strings numbers)))

challenge_test.clj

(ns euler.challenge-test
  (:use clojure.test
        euler.challenge))


(deftest potential-strings-test
  (is (contains? (potential-strings [8 7 3 7 8 2 9]) "useruby")))

(deftest scoring
  (is (made-of-words? "useruby"))
  (is (not (made-of-words? "flbzrrr")))
         )

(deftest integration
  (is (= ["useruby"] (word-breakdowns [8 7 3 7 8 2 9]))))

dfs.clj

(ns euler.dfs
  (:use clojure.set))

(defn dfs [node neighbors predicate]
  (if (predicate node)
    node
    (some #(dfs % neighbors predicate) (neighbors node))))

(defn dfs-all
  ([node neighbors predicate]
   (let [new-finds (if (predicate node)
                     #{node}
                     #{})]
     (reduce
       union
       new-finds
       (map #(dfs-all % neighbors predicate) (neighbors node))))))

dfs_test.clj

(ns euler.dfs-test
  (:use clojure.test
        euler.dfs))
(deftest
  dfs-test
  (testing
    "dfs"
    (let [graph {1 [2 3 99999]
                 2 [4]
                 3 [8]
                 4 [11]}
          root 1
          neighbors #(get graph % [])
          predicate #(> % 10)]
      (is (= 11 (dfs root neighbors predicate)))))

  (testing
    "dfs-all finds all of the dfs hits"
    (let [graph {1 [2 3 99999]
                 2 [4]
                 3 [8]
                 4 [11]}
          root 1
          neighbors #(get graph % [])
          predicate #(> % 7)]
      (is (= #{99999 11 8} (dfs-all root neighbors predicate))))))