Project 4 Fall '05

CMSC 201
Programming Project Four

Recursive Word Search

Out: Sunday 11/13/05
Due Date: Monday 11/28/05, before midnight

The design document for this project, design4.txt, is due: Before Midnight, Sunday 11/20/04

Engineering Change Notices

ECN 1 clarifies loop usage.

The Objective

The purpose of this assignment is to give you practice with recursion, writing error messages to stderr and to do some file handling where it's necessary to detect EOF. You'll also be getting some more experience with dynamic memory allocation and using command line arguments. As always, you should continue to practice using top-down design and good implementation techniques like incremental programming.

The Background

A popular form of puzzle is known as the "word search". Besides being good entertainment when waiting at the airport or at the doctor's office, this type of puzzle is often used to help young children build vocabulary and practice spelling.

A word search is a 2-dimensional grid or matrix of letters which contains "hidden words". The person working the puzzle is given a list of words that are hidden in the matrix and is asked to locate and circle them. The fun part is that the words may appear horizontally, vertically or diagonally in the grid. Horizontal words may be written left-to-right or right-to-left. Vertically oriented words may be written top-down or bottom-up. Similarly for diagonally oriented words.

Here's a simple word search puzzle for you:
It is not the same size as the ones your program has to handle.
This one is 12 X 12, not 15 X 15.

 
    G J T P B A V K U V L V 
    M N Q H S G M N T C E E 
    Y H I J S G Q E N Y C W 
    G S K M G H C B M U T H 
    R A T V M N V D G V U T 
    E P G U E A B P W Q R T 
    T J C I D D R Q T E E C 
    U P C I S E N G B U O B 
    P S J C I V N F O U N N 
    M P R O J E C T R R A M 
    O H Q T P P D S H A P G 
    C O W U K Q E G I J M S 

    COMPUTER
    COURSE 
    LECTURE
    PROGRAMMING
    PROJECT 
    SCIENCE 
    STUDENT 
    UMBC

The Task

Your task is to write a program that solves a word search puzzle. Your puzzle will NOT contain words which are diagonally oriented. It WILL contain both horizontally and vertically oriented words which may be left-to-right, right-to-left, top-down or bottom-up. All words will be a minimum of 4 characters and a maximum of 15 characters. Your puzzle will be square and will have 15 rows and 15 columns.

You are to read in the puzzle from one file and the words to search for from another file. Your program must then search for each of the words in the letters grid recursively. When the word is found, the position of its first character (row and column) must be stored and also that word's orientation from its starting position (direction).
For example in the grid shown above:

    COMPUTER begins at Row 12, Column  1 and its direction is Up
    PROJECT  begins at Row 10, Column  2 and its direction is Right
    UMBC     begins at Row  4, Column 10 and its direction is Left

Program Requirements

Your program must use command line arguments. At the command line the user must enter
(in this order):
- the name of the executable file,
- the name of the file containing the puzzle letters,
- the name of the file containing the list of words to try to find,
- and the name of the output file in which to write the answers.
You do NOT need to dynamically allocate the 2D-array of letters that holds the puzzle. Just declare it using ROWS and COLS.
HINT : If you use an array of size 15 X 15, you will have to do edge checking constantly to keep from looking off the edge of the array (a cause of seg faults). If you declare the array to be of size 17 X 17, you can "center" the 15 X 15 array within it. This is an old programming trick that makes your code easier to write in a couple of ways:
- The indices that you'll use to access the portion of the array that you're storing letters in are rows 1 - 15 & cols 1 - 15. If you are using a 15 X 15 array, the indices 0 - 14 have to be used and then translated into positions the the user will understand (1 - 15).
- You'll have a buffer of 1 row/1 column around the edges of your array, so instead of looking off the edge of your array, you'll be looking at what's in your buffer row/column. This makes it possible to have just general-use code, rather than having many if-elses with special cases of when to avoid looking over the edge.
- You are NOT required to use a 17 X 17 array. You may just find it easier.
You must use a dynamically allocated array of WORD structures to store the information about each of the words in the words file.
HINT : Since the number of words in the words.dat file is not known in advance, you'll need to use dynamic memory allocation for the array of WORD structures. But how can you dynamically allocate the right amount of memory to hold the array before reading in the words that need to be stored in it ? Go through the file once just counting the words, dynamically allocate your array, go back to the beginning of the file and this time store the words into your array of WORDs.

You must use the following structure definition.
typedef struct word { char word[16]; /* You should use a #defined constant for this size */ int startRow; int startCol; char direction; }WORD;

You must use a recursive search. Although your project may use loops to control reading in the information from the files, or to write the solutions to the output file, the search for a word must be recursive. There can be NO LOOPS or gotos used in the code that searches for a word in the letters array.
You MUST close any files that you have opened and also free any memory that you have dynamically allocated as soon as you have finished using them.
You must use separate compilation for this project.
Your program must write the answers table into a file whose name is whatever the user typed in as the last command line argument. The chart written to this file must be formatted identically to the chart shown in the sample output below.

Copying the files

The data files you need to use for this project are letters.dat and words.dat
You may get a copies of these files from my account. The files are in the
/afs/umbc.edu/users/s/b/sbogar1/pub directory.

The executable and the data files need to be in the same directory when you run the program. The commands to copy the files are:
cp /afs/umbc.edu/users/s/b/sbogar1/pub/letters.dat .
cp /afs/umbc.edu/users/s/b/sbogar1/pub/words.dat .

Sample Run

[wordsearch]% a.out letters.dat words.dat answers.out
                 
Your greeting goes here

 EHUKXDICNMYTYLF 
 WOCJSKLTIMHONII 
 NOTGNIHSAWZIFNP 
 IRBWNIIWPPIERCE 
 BMETVELIIOKOWOK 
 QUOWCLEVELANDLN 
 VNCCOORTHTSNUNA 
 AMKHRHFELSIONOM 
 DULNAANETXUQNSU 
 AIOATNVEORKBARR 
 MMPZVEANSUALBET 
 SYSDSWGNBITCLFI 
 OHZOMYDENNEKWFD 
 IAOTNARGRNVTFEF 
 KRRVFVEEDMBDMJZ 
                 

   ADAMS
   CLEVELAND
   GRANT
   JEFFERSON
   KENNEDY
   LINCOLN
   NEMO
   PIERCE
   POLK
   TRUMAN
   WALDO
   WASHINGTON


[wordsearch]% cat answers.out

Word                 Row  Col   Direction
------------------------------------------
ADAMS                  8    1   Down
CLEVELAND              6    5   Right
GRANT                 14    8   Left
JEFFERSON             15   14   Up
KENNEDY               13   12   Left
LINCOLN                1   14   Down
NEMO                   0    0   Not Present
PIERCE                 4   10   Right
POLK                  11    3   Up
TRUMAN                11   15   Up
WALDO                  0    0   Not Present
WASHINGTON             3   10   Left

[wordsearch]%

Please note that the sample output only shows what is expected from your program if the user is actually entering everything as instructed. This is not a test of the program at all, but just a sample for your clarification.

Submitting the Program

To submit your program, type the following command at the Unix prompt

submit cs201 Proj4 proj4.c followed by all the .c and .h files necessary for compilation

To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs201 Proj4