Coding Challenge — Scrabble Help
I’ve been in the Devslopes Academy (devslopes.com) for a few weeks now to review and better my iOS skills. One of the coding challenges was really challenging in my eyes, and I wanted to share that challenge and solution.
So, basically, it’s a Scrabble cheating app. You’re given 7 letters at random and then we can see what words can be made from it and how many points it is. We have a text file with all possible words. We need to store the contents of the file in a data structure, but, we can’t store the dictionary in an array since it would be inefficient to always search the entire array for possible words.
So the easy part is making the bag and assigning points to each letter.
Then we want an array with all the letters in the bag and then get an array with 7 random letters.
We also want to know how many points each letter are, so we can display them to the user.
Now, comes the hard part. First, we need to figure out how to store the dictionary, and then secondly figure out what words can be made with the letters at hand.
So, first, we need to see how to go about solving this in real life. What came to mind was to open a dictionary and search based on letters at hand. So in order to solve the first part of the challenge, we needed a dictionary like structure where we can easily search to check if a word is present. Swift’s dictionary data structure came to mind, but I couldn’t figure out how to find words with the 7 letters at hand. So, after googling around, one solution was to use the Trie data structure. Basically, we start with a node which can point to one or more nodes. So let’s say the dictionary had two words: zebra and zen. There would be a Z node pointing to an E node. The E node would point to a B node and an N node. The N node would have a property so one knows ZEN is a word. The B node would point to an R node and the R node would point to an A node. The A node would also have a property set to true to let the user know that ZEBRA is a word. The B and R node would have that property as false, so that ZEB and ZEBR aren’t considered as words. Ray Wenderlich had a tutorial on Trie which is what I used in the project.
When checking to see if a word exists like zebra, we would check if there’s a z node, and if it’s connected to e, then if it’s connected to b, and so on. Then we check if a isTerminating, and if it is, then we know zebra is a word, and would return true.
So, now we can load our dictionary into a String variable, and then get the individual words and store it in the Trie Node data structure.
Now, let’s solve the last challenge which was to be able to see possible words. So let’s see how we would solve this in real life with this hand:
So, we would start J and see if there are words that start with J, if so, then we check JU, if there is, then check JUV. Let’s say no words started with JUV, then we check JUR and so one. One check we do before checking if the words starts with a certain sequence is to check if the sequence we’re checking is actually a word. If it is, we add that to an array of possible words and still continue checking since we don’t want to stop at BAT when BATS and BATCAVE is still possible. How do we do all this in code?
So, on the GitHub page for Trie’s Data Structure in Swift, there were more functions. One was findWordsWithPrefix which we would need.
So this functions returns words that exists starting with partialWord. This function uses recursion, so the function is called again with the next letter until a letter comes which makes a word.
This checks to see what letters come after a certain word.
This function takes in a prefix and then using findLastWord and wordsInSubtrie, an array is made of words that are possible with the given prefix.
Now, we need to find a way to make a prefix. This is basically, finding all possible combinations with 7 letters. How do we do this? After googling, I came upon this resource:
There wasn’t a swift code available, so using the knowledge of Java and C++ I learned in college, I translated the code into Swift.
This is a helper function to swap values. We had JUVRTOF in our hand. So with J we want to make combos with the rest of the letters. Once we’re done with J, we’ll swap J with U and then check combos of U with JVRTOF and so on.
In this function, we take in the letters that we have in hand and a results set so that we modify it in the function. (A set is like an array, but when we add to a set, if the value already existed, then it’s not added. So, all values are unique in a set, whereas arrays can have duplicate values.) So, we make a prefix, and then get all possible words possible with that prefix and we also check if the prefix itself is a word. If the prefix has words in the dictionary, then, we swap values in the character array adding a letter to the prefix and finding words until we’ve gone through all possibilities. If a certain prefix doesn’t have any words then we go to another combination until we’ve exhausted all combinations.
So, with this final piece of the puzzle solved, we can make a cheat function to get all the words possible with 7 letters at hand.
So now, when we press the cheat button, we’ll get a list of all the words possible along with the point value.
Hope this helps.
