weight = 19

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> and Set<E> interfaces as described in the Java Collections Framework
• Write and interpret code using the ArrayList, HashSet, LinkedList, and TreeSet data structures
• Override the Object.hashCode() and Object.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 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.

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.

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) — 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 private and only called by findWords().
• 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() 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, Character letter) — the constructor
• int hashCode() — Computes the hash code using the row, column, and letter using Object.hash().
• boolean equals(Object o) — Determines if this Cell instance is equal to the given object. You may use IntelliJ to generate the equals() method.
• 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):
  • ArrayList
  • LinkedList
  • HashSet
  • TreeSet

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.

Benchmarking

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.

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