For the first part of this assignment, you will design and implement a Trie
class
for storing and efficiently accessing Strings (as described in the lectures). Your
class must provide the following constructor and methods:
Your Trie
implementation should be case-insensitive, so adding "foo" and "Foo" would
result in a single entry. You may assume that the Strings to be stored in a Trie
consist of letters only (no spaces or puncuation marks).
As part of your Trie
class definition, you will need to define an inner class to
represent the nodes in a Trie
(similar to the ListNode
and TreeNode
inner classes we have previously discussed).
For extra credit, you may implement other useful
Trie
methods, such as remove
and iterator
.
Be sure to test your class thoroughly before moving on to part 2.
Boggle (® Hasbro) is a game in which a 4x4 grid of letters is randomly chosen, and then the players try to identify as many words in that grid as possible. Words can be formed by any sequence of adjacent letters in the grid. For example, consider the following grid.
The word "sock" is formed starting at the letter "s" in the top row, moving down diagonally to the "o", moving up diagonally to the "c", and finally moving right to the "k". Note that letters can be connected horizontally, vertically, and diagonally. The same occurrence letter may not be used more than once in the same word, however. Thus, "tot" is not a valid word in the above grid. In the real game, a player earns points for each word found in the grid, with an n-letter word earning n points. For example, "so" is worth 2 points while "strand" is worth 6 points. An invalid guess (i.e. a word not in the dictionary or not on the board) costs the player 1 point.
A BoggleBoard class has been provided
for you, along with a dictionary file named dictionary.txt.
When constructed, a BoggleBoard
reads in and stores all of the dictionary words
in a Trie
. It then uses recursive backtracking to search the board,
calling the contains
and
containsPrefix
methods to identify words from the dictionary.
Using the provided BoggleBoard
class and your own Trie
class, design and implement a GUI-based program for playing a game of Boggle. At a
minimum, your program should generate and display the board, allow the user to
repeatedly enter words, display the valid entered words, show the player the words
at the end, and allow them to play again. For example, a very basic
interface might look like the following:
For extra credit, you may add additional functionality to the game (e.g., scorekeeping, a time limit).