I was recently introduced to a mobile (among other platforms) game by
the name of Word Trek. It is in the same family of games
as Boggle. After playing for a while, I began to realize that the game
was a bit more challenging at times than I thought. I wanted to get
some hints without having to watch ads a couple times an hour for just
a few extra points.
True puzzle enthusiasts will of course consider this blasphemy, but
the result can just be used in cases of extreme frustration :)
But on to the code. The github repository can be
The goal was to build a solution that takes a string-representation of
a Word Trek matrix and the lengths of the words being searched for, then
compute a list of all possible solutions to the matrix. A solution is
considered a path through the matrix, where no positions in the matrix
are repeated, and the characters at each node (in order) form a word
from a provided dictionary. I pulled my dictionary from here.
The matrix above has been plugged into the API, where the resulting
solutions are shown. The quality of the words will depend on the
quality of the dictionary used.
A naive approach to the problem (and my first attempt), is to generate
all possible paths one might follow on the matrix, and then remove all
paths that aren’t words in the dictionary we loaded. The problem we
rapidly run into is that even in a 4x4 matrix, there are usually
millions of possible paths to take. With some optimization techniques
we can speed up the process a little, but the big win is to reduce the
size of the input by short circuiting paths that we know will never
I did a bit of Googling, and came across a great thread
on Stack Overflow discussing this exact problem. A solution using a
trie ended up being the most compelling. I know that
Lucene uses this data structure under the hood in order to achieve
search at the level of performance we’ve become accustomed to, so I
brought in a Clojure wrapper around Lucene, weavejester/clucy.
The above code creates an in-memory Lucene index
using clucy, and adds a collection of strings to it,
effectively creating our trie. The prefix? function accepts a trie
and a string as inputs, and tells us whether the string appears as a
prefix to any of the words in our dictionary. We can use this function
to short circuit any paths in the matrix that won’t lead to any words
being discovered. Our workload sees a massive reduction by following
this simple idea. I have used a depth-first search as my graph-walk
Finally, tying it altogether, we have the public function from the
There are a few helper functions I haven’t included in this port but
can be found in the core namespace provided in the project. Once
more, the repo can be found here.
Happy Word Trekking! Just remember to solve a few on your own from
time to time.