Write a program to solve word searching puzzles, where words from a dictionary are to be found in a two-dimensional array of letters. For example, you might be given the following array:
m v j l i x a p e j h b x e e n p ph k t t h b s w y
r w a i n u y z h p p f x r d z k q t p n l q o y j y a n h a p f g b g h x m s h w y l y u j f j h r s o a
Your program is to find words from the dictionary that can be spelled out in the puzzle by starting at any character, then moving in a straight line up, down, left, right, or on any of the four diagonals. For example, the above array contains the word algorithm because it can be spelled out by starting the lower right corner and moving up and to the left; and it contains the word syzygy because it can be spelled out by starting at the s on the third row and moving down.
The purpose of this assignment is to give you an opportunity to put to work the algorithms design skills that you have learned. Thus, we will be saying very little about the algorithm for solving this problem, most of it is up to you!
Input
format. Your programs should
be run as follows:
java
–classpath . WordSearch1 array.txt dictionary.txt
array.txt is the name of the array of all lowercase
letters. We’ve provided some
examples in /projects/cse/courses/cse326/03su/hw6. This file contains the value
of N in the first line, followed by N lines of N characters each (with
characters separated by spaces).
The aforementioned directory also contains a file wordPuzzleGen.java for
creating more such files for testing.
dictionary.txt is a list of the words to search for,
for instance, /projects/cse/courses/cse326/texts/words.txt. You should convert each word to all
lowercase (see String.toLowerCase() ).
You may ignore any words of less than four letters or that contain
punctuation. You may assume that the dictionary is given to you in alphabetic
order (after converting each word to all lowercase).
Output format. Print out every dictionary word (one per line) that is contained somewhere in the puzzle. If a word appears in the puzzle more than once, print it only once. You may print the words in any order.
Requirements. In order to gain experience with hashing and with
comparing different implementations, you are required to write two separate solutions to this problem and compare them:
1.
WordSearch1.java
– a solution that somehow involves hashing in any form.
2.
WordSearch2.java
– a solution that does not make use of hashing.
You may certainly share code between your two
solutions but they should represent different approaches to the problem. You may also re-use any code that you
have previously written for this course, whether individually or as part of a
group.
Approach. We have covered a number of different algorithms that can be used effectively to solve this problem. Your task is to study the problem; come up with two possible strategies for solving it using some of the algorithms and data structures that you have learned; implement and test your solution; and then explain and defend your design in the writeup. A good writeup is particularly important for this assignment, because we expect to see a variety of solution strategies. You need to clearly explain not just what you did, but also why you did it, backed up with estimates of resource costs (time and space). Also, you should clearly explain whatever limitations you need to place on the puzzle size N and the dictionary size M. As usual, your goal is to find a decent method which works within reasonable bounds. You need not waste effort squeezing time and space out of a bad algorithm or implementing complex or highly tuned code. This problem can be solved efficiently with 200 or so lines of code (including comments and basic error checking).
1. This is an individual assignment, you must write all the code yourself. As always, you may discuss general approaches with other students, but be sure to credit them in your README.
2. We highly recommend that you carefully read this document twice through before starting any code.
You may do any, all, or none of the following. They will be worth a nominal amount of extra credit.
You should have the files WordSearch1.java and WordSearch2.java, plus associated helper files. Turn in electronically all of your source files (use *.java) plus your usual README. Follow the usual instructions. This assignment is called “hw6” in the turn-in system. Your README should contain:
Bring
to class the printouts of your source files as well as your README.
This assignment and much of the text is based on an assignment from CSE 226 at Princeton University.
For unknown reasons, that literature professor from the last assignment is still involved in your life, and still demands that all the data structures you write be your own. She has seen lots of them on the web and in other places, but those simply don't cut it! Please be sure you do not reference library data structures or copy (even partially) any code that is available from a variety of sources. The goal of this class is for you to learn how to implement and use each data structure, not simply to copy and use.
About code from the textbook: Ideally, we would like you to write the code on your own based on the descriptions/examples of the ADT operations provided in the lectures and the textbook. In this case, you could look up the code given in the textbook whenever you run into problems. Doing it this way will help you to learn the transition from descriptions of ADT operations to their actual implementation, which is one of the main goals of a Data Structures course. However, we will not take off any points if you use any of the book code as a template -- we will simply assume that you fully understand what the code is doing before using it (you may be asked to write some code in the midterm/final!). If you use any of the book code, make sure you explicitly state which parts are from the book in your README.