UMBC CS 201, Fall 05
UMBC CMSC 201 Fall '05
CSEE | 201 | 201 F'05 | lectures | news | help

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

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

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


CSEE | 201 | 201 F'05 | lectures | news | help

Sunday, 20-Nov-2005 18:08:19 EST