Homework Assignment 3
Word Search Puzzle
Program Due: Thursday Sep. 28, 2006 at 11:59pm
The aim of this assignment is to give you more experience working with collection classes (such as ArrayLists, Strings and Hashtables), as well as to strengthen your algorithm design skills.
Given a two-dimensional array of letters (a grid) and a dictionary. Your task is to find words from the dictionary that can be spelled out in the puzzle. A word match is a straight, uninterrupted line of letters in the grid. The matching can be done in any of the EIGHT horizontal, vertical, or diagonal directions. A word should match the letters in the grid regardless of case.
The input file begins with a pair of integers
followed by a blank line. This pair defines the grid (table) size, namely it tells that
N lines contain exactly
M letters. The letters could
be either in lower- or uppercase. The grid does not contain spaces, numbers, hyphens and
any other non-alphabetical characters.
The dictionary file contains exactly one word per line.
Note that not all the words in the dictionary will be in the grid.
The Hashtable provides a constant time to put and find a word.
You output the word and a pair of integers representing its location in the grid. The first integer represents the row of the first character, and the second - the column of the first character in the word.
You are to design (or to complete) three classes: Grid, WordSearch and MainDriver.
For each of these classes we provide you with templates that present implementation requirements. You must conform to all requirements.
Create a private directory for your work, download the file lab.zip into it, and then unzip it. You should see the following files:
Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether requirements were satisfied, as well as judge the overall style of your code. Programs will be graded both on correctness as well as the style. Points will be deducted for poor design decisions and un-commented, or un-readable code as determined by your TA.
Here is the point breakdown:
FTP your implementation to
/afs/andrew.cmu.edu/course/15/200/www/handinDO NOT HANDIN dictionary.txt