Project 2: Boggle!
In this project you will implement various
Map data structures in
attempt to write the fastest Boggle solver possible. You will do so
without using the
java.util library, which means, you'll have to
do ALL the implementation work yourself for the Map's; however,
prior data structures will be provided for you.
This project is due Sunday, October 30th at 2359
- Max Grade: 70% (optional before doing a higher max grade)
- Complete an O(n) or greater Map data structure (e.g., a BST) and use it complete Board.java
- Max Grade: 90% (required before doing a higher max grade)
- Complete an O(log n) AVL implementation of a Map and use it complete Board.java
- Max Grade: 100%
- Use another data structure (e.g., an HashTable or something else!) implementation of a Map and use it to complete Board.java. You must describe your hashtable solution in your README file
Partial credit and deductions will be provided based on quality of work. If you complete the AVL, you do not need to use another O(n) performance Map, to receive credit in the AVL category; however, before moving on an attempting another data structure, you must have completed the AVL first. And, of course, you must fully complete the interface with all methods working as expected
Generally, the following grading criteria will be applied:
- Accuracy: E.g., Are all set keys present and return consistent answers?
- Performance: E.g., How fast does get and set run?
Speed competition between students:
- +2 Points: Fastest submission in your section (plus a mystery prize!)
- +3 Points: Fastest submission across all sections (plus a double mystery prize!)
Speed competion with instructors:
- +3 Points: Submission is faster than Dr. Aviv's AVL solution!
- +2 Points: Submission is faster than Dr. Aviv's fastest solution!
It is possible to not be the fastest in your section (or across sections) and still produce a solution faster than Dr. Aviv's.
You can run Dr. Aviv's solution for the
java OnePlauer 0 execution
on a lab machine with the following commands.
As a guide for improving your code, you should try running your
-Xprof option, e.g.,
java -Xprof OnePlayer
which will print out performance statistics about which part of your code is the slowest.
Submission and Starter Code
All starter code for this project can be obtained via the
~aviv/bin/ic312-up and submission will occur via
You must submit the following edited file(s):
README: Containing any attributions or notes for grading
For your additional data structure, place this in the ic312 package directory properly labeled. You must describe your data structure in your README.
DO NOT submit non-compiling code.
You Board.java Submission should include the fastest implementation you developed. Non-compiling Board.java files will not be graded.
The following files will be provided for you to complete the project and you should not edit them:
output0.txt: sample run of
java OnePlayer 0
output10.txt: sample run of
java OnePlayer 10
american-english: english language dictionary file
TwoPlayer.java: Two player Boggle game
OnePlayer.java: Single player Boggle game
ic312 data structure package files are also
provided for you and should not need to edit them:
You'll be programming a Boggle game with an unbeatable computer player. Read all this before beginning. Before we move on to the actual programming, let's review the rules of Boggle. Boggle consists of 25 dice, each of which have different letters on the six faces (one face of one die has a "Qu"). The dice are rolled, and placed at random in a 5x5 grid, so that they look like this:
Players then have 1 minute to find as many words in the letters as they can, moving horizontally, vertically, or diagonally one space. For example, the above board has the word "TIN," starting in the upper right, moving to the left one spot, then moving diagonally, down and to the right. Dice may not be reused in a given word. For example, the above does not have the word "TINT," because we may not reuse the "T" in the upper right in a given word.
Scoring depends upon the number of letters in the word. Words with 3-4 letters get 1 point, words with 5 letters get 2, 6 letters gets 3, 7 letters gets 5, and 8+ letters gets 11.
There are two different programming challenges in this assignment. The first, is we will need a data structure to store words in. The second, is we will have to find out which words exist in a given Boggle board.
You will be required to complete an AVL datastructure that implements
the Map inteface, as defined in
ic312/Map.java. Once completed, you
may implement a second data structure, to be placed in the base
directory of the submission.
A Tour of the Code
The follow files are provided for you to use and retrievable via
american-english is a text file consisting of every word in the
English dictionary which uses the standard 26 letters (no accented
letters). There are 64,117 words in this document.
Board.java is where a lot of the magic happens. Places that need
your attention are labeled with TODO.
- A Board instance has three class variables; a 2-dimensional char
array (for encoding the dice rolls), an instance of a
englishWords(for holding every word in the English dictionary), and a random number generator (for rolling the dice before you start).
- There are two constructors, one of which takes a seed for the random number generator, and one which does not. The one that accepts a seed makes debugging easier, as you'll get the same Boggle board every time as long as you use the same seed. Both constructors call two functions to set up the game:
initDictionary()reads every word from the file american-english and adds it to englishWords. You have one line to repair so it builds your data structure.
initBoard()handles the rolling and placement of the dice, based on the actual dice that come with a game of Boggle. When it is done running, the field board is filled with chars. You don't have to do anything for this.
toString()is a toString. It's used when printing the Board, and uses fancy unicode characters to draw a box around it. You don't have to do anything for this.
static countPoints(List<String> l)takes a List full of Strings, and returns the number of points that word list gets in Boggle. You don't have to do anything for this.
List<String> allWords()returns a List full of all words that appear in this game of Boggle. It requires a lot of work. First, it creates a 2-D boolean array called used. Remember how a given word may only use each die once? This array encodes which die have been used. It starts as all false. Second, you'll build an instance of your data structure called foundWords to hold all the words that you find. Then, for each possible row and column combination, you'll call the recursive helper method.
void allWords(String sofar, int row, int col, boolean used, Map<String,Boolean> foundWords)is the recursive helper method to do the heavy lifting. The String is the word as built so far. row and col are the row and column we're currently on. used encodes which dice have been used already, and foundWords is there to get filled when we encounter actual English words. Obviously you'll want to change the type of foundWords to be your data structure. In order to speed things up, go ahead and assume no words exist longer than 8 letters. If your final product is fast enough, perhaps you'll be able to take that restriction off (my solution doesn't have it).
TwoPlayers.java is already written to allow you to play against the
computer; you just have to set the type of your data at one or two
spots. This is fun when you've finished, to see how badly you're
beaten by the computer (very badly).
OnePlayer.java is a main method used to see what words the program
found in the board. This also does the timing that we'll use for the
Please thoroughly comment your data structure, so it is easy for me to understand. Additionally, please comment the method allWords() in Board.java.
In attacking this project, I recommend starting with a BST, even if you have grander designs. So, make the BST, and make sure the methods it needs have work. Then work on the Boggle algorithm. Once that works with a BST, then you can swap in different data structures.
Don't forget that Q is automatically followed by a 'U.'
The project must be written in Java.
If you find yourself getting a StackOverflowError, there are two possible reasons for this. One, you have infinite recursion taking place. Two, your data structure isn't great, and it's just gotten too tall. You can increase the size of the stack allowed by Java by using the -Xss flag. The following runs OnePlayer with 2MB of stack space:
java -Xss2m OnePlayer