Building a Word Game Solver

06. August 2016 Problem Solving 0
Building a Word Game Solver

So, the other day one of my colleagues, Sashoto Seeam, told me, “Did you play LetterPress, the #1 word game of iOS?”

I said, “No, i don’t have an Apple device.”

He said, “Whatever, let me show you. This is a game where you play with your opponent at online where you just need to make a valid word from the scrabbled letters given in a 2-dimensional grid. The longer word you can make the better. We can easily win this game using our programming knowledge.”

I asked, “how?”

He said, “well, if we can write a program which can scrap all the words of dictionary and search through it for the possible matches of our options from the scrabbled letters of the game, then we will have better chances to win.”

I said, “lets do it then.”

First he proposed a idea where we make a list of dictionary words. Then from the scrabbled letters, find all possible combinations of the letters to make words and match them with the dictionary words to check validity. Matched words would be our option to use.

Can you guess the complexity of it’s implementation? Horrible idea, i know.

So i came up with a better idea.

First we make a list of dictionary words. Then from that dictionary words we would make a TRIE tree. So, all of our valid words are in a well-structured form. Then we just need to check if we can find valid words using our letters. lets say we have 4 letters ‘HAWT’ to make our word. Now starting with the letter ‘H’ we try to move on the TRIE tree with our next available letters, here ‘AWT‘. Every time we pick a letter and search recursively through the to see if we have a move. When we find a letter which is a leaf of the tree, we know that we found a valid word. We pushed it to a list. So after iterating with all of the letters, we will have a list of words which we found valid in the TRIE tree. Then we just sort the list in decreasing order of the length of the words. and TA DA!

See, here are some of the valid words we can make using ‘HAWT’.

THAW
WHAT
TAW
WAH
HAT
……..

……..

 

Don’t ask if any of the words are seems weird. I didn’t make it. The dictionary words are taken from this Github Repo.

I wrote the code using Java and it is available here. You can use your own dictionary words if you wish. Just replace the ‘dictionary.txt’ file with your list of words.

 

As it is mentioned in my repository:

This project is done just to practice algorithm, there was no bad intention of cheating or whatsoever. Don’t use this game to cheat on real game. We are not responsible for any mis-use.


Thanks my another colleague and good friend Syed Sirajul Islam Anik for helping us to scrap the dictionary words from the github repo.

 

Let me know about your feedback or suggestion in comment.


Leave a Reply

Your email address will not be published. Required fields are marked *