15-200 Fall 2006

Homework Assignment 3

Word Search Puzzle

Program Due: Thursday Sep. 28, 2006 at 11:59pm


Overview:

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.


Objectives:


Instructions:

  1. You read the input data and store it in the 2D array of characters.

    The input file begins with a pair of integers N and M followed by a blank line. This pair defines the grid (table) size, namely it tells that the next 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.

  2. Read the dictionary file and store it in the hash table. You are to use the Java API's Hashtable class.

    The dictionary file contains exactly one word per line.

  3. Print the original grid to the console.

  4. Find all words (of the length greater than 4) in the grid that match words in the dictionary and store them (and their locations) in the Arraylist.

    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.

  5. Sort the Arraylist and output it to the console.

    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.


Notes:

  1. Feel free to add any helper methods to WordSearch and Grid classes.
  2. If a word can be found more than once in the grid, output any of them.
  3. Search for words of the length five and higher.
  4. You must pay attention to boundary cases, especially in the Grid class.
  5. We advise you to start with the small input file small.txt, that represents a 4x4 grid.
  6. Once your make sure that the implementation works fine on this file, you switch to a larger file large.txt that has a 15x15 grid. For this input file we have provided you with the expected output.

What You'll Need:

Create a private directory for your work, download the file lab.zip into it, and then unzip it. You should see the following files:


Grading:

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:


Handing in your Solution:

FTP your implementation to /afs/andrew.cmu.edu/course/15/200/www/handinDO NOT HANDIN dictionary.txt