download
There are two things I find interesting about this program and I will discuss both here, starting with the simpler of the two.
Assuming we have a list of words (a dictionary) and a 4x4 grid of random letters (a Boggle board) how can we make a computer figure out if a given word is located on the board? While there are always
multiple ways to accomplish any programming task, I used the following approach. First I scan the board looking for the first letter in my word. Once I find that letter I have my starting place on the board. Now I call a recursive function which looks for the next letter in the word on each of the adjacent dice. If I find a die with my next letter on it then the function gets called again, but this time we start at this new location and we look for the next letter in the word. Each time we find the letter we are looking for we need to mark that location on the board so that we don't re-use the same exact letter again later in our word. If we ever find the last letter in our word then we have found the word and we can stop. If we have looked at all the adjacent dice and we cannot find the letter we are looking for then we need to un-mark the die we are at so that it may be used later in the word and fall out to the previous level of recursion. If we fall all the way out of the recursive function without having found our word then it must not exist at this location on the board and we can continue scanning the board to see if the first letter in our word exists in another location. Once we have checked every place on the board where our starting letter exists and not been able to find our word anywhere then we know the word is not on the board. I have always been a fan of recursive functions and I enjoy when I get a chance to use them so, for me at least, searching for a word on the board is fun and interesting. By the time I finished working on this program I was no longer using this function but my final product still uses recursion and is basically the same concept in reverse (instead of trying to find a word on the board, I find all the possible patterns of letters on the board and see if they are in my dictionary).
Which brings me to the other part of the program that I find interesting; the dictionary. The original dictionary that I found for the program was about 30,000 words each of which was listed on a
separate
line. When it came time to check the words the players had typed, the first thing I did was scan through the dictionary file a line at a time to see if the typed word was in the dictionary. This was slow so I was thinking of ways to speed things up. At the same time I was looking for a more comprehensive dictionary file and I came across an 80,000 word dictionary which was formatted very differently from my original one. Instead of having a single word on a line, this file had a few capital letters followed by a space and then some lowercase letters, another space, more lowercase letters and so on. This would look something like the following:
ADVIS e ed ee ees er ers es ing or ors ory
The capital letters indicate the beginning of a word and the lower case letters are all the things you can tack onto the beginning to form a word. In this case we get advise, advised, advisee, advisees, adviser, advisers, advises, advising, advisor, advisors and advisory. This gave me the great idea to take the same idea and expand it so that the dictionary is as compact as possible. I made the following data structure:
struct LETTER_NODE
{
bool endOfWord;
LETTER_NODE nextLetter[26];
};
When I read words into my program from the dictionary it adds them to the data structure like this:
Before the game begins I search the board for every single word in the dictionary and compile a list of all the words on the board. This is a very quick process because large chucks of the dictionary can easily be skipped. Let's say we find the letter B on the board but there is no BR to be found. We can immediately skip past all the words in the dictionary which start with BR. In this case that would mean we could skip 713 words or about 0.9% of the dictionary I am using. 0.9% may not sound like a lot, but little percentages like that add up quickly. Also the 713 words I am talking about are only the ones which start with BR, but we will also be able to skip most of the words which have a BR in them so words like abridge and inebriate and all their conjugations will be skipped as well. This new method of storing the dictionary and searching the board to compile a master list before the game begins takes a split second on any computer I have tried it on (the oldest I have used was a 300 megahertz Pentium 2, which incidentally was the the first computer I put together back in Junior year of high school).