A boggle board is a 4x4 grid (or 5x5 for Big/Super Boggle) of boggle cubes which are similar to dice. These 6-sided dice have letters rather than numbers on the faces, creating a grid of letters on which you form words. In the original version, the players all start together and write down all the words they can find by tracing by a path through adjacent letters. Two letters are adjacent if they are next to each other horizontally, vertically, or diagonally. There are up to eight letters adjoining a cube. A letter can only be used once in forming a word, but can be used in more than one word. When time is called, duplicates are removed from the players' lists and the players receive points for their remaining words based on the word lengths.
For example, the screen shot below shows the result of one game in which the computer has significantly outscored the human. One word, reinstate found by the computer is shown highlighted on the board when the user clicks on the word in the GUI.
Your assignment is understand the classes and interfaces in a GUI-based version of Boggle. You're supplied slow, simple implementations of some classes and you'll have to write more efficient implementations. You'll also need to implement two classes using two different ideas that allow the computer to find all words on a board.
You'll implement more efficient versions of a lexicon or dictionary that facilitate looking up words and prefixes for words more efficiently than the class you're supplied.
You'll also implement two methods for automatically finding all words on a Boggle board. Each method requires writing a recursive routine based on flood-fill, the method we study/studied in class as part of the blob-finding program.
You'll write three new classes for this part of the assignment. Two are lexicon implementations and one is a class for testing your implementations. You may want to write the testing class first based on the provided SimpleLexicon so you can then test your new implementations.
In Boggle, legal words are those found in the lexicon associated with a game's model. A lexicon is simply a list of words, it's not a dictionary because it doesn't have associated definitions for each word.
The ILexicon interface specifies
the methods exported and useful for a lexicon. You're given
an implementation SimpleLexicon
implementation that has an O(n) implementation
of the method wordStatus since the implementation simply
does a linear search over the list of words it stores. Read the
documentation for details of the interface, an inheritance
diagram is given below.
You must write two new, efficient implementations. The first is based
on using binary search on an ArrayList so the class
will have an O(log n) implementation of
wordStatus. The second is based on a using a trie,
so it has an O(word-length) implementation, regardless of
how many words are in the lexicon. This is essentially an O(1)
implementation since the complexity doesn't depend on the size
of the lexicon.
BinarySearchLexicon
implementing the ILexicon interface.
Base your implementation on SimpleLexicon but don't worry about
duplicating code in your implementation. Store words in the lexicon in a
sorted ArrayList and use
Collections.binarySearch to search the list. You'll want to
read the
documentation for binarySearch. In particular, note
that when the value returned is less than zero the value can be used to
determine where a word should be in a sorted list. For example,
when looking up "ela" the value returned might be -137. This
means that "ela" is not in the lexicon, but if it were to be
inserted it would be at index 136. This also means that if the
word at index 136 does not begin with "ela" then no word
in the lexicon has a prefix of "ela". So, any non-negative value
returned by binarySearch
means the status of a word is WORD. If the value returned
is negative, one call of the appropriate startsWith
string method can determine if PREFIX should be returned (make
sure you don't go off the end of the array of words in the lexicon
when calling startsWith).
wordStatus
and the set will be used only for supplying an iterator
when the lexicon's words are accessed in order via its iterator.
LexiconTester. The main
method of the class should create a lexicon, initialize it, and
test its wordStatus method with different strings
and check the anticipated return value. For example, you could
construct a Scanner from a String such as
"big bigger small smaller sun" by creating a scanner
from the string, loading the lexicon, and then calling
wordStatus and checking the value returned. Your
test class should print errors using System.out. If all tests pass,
the class should print nothing. Here's an idea for what your
code might look like.
public static void test(ILexicon lex) {
String[] words = { "cpt", "cat", "cas" };
LexStatus[] stat = { LexStatus.NOT_WORD, LexStatus.WORD, LexStatus.PREFIX };
for (int k=0; k < words.length; k++){
LexStatus ls = lex.wordStatus(words[k]);
if (ls != stat[k]){
System.out.println(words[k] + " got "+ls+" expected "+stat[k]);
}
}
}
One class will iterate over the lexicon looking up every word in the
lexicon on the board. The other will try every possible string on the
board, looking up the strings in the lexicon. The first class
potentially searches for lots of words that aren't on the board, so the
implementation should "fail fast", i.e., minimize the search when a word
isn't on the board. The second should avoid searching for strings that
can't be part of a word. This is why the lexicon method
wordStatus returns a value you can use to avoid searching
uselessly.
WordFinder implementing the
IWordOnBoardFinder
interface. This method takes a Boggle board and a string and returns a
list of BoardCell values for the
string as found on the Boggle board.
When you've implemented the class, you should call
setFinder of
BoggleModel with a new
WordFinder object. If your class works, you can
play a game and click on a word the user enters. The words cubes
should be highlighted as shown in the screen shot at the
beginning of the handout.
The idea is to look for the string by starting at every possible Boggle cube, i.e., at every row,column of the Boggle board. If you find the first character of the string you'll continue searching in adjacent cubes for the second character. If that's found you'll look at adjacent cubes for the third character and so on. You shouldn't use a cube more than once for a string and you stop searching for a string on the board when no cube matching the current character in the string is found or when the entire string is found.
For example, when looking for "TUNE" in the board at the top of the page, there are two cubes from which a search could start since there are two cubes whose face shows "T". However, no cube adjacent to the "T" cubes has a "U", so the search for "TUNE" will fail when looking for the second character.
The cellsForWord method will call a private, helper method
that does the work. This was the same idea used in the blob-finding code
we studied. The helper method will have as parameters at least
the following:
ArrayList that will have BoardCell values
added to it as cubes are found that correspond to the the current
character in the string being searched for.
The helper method will make eight recursive calls to check all adjacent cubes. Cubes that have been used in forming a string should not be re-used.
You might find it useful to have the helper method
return a boolean value indicating whether the string
searched for is found. If the face of the cube at
the specified row, column in the helper method doesn't match
the current character of the string then false
is returned. If the face does match, and the cube hasn't
been used in forming the current word, then a BoardCell value
corresponding to the cube is marked as used/added to a list of
BoardCell values. Then eight recursive calls are made looking
at adjacent cubes for the next character of the string.
When the index of the current character being searched for is greater than the length of the string then all characters have been found and the method returns true. If no recursive call returns true then the BoardCell last marked/added to the list is unmarked/removed from the list so that it might be used later in forming the current word.
Be careful when finding a "Q" in a word since if there's a match the Boggle board cube has two characters and you'll have to take action to search appropriately.
getAllValidWords you should
first set the autoplayer's score to zero and the clear any words
already stored. This requires accessing the appropriate inherited
state from AbstractPlayer
directly, e.g., you'll write
myScore = 0;where instance variable
myScore is in
AbstractPlayer.
Here's a diagram of some of the classes and interfaces in the player
hierarchy, the IPlayer interface at the root of the
hierarchy isn't shown.
LexiconFirstAutoPlayer that extends
AbstractAutoPlayer. To find all the words on a board simply
iterate over every value in the lexicon checking to see if the word is
on the board by calling the model's cellsForWord method
that now works based on the class WordFinder you write in
the previous section.
You can then add this auto-player to the BoggleGui
by changing the code in BoggleMain.
You should then be able to play a complete game and have the computer
find all the words on the board. This requires only a modification
of the main method to create the auto-player based
on the WordFinder method.
Rather than iterating over every every word in the dictionary you can use the board to generate potential words. For example, in the board shown in the screen shot below the following words can be formed starting the "L" in the upper-left corner: lore, lose, lost, lot. From the output it's clear that "loser" isn't in the lexicon since it is on the board, but isn't shown in the output.
Starting at the cell "R" at [1,3] (recall the first row has index zero) we can form "REST" and "RESORT". Starting at the cell "R" at [0,2] we can form "ROLL" and "ROSE" as well as "REST".
Since no word begins with "GT", "GP", "GS", no search will proceed from the "G" in the lower-right after looking at more than two cubes since these two-character prefixes aren't found in the lexicon.
You'll write a recursive helper method for this class to find all the words starting at a specified [row,column]. The basic idea is to pass to this helper method at least the following:
When first called, the string built from the search so far is the empty
string: "". The current cube/cell on the board, if legal and not used in
the search so far, is added to the end of the string built so far.
If the string is a word, the word is added to a set of strings
that will eventually be returned from the original call
to getAllValidWords (this set might be a parameter
to the helper method you write). If the string is either a word
or the prefix of a word in the lexicon then
the search is continued by calling the helper method for each
adjacent cube with the string built so far. If the string
is not a prefix (or a word) then the search is cut-off at this
point and will continueom the method that called the failed-method,
which
is either the original getAllValidWords or some recursive
call that call generated.
As with all flood-fill/backtracking code you must make sure your code doesn't re-use a cube once it has been used in the current search. This means that each cube that contributed to the string built from the search so far can't be re-used in extending the string. But the cell/cube can be re-used when searching for different strings/starting from or continuing from different cubes.
makeBoard method is called. This method generates a board
by calling BoggleBoardFactory
methods. This factory uses a random number generator with a specific
seed so that when you start a sequene of Boggle games the same boards are
generated (e.g., if you use only 4x4 boards the same sequence of boards
will appear each time you launch the program.)
You can ensure that new,random boards are generated by calling
the setRandom method of the
BoggleBoardFactory class
with a java.util.Random object created without a specific
seed, e.g.,
BoggleBoardFactory.setRandom(new Random());
When debugging you may not want to do this to ensure that you have repeatable behavior. In your final program you'll probably want users to have a different sequence of boards every time.
BoardStats that generates 1000 boards
starting with a java.util.Random object initialized with a
seed of 12345.
BoggleBoardFactory.setRandom(new Random(12345));
The class should find all the words on the board using
BoardFirstAutoPlayer and print the highest-scoring board
found out of the 1000 boards. The class should repeat this "experiment",
again starting from a newly created random number generator seeded with
12345, generating 1000 boards, and printing the highest-scoring board
but this time using LexiconFirstAutoPlayer to find words on
each board.
Your code should print the total time taken to process the 1000 boards with each of the two auto-player classes. In your README be sure to document your findings including the highest scoring board and the time taken by your methods.
This assignment is worth 40 points, the breakdown is as follows:
| functionality | points |
|---|---|
| WordFinder | 9 |
| BinarySearch lexicon | 4 |
| Trie lexicon | 5 (extra) |
| Lexicon tester | 4 |
| Lexicon-first auto | 9 |
| Board-first auto | 4 |
| Stats 1000 games | 6 |
| README | 4 |
Your README file should list your testing results, all the people with whom you collaborated, and the TAs/UTAs you consulted with. You should include an estimate of how long you spent on the program and what your thoughts are about the assignment.
Submit your README and all of your source code using Eclipse with assignment name boggle.