UMBC CS 201, Fall 05
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,
is due: Before Midnight, Sunday 11/20/04
Engineering Change Notices
- ECN 1 clarifies loop usage.
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.
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
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
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
- 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
- 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; /* You should use a #defined constant for this size */
- 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
- 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
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 .
[wordsearch]% a.out letters.dat words.dat answers.out
Your greeting goes here
[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
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
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
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
Sunday, 20-Nov-2005 18:08:19 EST