Boggle! Due Wednesday, October 31
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.
Programming Your Data Structure
You will need a data structure to hold Strings, which you program yourself (no using Java's), and which implements the following methods (you will want to be exact about the method signature, as I'll give you code that uses some of these):
- void insert(String word): This method inserts this String into the data structure. If the word already is in the data structure, it should not add it again.
- boolean find(String word): This method tells you whether the String word appears in this data structure.
- Queue<String> allWords(): This method returns a Queue filled with all Strings that appear in the data structure. Because you are already an expert on Queues, you may use Java's built-in Queue interface, which is implemented by LinkedList (e.g. Queue<String> q = new LinkedList<String>();).
It is your choice what data structure to use, but as you will see, there are rewards for it being fast.
Your program will have two instances of your data structure: one to hold every word in the English language, and one to hold the words that your program finds in the Boggle board.
What I'm Giving You: A Tour
Here's a tarball which contains some code which will be helpful for you. Untar it with tar xzf project2.tgz
In there, you'll find five files. Let's start with american-english.
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.
- Board has two fields; a 2-dimensional char array (for encoding the dice rolls), and an instance of your data structure called englishWords (for holding every word in the English dictionary).
- The constructor first calls newGame() (we'll get there), then builds englishWords. It then reads every word from american-english and adds it to englishWords. You have one line to repair so it builds your data structure. 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 if you use the same seed.
- newGame() 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. You don't have to do anything for this.
- static countPoints(Queue<String> q) takes a Queue full of Strings, and returns the number of points that word list gets in Boggle. You don't have to do anything for this.
- Queue<String> allWords() returns a Queue 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 s, int r, int c, boolean[][] used, YourDataStructure foundwords) is the recursive helper method to do the heavy lifting. The String is the word as built so far. r and c 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 and Player.java are already written to allow you to play against the computer; you just have to set the type of data structure in Player.java. 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 contest.
What You'll Give Me
You'll submit all .java files, along with a README (called README, not README.txt, or readme, or readme.txt, or Readme.txt... just README, please) telling me about what you did. What data structure did you use? Which of the below steps have you reached?
Submit as Project2.
Grading
Step 1 (75 points): Finish the project with a Binary Search Tree as your data structure.
Step 2 (100 points): Make some improvement on the above to make it faster. AVL Tree? A cleverly-sized Hashtable? Something else you learned about on the internet? Defend your choice in your README. What's the runtime of your three methods?
You can change anything you like about the program to speed it up, as long as OnePlayer still works.
For the following extra credit points, you only qualify if you get a 100 on the rest of the project.
5 extra-credit pts: You successfully finished Step 2, and OnePlayer.java runs faster than anybody else's in your section.
5 extra-credit pts: You successfully finished Step 2, and OnePlayer.java runs faster than anybody else's across all three sections.
5 extra-credit pts: You successfully finished Step 2, and your OnePlayer.java runs faster than my OnePlayer.java (I know this is possible). My OnePlayer.java runs in less than .4 seconds on my laptop.
Other Notes
Please Javadoc and inline-comment your data structure, so it is easy for me to understand. Additionally, please inline 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
Example Output
This file contains the result of running my program with java OnePlayer 0
This file contains the result of running my program with java OnePlayer 10
This project was inspired by one written by Owen Astrachan at Duke University.