Wordament Solver

 

Many many years back in an interview I was asked to design a solver for the game Wordament. At that time I had no idea what the game was and the interviewer patiently explained it to me. I later learnt that couple of engineers in Microsoft came up with the game for the Windows phone platform and it was such a success that they went and bootstrapped a team and made that game their full time job. 

I was able to give a solution in the interview, but that always remained at the back of my mind. I wanted to go further than the theoretical solution and  really build the solver. I began tinkering with the idea a couple of weeks back and over the Thanksgiving long weekend I got enough time to sit down and complete the solution.

The sources are at github.com/abhinababasu/wordament/

You can see it in action at bonggeek.com/wordament/

Basic Idea

We begin by loading dictionary into a Trie data-structure.  Obviously there are fantastic Trie implementation out there, including ones that are highly optimized in memory by being able to collapse multiple nodes into one, however, the whole idea of this exercise was to write some code. So I rolled out a basic Trie.

If a particular Trie node is a end of word, then that node is marked as so. As an example a Trie created with the words, cat, car, men, man, mad will look as below. The green checks denote these are valid end of word nodes.

Now starting from each cell of Wordament, we start at the node for that cell character in the Trie. We look at the 8 adjacent cells (neighbors) and if there are Trie children with the same character as the neighbor, then it is a candidate to look into. And we recursively move to that node. At any point if we arrive at a valid word node, then we check to see if that word was previously found, if not, we add the word and the list of cells that created that word in the result.

Finally since Wordament gives higher score for longer words, we sort the list of words by their length.

The logic of this solution is implemented in wordament.go.

I built the solver into a web-service, that runs in a docker container inside Azure VM. The service exposes an API. Then I built a single page web-application, that calls this web-service and renders the solution.

You can hit the API directly with something like

curl -s commonvm1.westus2.cloudapp.azure.com:8090/?input=SPAVURNYGERSMSBE | jq .

The input is all the 16 characters of the Wordament to be solved.