You have been captured by the sinister Gamemaster of Bademjan, a sadistic fiend with an affinity for riddles and games! Your only saving grace is that he recently also captured Garry Kasparov, the world's greatest chess player. Because he is absorbed with the task of beating Kasparov, he has little time and energy to devote to your demise.
In his preoccupation, he only had time to whip up a few word hunt puzzles, which might be familiar to you from your childhood. Each puzzle is a rectangular grid of random looking lowercase letters followed by a list of words you must find within the grid. The Gamemaster is no fool, however, and he has made the puzzles of gargantuan size in order to foil your efforts. Fortunately, he failed to notice that you have your laptop with you. The only thing you need to do now is write a program that can solve the problems before the Gamemaster returns. If he can finish defeating Kasparov before you can complete your puzzles, he will certainly execute you in the most excruciating manner.
This problem heavily uses both arrays and Strings. You will need to create two classes, Puzzle and PuzzleSolver. The Puzzle class will hold the grid of letters, and the PuzzleSolver class will do the actual work of finding the words within the grid.
The input to your program will be a file redirected to stdin, just like in Project 1. This file will contain both the puzzle information and the list of words you are looking for, organized in a specific format. Each file will contain an integer specifying the number of rows in the puzzle then an integer specifying the number of columns. Following these integers, each line of input will correspond to a row of puzzle data. After these lines, another integer will be given, specifying the number of words you will be looking for. After this integer, each word you need to find will appear on a separate line.
Below is a simple puzzle of size 10 x 15, with a list of 5 words to search for:
10 15 hcbnzaydffydvkc jimcyvwfiahryyu ngpzwzgrkelxmxo swphfzcesiedxux blhzollsmkswnwm hlobppahakijftc ebfpsnivdvwlztr pktagbnzoibmlni ykfvinbgjrzydsu lfxnvavktknhrsz 5 flavor fresh hiphop mad skills
You can also download this puzzle here, a larger puzzle here, and a very large puzzle here.
The Gamester was in a hurry. The problem he gave you was not very difficult, but it still requires careful programming to get it right. As you look at the problem, you have a strange feeling that you will, one day, return to this code with plans to make it run faster. For this reason, your life will be easier if you design it cleanly.
In the following section, implementation details about the classes involved in this project will be given.
We have provided the Word class. The purpose of this class is to hold a String corresponding to a word you are looking for, and, when you find it, record its orientation and starting point. Note that the starting point is defined using the Point class. By our convention, the x-value of the Point object holds the row and the y-value holds the column.
Included in this class file is a definition of the Orientation enum, whose values are HORIZONTAL, VERTICAL, DIAGONAL, and UNKNOWN. Every word hidden in a puzzle must be either horizontally, vertically, or diagonally oriented. All words start up in the upper left and continue toward the lower right. So, a horizontal word reads from left to right in a single row of the puzzle. A vertical word reads from top to bottom in a single column of the puzzle. Finally, a diagonal word starts in the upper left and moves down one space and to the right one space with each character. No words are backwards. All words can be found in the puzzle. All words (and puzzles) are lower case and made up only of characters of the alphabet.
You can download the Word class here. Do not make any changes to this file.
You will be required to create a Puzzle class. This class should hold a given instance of a puzzle consisting of the grid of characters you search through (preferably stored as a 2D array).
You are responsible for designing all necessary accessors, mutators, utility methods, and constructors for this class.
You will also be required to create a PuzzleSolver class, which is the driver class containing the main() method that makes this project work. This class should read in data from stdin and use it to create a Puzzle object and an array of Word objects corresponding to the words you are looking for.
Once the objects have been created, the main() method should perform the necessary steps to find each word and record the starting position and orientation for each one. Finally, the program should print out the list of words, in order, with the words printed first in a column 20 characters wide, followed by the start position in a column 12 characters wide, followed by the orientation.
For example, the output for puzzle.txt would be:
Word Start Orientation flavor (3,4) DIAGONAL fresh (1,7) VERTICAL hiphop (0,0) DIAGONAL mad (4,8) VERTICAL skills (3,8) DIAGONAL
This project uses command line input just like that last one. You should create several small test puzzles in addition to the ones we provide. To redirect puzzles to stdin, you would run your program as follows:
java PuzzleSolver < puzzle.txt
You are required to output the words you find in a specific way, that is, in three columns, with the widths of the first two columns fixed at 20 and 12 characters, respectively. To format output, one easy way is to use the System.out.format() method. With this method, you can specify a String that tells how the rest of the output should be formatted.
For example, if you want to print the Strings "Word", "Start", and "Orientation" in three columns where the first two are fixed at 20 and 12 characters, respectively, you would use the following line of Java:
System.out.format( "%-20s%-12s%s\n", "Word", "Start", "Orientation" );
The % character indicates a special formatting command. Then, the - character indicates that the column is left justified. Finally, the trailing 20 and 12 give the column widths. For more information about formatting this way, visit the tutorial here. For those of you who have programmed C, you will notice many similarities with the syntax for printf().
Other than specifying the names for two of the classes and giving you a third to work with, we are not giving you a lot of guidance about how to design your project. Draw a UML diagram. Try to see how the classes should interact with each other. Create short methods (one rule of thumb is roughly the size you can cover with your palm) to do a specific job, and then use those methods to make your code more readable and modular.
One good idea is to make the Puzzle constructor take a Scanner object as a parameter.
When you have tested your code and are satisfied with the results, you will need to turn in the project directory which includes all 3 Java source files. Make sure you run and test your code from the command line. DrJava does not easily support the input redirection discussed above.
To turn in your project, navigate to the directory containing your source files. Then type the following command:
turnin -v -c cs190m -p project2 *.java
You can submit your code as many times as you want. Submit early and often.
30 points will be awarded based on the functionality of the Puzzle class. All member variables in the class should be private, and you must create all necessary accessor, mutator, and constructor methods.
You can earn up to 10 points for correctly processing input.
If you can find all the words and their orientations in puzzles of arbitary size, you can earn up to 40 points.
You can earn up to 10 points for correct output and formatting.
As before, you should use good programming style and commenting in order to receive full credit. Every Java file should have a comment header at the top giving your name, the course, the project, the date, and a short explanation of the class(es) in the file.
Note: Submissions which do not compile will automatically score 0 points.
As always, be sure to uphold the high standards of academic honesty required by this course. Failure to do so can lead to consequences as dire as failing the course and expulsion from the school. If you have any questions about whether or not a given action is allowed, please ask your instructor or TA.