# Word Trek Solver

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 found here.

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 form words.

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

Finally, tying it altogether, we have the public function from the
namespace, `solve`

.

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.