Overview

In this lab, you will complete a partially-written a program to find all the words in a dictionary that can be spelled by combining adjacent letters in a game board of letters.

Screen Shot of Program

Procedure

Most of this application has already been developed. The exception of is the core recursion algorithm, which you must complete. You will also need your Dictionary class that you implemented in lab 4 (and have updated based on your instructor's feedback). The remaining files that you need for this assignment can be found in the WordSearch.zip (download) file.

Note: You are required to place the lab6 folder from the .zip file in your IntelliJ src folder, rename the lab6/username folder to match your MSOE username, and place your Dictionary implementation in the same folder as the WordFinder implementation.

The WordSearchApp class contains the main method. The class is responsible for reading two input files: one is a "dictionary" file containing a large number of words. The other file consists of a grid of letters (as in the example below). The dictionary words are loaded into your Dictionary class from lab 4, and the grid of letters is stored in an ArrayList<GamePiece<Character>> structure. When executed, the program produces an output file containing all possible combinations of adjacent letters on the game board that are found in the dictionary. You will use the words.txt file from lab 4 for this assignment.

You are required to implement the recursive algorithm for the recursiveSearch() method of the WordFinder class. 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 the dictionary. There are two variations of the recursive search that must be implemented: 4-way and 8-way. The do8WaySearch parameter determines which variation of the search should be executed. 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.

Consider the 4-way search on the game board below. 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.

The recursion algorithm must be structured such that words with fewer than 3 characters or more than 15 characters should not be considered. Three example files (grid1.txt, grid2.txt, and grid3.txt) are included in the .zip file for the assignment. You must process the file containing the 4x4 grid (grid1.txt) using both a 4-way and an 8-way search. You must process the file containing the 8x8 grid (grid2.txt) using only a 4-way search - the 8-way search will likely take too long. Save the output files and note the times taken to process the files for the various searches. You may find it useful to disable the GUI when performing the benchmarking since the GUI will slow down the processing.

Note that the WordSearchApp initially creates a data structure for the dictionary based on SortedArrayList<String>. Once you get your program working, change SortedArrayList<String> to ArrayList<String> and re-process the 4x4 grid for both 4-way and 8-way searches. Save the output files and note the times taken for the two searches. Compare those times using ArrayList<String> to the times using SortedArrayList<String>. It's also worth noting that the game board files consist of uppercase letters while the dictionary supplied in the .zip has only lowercase letters.

Comments are provided within the WordFinder.recursiveSearch() method that describe how you should implement the method.

Optional Components

There are a number of additional things that you may wish to explore. Here are a few ideas:

• Compare results when using a LinkedList for the collection.
• Modify your Dictionary class to optimize performance.
• Create an interactive game allowing the user to play against the computer.
• Something else...

All of these are optional. Make sure you complete the basic requirements before moving on to the optional components.

Demonstration

Upon completion, demonstrate your working implementation to your instructor (see your instructor's guidelines for when and how to do this).

Sample Results

As a preliminary test of your implementation, you may wish to use the following as input:

TDG
AEY
SIL

This should produce the following 4-way search results:

The following 17 words were found:

	deasil
	dei
	deil
	dey
	easily
	eat
	edgy
	lie
	lied
	lis
	lye
	sae
	sat
	tae
	tas
	yea
	yeas

and the following 8-way search results:

The following 77 words were found:

	ail
	ailed
	ais
	ate
	ates
	daily
	dais
	date
	dates
	deasil
	dei
	deil
	del
	deli
	delis
	des
	detail
	dey
	dye
	dyes
	easily
	eat
	edgy
	eta
	etas
	ged
	gel
	get
	gey
	ilea
	lea
	lead
	leady
	leas
	led
	ledgy
	leg
	lei
	leis
	let
	ley
	lie
	lied
	lies
	lis
	lye
	lyes
	sad
	sade
	sae
	sail
	sailed
	sat
	sate
	sated
	sea
	seat
	sedgy
	sei
	sel
	set
	seta
	tad
	tae
	tael
	tail
	tailed
	tas
	tea
	teas
	ted
	teg
	telia
	yea
	yeas
	yes
	yet

Acknowledgements

This assignment was developed by Dr. Mark Hornick and Dr. Chris Taylor.

Lab Deliverables