weight = 19
Lab 9: Word Search
- Have a thorough understanding of commonly used library data structures
- Use data structures in software design and implementation
- Use the
Set<E>interfaces as described in the Java Collections Framework
- Write and interpret code using the
- Override the
Object.equals()methods to use an object with hashing-based collections
- Understand and apply recursion in algorithm development
This assignment was inspired by the Boggle board game originally distributed by Parker Brothers. A 4-by-4 grid of letters is presented to players who generate a list of words that can be constructed by combining adjacent letters in the grid. No grid position can be used twice in the same word. After a timed round, each player receives a certain number of points (based on the length of the word) for each unique word in their list.
In this assignment, you will create a program that will take a grid of letters and a list of words to produce a list of all of the words in the list that can be constructed by joining adjacent letters in the grid.
You are required to implement the recursive algorithm,
method in the
GameBoard class (more details later). This method implements
the core recursive algorithm that generates all possible letter combinations
on the game board and finds all of the letter combinations that are found
in a dictionary (specified by a file containing a list of words). There are
two variations of the recursive search that could be implemented: 4-way and
8-way. You are required to implement the 4-way search and may implement
the 8-way search if you have extra time and motivation.
The 4-way search considers only the game pieces to the North, South, East, and West as neighbors. The 8-way search includes the additional game pieces to the NW, NE, SW, and SE as neighbors as well.
For simplicity, let's consider the 4-way search on the game board below first. Here LEAP is a legal letter combination since L is to the West of E, which is to the West of A, which is to the North of P. However, APE is not a legal letter combination because E is not a N, S, E, or W neighbor of P.
Now consider the 8-way search. The colored text in the following sample game board demonstrates legal letter combinations for LOOT, APE, and ROPE, but the letters that formed ROPE may not be used to form PORE since R and E are not adjacent to one another. Also note that ROAR is not possible since you cannot use the R twice in the same word.
You must implement a class called
GameBoard that will manage the grid of
GameBoard object must maintain the following data:
- The grid of game pieces
- A dictionary of valid words
- Any other attributes needed to implement the required functionality
GameBoard class must implement the following methods:
GameBoard(Collection<String> emptyDictionary)— Constructs a game board object that makes use of the collection to determine if a letter sequence is found in the word list.
loadDictionary(Path path)— Loads a collection of correctly spelled words into the dictionary data structure.
loadGrid(Path path)— Loads a grid of letters that make up the game board.
recursiveSearch(int row, int col, String partialWord, HashSet<Cell> visited)— returns a list of all words that begin with the letter at position (row, col) that are found in the dictionary. This method should be declared
privateand only called by
findWords()— Makes use of the private recursive method to generate and return a list of all of the words in the word list that can be constructed from adjacent letters on the game board.
recursiveSearch() method will need to make, at most, eight recursive
calls — on call to each neighbor (NW, N, NE, W, E, SW, S, and SE). It
should not make the recursive call if the neighbor has already been visited
or such a call is for an invalid row or column.
Cell class is used to model a letter in the grid. It stores the row,
column, and letter of the grid cell and provides functionality that allows
Cell objects to be stored in hashing-based data structures.
Cell(int row, int col, Character letter)— the constructor
int hashCode()— Computes the hash code using the row, column, and letter using
boolean equals(Object o)— Determines if this
Cellinstance is equal to the given object. You may use IntelliJ to generate the
char getLetter()— Return the letter stored in the cell
Word Search Command Line Interface
You must implement the
WordSearchCLI class. The class must provide a program
with a command line interface that accepts three arguments:
- Grid filename — name of a file that contains a grid of letters
- Wordlist filename — name of a file that contains a list of words
- Dictionary data structure — a description of the strategy to be used. You must include the following strategy options (exactly as shown):
The program must produce the following output to the the console (in this order):
- A list of all the words found. Include one word per line of output. Do not include duplicates.
- The total number of words found
- The total time required to complete the search. The time should be formatted following the same requirements as lab 1. Be sure that you do not include time to load the files or display the results.
You must include sample results running your program as follows:
java -jar 2852[username].jar data/grid3x3.txt data/words.txt ArrayList
java -jar 2852[username].jar data/grid4x4.txt data/words.txt LinkedList
java -jar 2852[username].jar data/grid6x6.txt data/words.txt HashSet
java -jar 2852[username].jar data/grid6x6.txt data/words.txt TreeSet
In addition, you must experiment with the different strategies and grid sizes (including making your own larger grid files, if appropriate) in order to characterize the completion time differences between the various strategies. You should prepare a Word document report that describes the rationale for the trial runs you performed, includes the benchmarking results of your tests, and summarizes your conclusions. Be sure to add it to your repo, commit it, and push it to GitHub.
Your program must handle any exceptions in a reasonable way.
Just For Fun
Once you have completed the requirements, you may choose to do any or all of the following:
- Develop a custom dictionary class that optimizes the run-time
- Add an option to do a 8-way search instead. An optional fourth argument could be added to the command line interface to determine if the program should do an 8-way or 4-way search.
- Create a GUI interface. — You must still implement the command line interface, but you could reuse all but your
WordSearchCLIclass in a separate JavaFX project. With a GUI, you could do lots of things:
- Animate the search progress (see screenshot below which shows a red highlight on the starting letter and progressively lighter yellow highlights on the remaining letters in the current recursive search).
- Make an interactive game where the user can play against the computer
- Your own ideas.
This assignment was originally developed by Dr. Chris Taylor and Dr. RJ Nowling.
Note: Word lists contain lowercase letters while the grids contain uppercase