Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

share|improve this question
    
I wondered about if distinct was lazy too. Also, the dictionary is much smaller why not loop through that and see what can be made? –  thattommyhall Feb 1 '13 at 22:35
add comment

1 Answer 1

up vote 3 down vote accepted

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.)

share|improve this answer
    
The distinct usage did bother me, and that was before realising that it keeps all of the combinations in memory. It seemed like a good solution to combinations returning duplicates when a letters occur >1 time in the input. But I'm less sure of that now. Thanks for your input. –  Dan Midwood Feb 1 '13 at 22:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.