Solved–Lab Assignment 2: Recursion– Solution

Description

Objectives

Review manipulating two-dimensional arrays Review text processing

Review using basic classes and objects Use recursion to solve a problem

Follow the Software Life Cycle model, with pseudocode and code refinement steps

Problem Specification

Following the Software Life Cycle model presented in class, develop a Java application that accepts a word as input from the user and searches for the word on a board with randomly generated letters on it.

The application should exhibit the following functionality (see the sample output provided):

Request for a “seed” from the user. This should be an integer in the range [1,9999] (note that 1 and 9999 are inclusive and so are valid inputs).

o A seed is useful for testing because each time the program is executed (using the same seed) the Random object will generate the same letters on the board.
Create a 4×4 board and fill the board with randomly generated letters using the Random object. Request for a word from the user and recursively search for the word on the board. Display an
appropriate message on the console indicating whether or not the word was found. If the word was found, print the board again with the verified letters (i.e. the letters of the word) marked (see Example output).

o Valid words (i.e. words that are found on the board) can start at any position on the board, and then each subsequent letter of the word is a neighbor of the previous letter. A neighboring letter is horizontal, vertical or diagonal to the current letter. The same letter cannot be used more than once per word.
Continue requesting for words from the user and searching for these words on the board until the user indicates that s/he wants to quit.

The output must follow the format of the Example Output below, specifically the formatting of the lines demarcating the positions on the board and the markings to show a word that was found on the board.

1
CS 1120 LA2 Word Search With Recursion

Enter seed: 9999
+— + +— + +— + +— +
|M||F||A||D|
+— + +— + +— + +— +
+— + +— + +— + +— +
|Y||O||D||F|
+— + +— + +— + +— +
+— + +— + +— + +— +
|G||X||B||P|
+— + +— + +— + +— +
+— + +— + +— + +— +
|Q||W||V||F|
+— + +— + +— + +— +
Enter a word to search for on the word search board:
yoda
‘yoda’ was found on the board!
+— + +— + +— + +— +
|M||F||||D|
+— + +— + +— + +— +
+— + +— + +— + +— +
|| || || | F |
+— + +— + +— + +— +
+— + +— + +— + +— +
|G||X||B||P|
+— + +— + +— + +— +
+— + +— + +— + +— +
|Q||W||V||F|
+— + +— + +— + +— +
——————————————————–

Do you want to search for another word? (Y / N)

what?

Invalid response. Y / N?

5

Invalid response. Y / N?
y— + +— + +— + +— +
+
|M||F||A||D|
+— + +— + +— + +— +
+— + +— + +— + +— +
|Y||O||D||F|
+— + +— + +— + +— +
+— + +— + +— + +— +
|G||X||B||P|
+— + +— + +— + +— +
+— + +— + +— + +— +
|Q||W||V||F|
+— + +— + +— + +— +

2
CS 1120 LA2 Word Search With Recursion

Enter a word to search for on the word search board:

Fox

‘Fox’ was found on the board!
+— + +— + +— + +— +
| M | || | A | | D |
+— + +— + +— + +— +
+— + +— + +— + +— +
| Y | || | D | | F |
+— + +— + +— + +— +
+— + +— + +— + +— +
| G | || | B | | P |
+— + +— + +— + +— +
+— + +— + +— + +— +
|Q||W||V||F|
+— + +— + +— + +— +
——————————————————–

Do you want to search for another word? (Y / N)

y
+— + +— + +— + +— +
|M||F||A||D|
+— + +— + +— + +— +
+— + +— + +— + +— +
|Y||O||D||F|
+— + +— + +— + +— +
+— + +— + +— + +— +
|G||X||B||P|
+— + +— + +— + +— +
+— + +— + +— + +— +
|Q||W||V||F|
+— + +— + +— + +— +
Enter a word to search for on the word search board:
add
‘add’ was found on the board!
+— + +— + +— + +— +
| M | | F | || ||
+— + +— + +— + +— +
+— + +— + +— + +— +
|Y||O||||F|
+— + +— + +— + +— +
+— + +— + +— + +— +
|G||X||B||P|
+— + +— + +— + +— +
+— + +— + +— + +— +
|Q||W||V||F|
+— + +— + +— + +— +
——————————————————–

Do you want to search for another word? (Y / N)

3
CS 1120 LA2 Word Search With Recursion

n

Terminating …

Design Requirements

You should have two classes in your application: WordSearchTest (your test class) and WordSearch. Your WordSearchTest class should request all user inputs, instantiate one WordSearch object and call the appropriate methods for the object to search the board for the word specified by the user. The WordSearchTest class should also display on the console the results of the word search. In addition, the WordSearchTest class should continue requesting words from the user till the user indicates that the program should be terminated.

The WordSearch class must use a recursive method to search for the word specified by the user. Recall that recursion is when a method repeatedly calls itself (one or more times) on a successively smaller form of a problem until some base condition (base case) is met. This will be useful for finding a word on the board.

NOTE: Using recursion is one of the main objectives of this assignment. A solution that does not use recursion to search for the user’s words will earn zero points.

Hints

1. The Random object (created using the seed) can then be declared as follows:

Random rand = new Random(seed);

2. The letters on the board can be of type “char”. Generating a random character is a lot like generating a random integer. Characters all have an ASCII value, which is an integer. Capitals range from ASCII values 65 to 90. So, you could use the following statement to generate a random character:

char someChar = (char) (rand.nextInt(26) + 65); // “rand” is a Random object.

3. You may want to use two identical 2-dimensional arrays to represent the board – one (the main board) that contains the letters, and another one (of type boolean) that keeps track of which cells have been visited already on the main board when attempting to find a word.

4. For the recursion, think about how you might check the board if you were doing it by hand. You might start by scanning the array (the board) for the first letter of the word. If you find a match for the first letter, you would then check each of its neighbors for the next letter—except the letters which were already identified (e.g., if you identified ‘E’ first and then ‘Y’ neighboring it, do not go back to the same ‘E’ but look for another ‘E’ which is a neighbor of ‘Y’. If one of the neighbors matches, you check its neighbors, and so on, until either reaching the end of the word or finding no matches. Think about which part of this is the recursive step, and what is the terminating condition(s).

Additional Requirements

Software Life Cycle Report

You are required to write the SLC Report, explaining how you followed the nine phases of the Software Life Cycle in this assignment.

A proper design (with stepwise pseudocode refinement), a proper coding method (with stepwise code refinement starting from the most detailed pseudocode refinement), and proper testing are essential. For reference, please see the Sample SLC Report (covered in class) on Elearning.

Note: Correct pseudocode development will be worth 40% of the total LA2 grade.

Coding Standards

You must adhere to all conventions in the CS 1120 Java coding standard (available on Elearning for your Lab). This includes the use of white spaces and indentations for readability, and the use of comments to explain the meaning of various methods and attributes. Be sure to follow the conventions also for naming classes, variables, method parameters and methods.

Assignment Submission

Generate a .zip file that contains all your files including: o Program Files

o Any input or output files
o The SLC Report (a text with description of all nine phases of the Software Life Cycle) Submit the .zip file to the appropriate folder on ELearning.

NOTE: The eLearning folder for LA submission will remain open beyond the due date but will indicate how many days late an assignment was submitted where applicable. The dropbox will be inaccessible seven days after the due date by which time no more credit can be received for the assignment.

The penalty for late submissions as stated in the course syllabus will be applied in grading any assignment submitted late.

5