Lab 9: Word Search
Learning Outcomes
- Have a thorough understanding of commonly used library data structures
- Use data structures in software design and implementation
- Use the
Collection<E>
andSet<E>
interfaces as described in the Java Collections Framework - Write and interpret code using the
ArrayList
,HashSet
,LinkedList
, andTreeSet
data structures - Override the
Object.hashCode()
andObject.equals()
methods to use an object with hashing-based collections - Understand and apply recursion in algorithm development
Overview
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, recursiveSearch()
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 the 8-way search.
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.
4-Way Search
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.
U | L | E | A |
A | O | A | P |
F | R | O | P |
H | V | K | T |
8-Way Search
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.
|
|
Implementation
GameBoard
Class
You must implement a class called GameBoard
that will manage the grid of
letters. Each 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
The 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, boolean isFourWay)
— 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 declaredprivate
and only called byfindWords()
. When this method is called, a deep copy of theHashSet
must be passed to it.findWords(boolean isFourWay)
— 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. The value ofisFourWay
determines whether the 4-way or 8-way search is employed.
recursiveSearch()
Details
The 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.
GameBoard.Cell
Class
The 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, char letter)
— the constructorint hashCode()
— Computes the hash code using the row, column, and letter usingObjects.hash()
.boolean equals(Object o)
— Determines if thisCell
instance is equal to the given object.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 four arguments:
- The following search technique (exactly as shown):
- 4way
- 8way
- 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):
- ArrayList
- LinkedList
- HashSet
- TreeSet
The program must produce the following output to 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. Be sure that you do not include time to load the files or display the results.
Benchmarking
You must include sample results running your program as follows:
java -jar 2852[username].jar 4way data/grid3x3.txt data/words.txt ArrayList
java -jar 2852[username].jar 8way data/grid3x3.txt data/words.txt ArrayList
java -jar 2852[username].jar 4way data/grid4x4.txt data/words.txt LinkedList
java -jar 2852[username].jar 8way data/grid4x4.txt data/words.txt LinkedList
java -jar 2852[username].jar 4way data/grid6x6.txt data/words.txt HashSet
java -jar 2852[username].jar 4way 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.
Exception Handling
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
WordSearchCLI
class 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.
Acknowledgements
This assignment was originally developed by Dr. Chris Taylor and Dr. RJ Nowling.
Note: Word lists contain lowercase letters while the grids contain uppercase