Okay, so here goes my third post.
My friends and me are very fond of killing time and so we discovered and started playing this word game called Wordament one day. The game is pretty cool, but it’s freakishly addictive and even more addictive when you play it in a group. On a basic level, it’s a word game where you have letters arranged in a 4X4 grid and the idea is to make as many words as you can in the stipulated time, going in any direction without jumping letters.
One fine day, I woke up feeling all motivated and shit and decided to become productive in life. I wanted to write some code and a quick idea was to try to write code to build something that looks like or at least seems close to Wordament; and so I started.
My choice of language was Python, for obvious reasons! It also offered a lot of modules for developing GUIs - popular libraries include wxPython, Tkinter, PyGTK and PyQt. I chose to go ahead with PyQt4 after reading up a bit on what’s better among them all. If ever you need to do something similar, I would suggest you to go with PyQt. It’s simple to use and supports a wide range of functionality - pretty much anything you ever need while developing a rich UI application.
So, PyQt is basically a Python binding and cross-platform GUI toolkit of the popular cross-platform toolkit called Qt. It’s sad that I picked that up straight from Wikipedia, but come on, that’s what it is! Anyway, I’ll just paste the link here for reference, here you go! The latest version of PyQt is PyQt5, but I used PyQt4 in my application, simply because it didn’t really matter.
So on that day when I really felt like it, I sat down to write some code. I am not particularly fond of writing GUI stuff, but yeah, PyQt4 made the job easier. The interesting part though, was figuring out how to store all the words in a suitable data structure that supports fast look-up. So, I had read about this DS called Trie, but never really used it before. Now seemed a good time to use it.
A Trie is nothing but an information retrieval tree that trades memory for speed. Ideally, it is used with strings to check for the presence of a particular word in the given data set. If you are using a Trie, it means that you have brought down seach complexities to a minimum - to the length of the key being searched for. You can go ahead and read about it further if you haven’t, it’s a pretty cool DS.
So, there’s a third-party library called PyTrie which is a Python implementation of the trie data structure. It’s pretty handy to have because I didn’t need to code up and implement the data structure myself.
Then I got hold of an english dictionary (it’s a british one, but I guess I didn’t preserve the link to it, too bad) and wrote a script to insert all of these words into the trie. I then pickled this trie and imported the pickled object into my code so that I just needed to unpickle it for using it in my program. In the application, I use a separate thread that loads the trie from memory and makes it available to be used. The starting of this thread is the first thing that happens when the application is started.
Now, the task was to delve into writing the actual code. So, this is how it goes - when you launch the application and start a new game, the 4X4 grid with letters is going to appear and a 60 second timer starts to tick. You have to type in the words into a textbox and the result is appropriately populated into a textarea beneath the textbox.
My initial attempt was to create a random grid when the user clicks on the ‘New game’ menu item. Once the grid is generated, it proceeds to find all the possible words that can be formed from the letters in the grid - and that is the key algorithm of the game. Once all the words have been generated, the grid is displayed to the user when he/she can start playing.
Here’s the algo for finding all the possible words in the grid-
def find_words(self, point, prefix, visited): visited[point][point] = True word = prefix + self.grid[point][point].letter if not self.is_prefix(word): return self.total_points[word] = self.total_points[prefix] + self.total_points[self.grid[point][point].letter] if len(word) >= MIN_LENGTH and self.is_word(word) and word not in self.grid_words_list: self.grid_words_list.append(word) self.sum_total_points += self.total_points[word] for neighbor in self.get_neighbors(point): if not visited[neighbor][neighbor]: _visited = [x[:] for x in visited] self.find_words(neighbor, word, _visited)
And this is the code snippet where the function is called,
def get_all_grid_words(self): for i in range(4): for j in range(4): visited = [[False for _ in range(4)] for _ in range(4)] self.find_words((i, j), '', visited) return len(self.grid_words_list)
The idea is to use a boolean 2D array to keep track of which positions in the grid have been visited. In the caller function, I initiate the task of finding words starting with each of the letters in the grid. In the
find_words() method, I first mark the starting letter as visited and then proceed to consider the word obtained by concatenating it with the
prefix passed to the method as argument. This
prefix is the word that has been passed by the previous call to the function in the recursion stack.
This is the part where the essence of trie is highlighted. I can check if the word currently being considered is a possibly the start of a bigger word or not. If not, I do not need to pursue it further but if it is, I proceed to see if it’s a valid word. If it is indeed a valid word and if the word hasn’t been generated before by some other possible combination in the grid, I go ahead and add it to a list (the
grid_words_list member of the class). If not, I proceed further by calling the function on all of its neighbours, passing this word as the
prefix argument. This way, I extract all the possible words in the grid.
Once the words are extracted and stored in a list, I can validate the text that user inputs and check if the word is present in the grid or not. The color of the word, while being displayed in the textarea is adjusted accordingly.
One issue with the approach of creating only one random grid per game was that, sometimes there would be very few words generated from the grid. I had typically experimented with adjusting the weights of each of the letters that were going to be used when choosing a random letter using
random.choice() so that the grid contained as many words as possible, but of course that is a very inefficient approach.
To fix that I proceeded to write a thread that was going to generate games in the background and store them in a queue called
game_queue, only if the game satisfied certain requirements. I chose a lower limit of 65 words - failing which the game would not be used, and will not make it to the queue. This way, the user is guaranteed to have at least 66 words in each game he plays.
create_random_grid() method below creates a random grid which has at least 66 words that can be formed from it -
def create_random_grid(self): grid_total_words = 0 while grid_total_words <= WORDS_LOW: self.initAll() for r in range(4): for c in range(4): random_letter = random.choice(alphabet) letter = Alphabet(random_letter) self.grid[r][c] = letter self.total_points[random_letter] = letter.points grid_total_words = self.get_all_grid_words()
So yeah, that’s pretty much it. Though simple, I enjoyed writing the game and my love for Python has grown even more since. You can find the entire code in my github repository.
It is also available on the Python packaging Index here, so if you want, you can try it out as well.
For instructions on how to install the game and take it for a spin, you can have a look at the project’s README file.
Do let me know if you find something faulty or if you think something’s lacking - pull requests are more than welcome! You can also shoot me an e-mail.
That’s it for now, Cheers!