Lab 6
Get started now
## Overview In this lab you will make use of recursion to find all of the words that can be created by connecting adjacent letters in a grid. In addition, you will modify the `AutoCompleter` interface and corresponding implementations from [lab 4](Lab4). ## Resources * [2000words.txt](/taylor/files/2000words.txt) &mdash; List of words, one per line * [words.txt](/taylor/files/words.txt) &mdash; List of words, one per line * [grid2x2](grid2x2.txt) &mdash; a $2 \times 2$ grid of letters * [grid2x3](grid2x3.txt) &mdash; a $2 \times 3$ grid of letters * [grid3x3](grid3x3.txt) &mdash; a $3 \times 3$ grid of letters * [grid4x4](grid4x4.txt) &mdash; a $4 \times 4$ grid of letters * [grid6x6](grid6x6.txt) &mdash; a $6 \times 6$ grid of letters * [`SortedArrayList.java`](SortedArrayList.java) &mdash; An implementation of the `List` interface that keeps elements in sorted order Note: Word lists contain lowercase letters while the grids contain uppercase characters. ## Word Search This assignment was inspired by the [Boggle](https://en.wikipedia.org/wiki/Boggle) board game originally distributed by Parker Brothers. A $4 \times 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 8-way search and may implement the 4-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 <kbd><font color="magenta">LEAP</font></kbd> is a legal letter combination since <kbd><font color="magenta">L</font></kbd> is to the West of <kbd><font color="magenta">E</font></kbd>, which is to the West of <kbd><font color="magenta">A</font></kbd>, which is to the North of <kbd><font color="magenta">P</font></kbd>. However, <kbd>APE</kbd> is not a legal letter combination because <kbd>E</kbd> is not a N, S, E, or W neighbor of <kbd>P</kbd>. <table> <tr> <td>U</td> <td><kbd><font color="magenta">L</font></kbd></td> <td><kbd><font color="magenta">E</font></kbd></td> <td><kbd><font color="magenta">A</font></kbd></td> </tr><tr> <td>A</td> <td>O</td> <td>A</td> <td><kbd><font color="magenta">P</font></kbd></td> </tr><tr> <td>F</td> <td>R</td> <td>O</td> <td>P</td> </tr><tr> <td>H</td> <td>V</td> <td>K</td> <td>T</td> </tr> </table> ### 8-Way Search Now consider the 8-way search. The colored text in the following sample game board demonstrates legal letter combinations for <kbd><font color="blue">LOOT</font></kbd>, <kbd><font color="red">APE</font></kbd>, and <kbd><font color="green">ROPE</font></kbd>, but the letters that formed <kbd><font color="green">ROPE</font></kbd> may not be used to form <kbd>PORE</kbd> since <kbd>R</kbd> and <kbd>E</kbd> are not adjacent to one another. Also note that <kbd>ROAR</kbd> is not possible since you cannot use the <kbd>R</kbd> twice in the same word. <table><tr> <td> <table> <tr> <td>U</td> <td><kbd><font color="blue">L</font></kbd></td> <td><kbd><font color="red">E</font></kbd></td> <td><kbd><font color="red">A</font></kbd></td> </tr><tr> <td>A</td> <td><kbd><font color="blue">O</font></kbd></td> <td>A</td> <td><kbd><font color="red">P</font></kbd></td> </tr><tr> <td>F</td> <td>R</td> <td><kbd><font color="blue">O</font></kbd></td> <td>P</td> </tr><tr> <td>H</td> <td>V</td> <td>K</td> <td><kbd><font color="blue">T</font></kbd></td> </tr> </table> </td><td> <table> <tr> <td>U</td> <td>L</td> <td><kbd><font color="green">E</font></kbd></td> <td>A</td> </tr><tr> <td>A</td> <td>O</td> <td>A</td> <td><kbd><font color="green">P</font></kbd></td> </tr><tr> <td>F</td> <td><kbd><font color="green">R</font></kbd></td> <td><kbd><font color="green">O</font></kbd></td> <td>P</td> </tr><tr> <td>H</td> <td>V</td> <td>K</td> <td>T</td> </tr> </table> </td><td> </td> </tr></table> The recursion algorithm must be structured **such that words with fewer than 3 characters or more than 15 characters should not be considered**. ## AutoCompleter Updates You must add the following method to the `AutoCompleter` interface from [lab 4](Lab4): * **`contains(String target)`** &mdash; Returns `true` if and only if `target` is contained in the auto completer object. This method should throw an `IllegalStateException` with the message "Must call initialize() prior to calling this method." if `initialize()` has not been called prior to the call to this method. In addition, you must: * If you implemented the `AutoCompleter` as part of your controller class, you'll need to separate out implementations of the `AutoCompleter` into classes that can be used in this lab. * Update all of the classes from your lab 4 submission that implemented the `AutoCompleter` interface. * Implement an additional class that uses the [**`SortedArrayList`**](SortedArrayList.java) class to implement the `AutoCompleter` interface. ## `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 * An `AutoCompleter` object that can query the word list * Any other attributes needed to implement the required functionality The `GameBoard` class must implement the following methods: * **`GameBoard(AutoCompleter strategy)`** &mdash; Constructs a game board object that makes use of the `strategy` to determine if a letter sequence is found in the word list. The `strategy` object passed in should already be initialized. If `strategy` has not been initialized, the constructor should throw an `IllegalArgumentException` with a descriptive message. Hint: call `getLastOperationTime()` and if it throws an `IllegalStateException`, catch it and throw a `IllegalArgumentException` instead. * **`load(Path path)`** &mdash; Loads a grid of letters that make up the game board. * **`recursiveSearch(int row, int col, boolean[][] visitedFlags, String partialWord)`** &mdash; returns a list of all words that begin with the letter at position (row, col) that are found in the `AutoCompleter`. This method should be declared `private` and only called by `findWords()`. * **`findWords()`** &mdash; 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 &mdash; 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. The `visitedFlags` parameter represents a two-dimensional array of values that indicate whether a grid position has already been visited. You'll need to maintain this in order to avoid reusing letters in the same word (e.g., avoiding identifying <kbd>ROAR</kbd> in the example board above). ## 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 &mdash; name of a file that contains a grid of letters * Wordlist filename &mdash; name of a file that contains a list of words * Strategy &mdash; a description of the strategy to be used. You must include the following strategy options (exactly as shown): + <kbd>SortedArrayList</kbd> + <kbd>ArrayListIndexed</kbd> + <kbd>LinkedListIndexed</kbd> + <kbd>ArrayListIterated</kbd> + <kbd>LinkedListIterated</kbd> 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. You may choose whether or not to include duplicates if the word is found multiple times. * 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 4. 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 grid3x3.txt words.txt ArrayListIndexed` * `java -jar 2852[username].jar grid4x4.txt words.txt LinkedListIterated` * `java -jar 2852[username].jar grid6x6.txt words.txt SortedArrayList` In addition, you must experiment with the different `AutoCompleter` 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 report that describes the rationale for the trial runs you performed, includes the benchmarking results of your tests, and summarizes your conclusions. ## 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 `AutoCompleter` class that optimizes the run-time * Add an option to do a 4-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. &mdash; 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. <figure>[![User Interface](wordsearch.png)](wordsearch.png)<figcaption>Figure 1: Optional GUI</figcaption></figure> ## Lab Deliverables > See your professor's instructions for details on submission guidelines and due dates. > * Dr. Taylor's students: See below > * All other students should refer to Blackboard > >If you have any questions, consult your instructor. ## Acknowledgements This assignment was developed by [Dr. Chris Taylor](/taylor/).

Thursday, 04-Apr-2019 13:23:17 CDT