Discovering words from letters in Clojure (Letterpress Solver)

Question

I created a Letterpress solver that will take a string of letters and return a list of valid words that can be constructer with the provided letters. Not all letters need to be used in each word.

This works by reading all words into a list named dictionary, transforming that list of words into a map, letter-permutations, keyed on ordered letters (as a list of characters) with values of vectors containing anagrams of the key letters.

Then, calling find-words with a string of letters and a lower bound for word length, will find all distinct combinations of those letters with lengths from the lower bound to the size of the input string.

The combinations are then map'd over letter-permutations to pull out all valid words that can be made.

(def dictionary
  (clojure.string/split-lines (slurp "words")))

(def letter-permutations
  (group-by sort dictionary))

(defn get-combinations
  [letters lower-bound upper-bound]
  (mapcat #(distinct (combo/combinations letters %)) (range lower-bound (inc upper-bound))))

(defn find-words
  [letters lower-bound]
  (mapcat letter-permutations (get-combinations (sort letters) lower-bound (count letters))))

This works extremely well for letter Strings up to 22 characters in length. But with 23 characters and upwards there is a drastic increase in the amount of time taken, when the response will come in bursts of words with long pauses (garbage collection?) between each batch.

My testing for the above stats has been with the string "otxtzlsunowayzoyiwqyocetl" (which may of may not be my current board :)), but I've experienced the same same behaviour occurring for other strings as well.

I'm happy to hear feedback on all of the code, but particularly for insights to the cause of the bottlenecks and suggestions of how I could improve this.

Full source code can be seen on Github

Answer 1

The (distinct (combo/combinations letters %)) looks mighty troublesome to me. I don't know what the complexity function is for combinations offhand, but I'm going to guess it's got a factorial in it. Using distinct around it means that you will hold that entire set of combinations in memory. That's one of those things that works well for small numbers, then falls off a cliff.

I also think this is one of those kinds of problems that can benefit significantly from memoization if structured properly. (Although memoization creates a cache in memory, so you might want to build your own with a customized cache to avoid blowing the heap. This is pretty easy with core.memoize.)