CSC 427: Data Structures and Algorithm Analysis
Fall 2006

HW5: Tries & Program Design

Part 1

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:

public Trie() // constructs an empty Trie public boolean add(String word) // attmepts to add word, returns true // if success (not already stored) public boolean contains (String word) // returns true if word is already // stored in the Trie public boolean containsPrefix(String pre) // returns true if pre is the prefix // of a word in the tree public int size() // returns the number of words stored public void clear() // clears the Trie

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.

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.

c k s z x o t h d g r n z n a m

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).