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