PA5 – Boggle

Introduction

This program provides an opportunity to use recursion for the essential algorithms to play a word game called Boggle.
Boggle is played with a 3×3 or 4×4 board of randomly generated letters. In the physical game, cubes with letters on each face are shaken and then settled into a square tray with slots for each cube. Our computer game will generate letters using a random number generator; the letters will then go into a 2D array.
An egg timer (which counts down to zero from three minutes) is started. Players attempt to form words from the letters on the board. Successive letters in a word must appear adjacent in the board vertically, horizontally, or diagonally, and no cube can be used twice in the same word. For example, consider the board below.

AKHG
NTER
MEJA
POWL

You can probably see how to form the words mop, owl, teem, meet, ether, and many more. On the other hand, wow cannot be formed because it uses the W entry twice, and then cannot be formed because E and N are not adjacent.
Players write down the words they find until the egg timer runs out. Words found by more than one player do not count for points. Words less than two letters score no points. All other words earn points as follows: three and four letter words earn one point, five letter words earn two points, six letter words earn three points, seven letter words earn five points, and words of eight or more letters earn 11 points.
The first player to get to 100 points wins.
Our computer version of Boggle has a user play against the computer. The computer uses a dictionary to find words. Of course, if the computer has a large dictionary, it will always find all the words that can be found on a board, and it will be unbeatable, which is not fun. Hence the computer has a much smaller dictionary of at most 1000 words to start with (you can use this file to seed your dictionary if you like). However, the computer learns words the longer the game is played, so its dictionary gradually expands, making it harder to beat. There are ten difficulty level, corresponding to the probability that the computer will learn a word. Difficulty level one means there is a 10% chance the computer will learn a word, difficulty level two means there is a 20% chance that the computer will learn a word, and so on up to difficulty level 10, which means the computer learns all new words.

During a round, the computer displays a grid of letters, a countdown timer, and enables an area for the user to type words. When the count down timer runs out, the round ends and the results are displayed.

After a round, the computer displays the scores, the words found by both the user and the computer, the words found by the user only, the words found by the computer only, and the words typed by the user that are not on the board (it is easy to make this mistake, so the computer checks). At this point, if the user typed a non-word by accident, he or she can remove it from the user-only list (it is also easy to mistype). Furthermore, if there is a word that the computer found that is not really a word (because a non-word found its way into the dictionary), it may be removed as well. The scores are adjusted and any non-words are removed from the dictionary. The user may begin another round at any time.

The computer also keeps track of whether the game is over.

The user may change the target score for a completed game, but this restarts the game. The user can also press a button to restart a game, or quit the program.

Program Design

The UML diagram below shows the design for this class. The Boggle class is in the default package and does nothing but create and start the graphical user interface for the program. You will be given this class. You should not change it.

The gui package has three classes that together implement the graphical user interface for the program. You will be given this package. You should not change any of the code in this package.

The gamePlay package contains all the classes constituting the “guts” of the game. You will be given some of these classes and you will need to implement some of them yourself. Once all these packages and classes are written and put together, you will be able to play Boggle on the computer.

Once all these packages and classes are written and put together, you will be able to play Boggle on the computer.

Provided Classes

Here we provide following classes and interfaces. You should not change these classes.

EggTimer
This class uses a separate thread (an independent process that does not interfere with other processing in the program) to count down from three minutes to zero. Other classes interested in the time can register as listeners for this class. Every second, it calls the tick() method of all its listeners, which can then react to this notification. The gui code uses the EggTimer to implement the three-minute countdown timer.
TickListener
This interface must be implemented by any class that listens to the EggTimer.
Game
This is the class that controls the game. It tells all the other classes in this package when to do things, scores rounds, monitors plays, and so forth. Although you do not need to change this class, you may find it helpful to look at it to see how it interacts with the classes that you are writing.

UML

Classes You must Modify or Create

You must write the remaining classes in the gamePlay package.

The Board class implements the Boggle game board. Besides the specifications provided in the UML diagram, it must do the following.

  1. The grid and inUse fields must be 2D arrays. The grid holds the letters (which must be lowercase), and the inUse array holds indicators for whether the corresponding letter in the grid is in use as part of a word. This is how the word-search algorithms can tell whether a letter has been used in a word already (remember, a grid element may be used at most once in each word).
  2. The LETTER array must be an array of 96 lowercase letters. The letters occur in exactly the same proportion as they do in a real (physical) Boggle game. Thus a letter can be gotten from this array for the board by generating a random integer between 0 and 95. You will be given the contents of the LETTER array.
  3. Board() and Board(char[][] grid)—The first constructor is used in the game; the second is for testing. The first constructor must fill the grid with NON_LETTER characters. Both constructors must set all the locations of inUse to false.
  4. mix()—This method must generate random letters according to the distribution in LETTERS and place them in the grid, and set all the locations of inUse to false.
  5. char charAt(int row, int col)—Return the letter at grid[row][col]. If row or col is out of bounds, then return NON_LETTER. If the letter at grid[row][col] is already in use, it should return NON_LETTER.
  6. char useCharAt(int row, int col)—Return the letter at grid[row][col] and mark it as in use. If row or col is out of bounds, then return NON_LETTER. If the letter at grid[row][col] is already in use, it should return NON_LETTER.
  7. unUseCharAt(int row, int col)—Mark the letter at the given grid location as not in use.
  8. boolean isOnBoard(String word)—Search the board for word, and return true iff the word is on the board (according to the rules of Boggle). This method should return true for empty string and false for null. This method MUST use a recursive algorithm.
    1. It is totally fine for this method to call a private helper method.
  9. boolean isInUse(int row, int col)—Return the boolean value at inUse[row][col]. This method is only used for testing.

