Never Lose in WordHunt Again, With Computer Science
Today, we’re going to make a lightweight solver for the popular iMessage game WordHunt with C++. It’ll be able to give us some insanely high scores and some solutions that are almost impossible for a human to come up with!
If you don’t already know, WordHunt is an iMessage game where players are given a 4x4 board of letters and drag their finger along the board to make as many words as possible in under a minute and 30 seconds. The more words that a player makes, the more points they get, and the longer the words, the higher their score is as well. The player with the highest score at the end of the time limit wins the game.
What we want to make is a solver for the game, or a program where when we give it input the board of letters, it outputs all the optimum valid words possible (or solutions) for us to put into the game. Let’s get started!
First, we need to have a list of valid words (or a literal dictionary) for us to know what a valid English word. With a simple Google search, I found one on Github. We want to save the list of all the valid words in a txt file — I called it dictionary.txt:
Now we can start coding! We can input the 4x4 board of letters as a string from left to right. For example:
We can then store this back in a 2D array (I did this for demonstration purposes, but a 1D array would be a little more efficient) with:
cout << "Enter the board:";
string read;
cin >> read;board[0] = read.substr(0,4);
board[1] = read.substr(4,8);
board[2] = read.substr(8,12);
board[3] = read.substr(12,16);
Then, we can iterate through every possible combination of letters that can be made with our given board using recursion. Specifically, we’re going to use an algorithm called Depth First Search. This essentially “mimics” a finger trying every single combination of letters possible, only a lot faster. We do this by first calling our recursive function on each letter of the board (this is where our finger would start):
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
recurse(i, j, "", ("(" + to_string(i) + ", " + to_string(j) + ")"), visited);
}
}Our recursive function is as follows:
void recurse(int row, int col, string word, string path, bool visited[4][4],
struct TrieNode *node)
{
if(row < 0 || row >= 4 || col < 0 || col >= 4)
return;
if(visited[row][col])
return;string letter = string(1,board[row][col]);visited[row][col] = true;//Here we have our current combination of letters
word += letter//Check to see if it is valid here.vector <pair <pair <int, int>, string >> directions =
{ make_pair(make_pair(1, 0), ", D"),
make_pair(make_pair(0, 1), ", R"),
make_pair(make_pair(-1, 0), ", U"),
make_pair(make_pair(0, -1), ", L"),
make_pair(make_pair(1, -1), ", LD"),
make_pair(make_pair(-1, 1), ", RU"),
make_pair(make_pair(1, 1), ", RD"),
make_pair(make_pair(-1, -1), ", LU") };for( pair < pair <int, int>, string > elem : directions)
{
int x = elem.first.first;
int y = elem.first.second;
string d = elem.second;
if(row+x >= 0 && row+x < 4 && col+y >= 0 && col+y < 4)
if(!visited[row+x][col+y])
recurse(row+x, col+y, word, path+d, visited, (node->children)[letter]);
}
visited[row][col] = false;
}
Okay! Now we’re able to have every single combination of letters possible given our board.
Now we have to check which ones are valid, and we can do this by checking which ones are in our dictionary.txt!
We can do this by storing our list of valid English words in a map data type (dictionary in Python). This is not that bad, because looking up something in a map can be done in constant time, or O(1). Here’s how we can do it:
dictionary = {};def make_dict(self):
f = open('dictionaries/470kwords.txt', 'r');
fr = f.read().splitlines();
for word in fr:
self.dictionary[word] = '1';with open('dict.json', 'w') as outfile:
json.dump(self.dictionary, outfile);
And then in our traversal of possible combination of letters, we should check if it is valid, adding it to an array of solutions, which starts off as empty (I also included the path the solver took to make the combination):
//Check to see if it is valid here.if(word in self.dictionary and len(word) > 2):
self.ans.append(word);
self.paths.append(path);
With a list of all the possible words we can answer in the game, we want to sort them by length so we can just see the best solutions:
pair = zip(self.ans, self.paths);final = sorted(pair, key=lambda x: len(x[0]), reverse=True);
for i in range(len(final)):
print(i, final[i][0]);
print(" ", final[i][1]);
Now, when we run the solver and input our board, we get a list of over 200 solutions to the board:
Not bad right? Yeah, well, definitely not good either. The program took 33 seconds to run, which is kind of long considering that the game is only 90 seconds long. We want to be using all that time to input our solutions into the game, not wait for the solver to run. So how do we make this faster?
The problem with our solver right now is that we keep continuing traversal that has a combination of letters that can never possibly make a valid word.
Let’s take this board for example:
With our solver right now, we will be on the traversal of “nbd”, and keep looking. For example, we keep traversing and will see if “nbdt” is in a valid word. We shouldn’t be doing this, because clearly no valid English word starts with “nbd”.
Using a map, there’s no efficient way for us to know whether or not to continue on a given traversal or not. Instead, we’re going to use a trie data structure to allow us to do this.
If our list of valid words was only composed of geek, geer, geez, geeks, and geekt, then our trie would look like this (Notice how the words that start with the same letters have shared nodes in the trie):
With a trie, given a traversal, we can just check if the current node in the trie has any children, or nodes connected and immediate underneath our current node. If our current node does not have any children, then we know that there’s no more possible words that can be made on this traversal, and we can stop continuing on it. If it does, then we should keep continuing on the traversal as we’ve doing normally. This saves us a ton of computation.
So, in our code, instead of making a map, we want to make a trie:
void make_trie()
{
ifstream dictionary_file;
dictionary_file.open("dictionary.txt");
string word;
if (dictionary_file.is_open()) {
while (!dictionary_file.eof()) {
struct TrieNode *curr = root;
dictionary_file >> word;
for(int i = 0; i < word.length(); i++)
{
string letter = string(1, word[i]);
if((curr->children).find(letter) == (curr->children).end())
(curr->children)[letter] = new TrieNode;
curr = (curr->children)[letter];
if(i == word.length() - 1)
curr -> full_word = true;
}
}
}
}And in our recursive function, we want to check if our current word is in our tree:
//if no children, we are at the end of possible valid combination of letters
//for the current traversal
if((node->children).find(letter) == (node->children).end())
return;
word += letter;visited[row][col] = true;//check if word is in trie
if(word.length() > 3 && (node->children)[letter]->full_word)
{
ans.push_back(make_pair(word, path));
}
Now, when we run the solver, we still get the same list of valid words, but much, much faster (in under one second):
With this solver, we pretty much win every single game:
And that’s it! We just made a solver for the iMessage game WordHunt.
Check out all the complete, commented code on my Github, along with instructions in the README on how to download and run the solver for yourself. Don’t hesitate hit me up if you have any questions or concerns!