You will be provided a skeleton Board class that has the LETTER array in it.

The Player abstract class contains all the functionality common to both the computer and human players. Besides the specifications in the UML diagram, it must conform to the following specifications. You should use HashSets when creating Set instances.

  1. Player()—This constructor must set the fields to reasonable values.
  2. resetScores()—This method must set both score fields to zero.
  3. assignRoundScore(int s)—Set the roundScore to s and increment the totalScore by s.
  4. decrementRoundScore(int s)—Reduce the roundScore and totalScore by s.
  5. setWordSet(Set<String> set)—Do nothing if set is null or empty. Create a new HashSet for the wordSet field. For each string in set, if it is null or empty, go to the next string. Otherwise, if it contains a non-letter character, go the next string. Otherwise, change the string to lowercase and add it to wordSet.
  6. int getRoundScore()—Return the roundScore.
  7. int getTotalScore()—Return the totalScore.
  8. Set<String> getWordSet()—Return the wordSet.

The HumanPlayer class must implement the findWords(Board b) method to do nothing.

The ComputerPlayer class must conform to the specifications in the UML diagram as well as the following specifications.

  1. ComputerPlayer(Dictionary d)—This constructor must call its super constructor and assign d to the dictionary field.
  2. findWords(Board board)—This method must create a new HashSet for the wordSet field. Then it must search board for any words in the dictionary, and add any that it finds to the wordSet. The algorithm this method uses MUST be recursive. The algorithm MUST NOT simply go through the dictionary and see if it can find any words on the board – this is too inefficient. Instead, it must find candidate words on the board and see if they are in the dictionary.
    1. It is totally fine for this method to call a private helper method.

The Dictionary class must conform to the specifications in the UML diagram as well as the following specifications.

  1. The list field holds the words in the dictionary, which must be all lowercase and sorted. The list must remain sorted when words are added to it or deleted from it. The sizeWhenSaved field records the length of list when it was last saved to a file. The fileName field is the name of the file where the dictionary is stored.
  2. Dictionary()—This constructor must create a new ArrayList and assign it to the list attribute, set fileName to "dictionary.txt", and load the dictionary from a file named fileName into list. It must assure that each loaded word is lowercase. It assumes that the dictionary file has one word per line with no extra whitespace (the only whitespace is the newline characters). It must assure that list is sorted. (Note that with this file name, the system will look for the file in the current directory when the program is executed.)
  3. Dictionary(String filename)—This constructor must create a new ArrayList and assign it to the list atribute, set fileName to filename, and load the dictionary from a file named fileName into list. It must assure that each loaded word is lowercase. It assumes that the dictionary file has one word per line with no extra whitespace (the only whitespace is the newline characters). It must assure that list is sorted.
  4. save()—Write the dictionary to the file fileName. At most 1000 words randomly selected from list are written to the file. If the list has fewer than 1000 words, all are written to the file.
  5. learn(String word, int prob)—Add word to the dictionary with probability prob/10. If list has grown by at least 20 words since it was last saved, then save it. The list must be still be in order after this method runs.
  6. forget(String word)—Remove word from list, or do nothing if word is not in list. The list must still be in order after this method runs.
  7. boolean isWord(String word)—Return false if word is null or empty. Otherwise, return true iff word is in list. This method MUST use a binary search to look for word.
  8. boolean isPrefix(String prefix)—Return false if prefix is null or empty. Otherwise, return true iff prefix is the start of a word in list. For example, ent is a prefix of entire, so if “entire” is in list, then isPrefix("ent") must return true. This method MUST use a binary search to look for prefix in list.
  9. boolean isSorted()—Return true iff list is sorted. This method is only used for testing.
  10. String getWord(int index)—Return list[index]. This method is only used for testing.
  11. int size()—Return list.size(). This method is only used for testing.

Hints and Recommendations

Although you are given a lot of code for this game, it will not provide a good basis for testing the code you write. You should write your own JUnit tests for your classes and make sure they work before trying to integrate them with the rest of the code for the game.

The code will be available on the Canvas page for your class.

Assignment Specifications

Your code must conform to the CS 159 coding standards, which are posted on Canvas.

Your code will be checked for correctness in AutoLab. You may submit as many times as you like in AutoLab.

Your code will be checked for for overall quality, called Elegance in AutoLab, by me. I will look for things like good variable names, appropriate control structures, decent comments, and so forth. I will also ensure that the algorithms that are supposed to be recursive, are recursive. You will lose more than 10 points if this is not the case.

Your classes must be in packages specified in the UML diagram.

You must zip the gamePlay directory into a zip file called pa5.zip that you will submit to AutoLab. To make sure that you have done this properly, when you unzip the file, it should create a gamePlay directory with all the gamePlay package files in it (those you wrote and the ones we gave you).

Due Dates and Deliverables

This program is due by midnight, Thursday April 17th. You must submit your code in AutoLab (autolab.cs.jmu.edu). The submitted file must be called pa5.zip.

For Professor Fox only: you must submit a hard copy of the code you wrote by the due date. The program is late if both deliverables are not submitted on time.