Project 1: A Recursive Word Search Program

Due Date:

Midnight Sunday February 25, 2001. Note that this means before 23:59:59 on Sunday evening. The standard late policy applies.

Objectives

The objectives of this project are:

To refresh ourselves on programming
To gain experience using recursion in programming
To better understand the importance of procedural abstraction in programming
To become familiar with LINUX and the g++ compiler

The Problem

One technique used to help young children build vocabulary and practice spelling is to have them solve a "word search" (it's also a good time filler for meetings like Cub Scouts). A word search is a 2-dimensional grid or matrix of letters which contains "hidden words". The child is given the 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 sample word search for you. 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 If you need help, the solution is available.

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 have 15 rows and 15 columns.

Your program will read data from two files.

One file contains the letters to be stored in the puzzle.
The file will contain 15 lines each containing 15 characters, terminated by a newline.
The second file contains the words that are found in the matrix.
Each word (4 - 15 characters) will be found on a seperate line. Note that the file may contain words which are not found in the puzzle and there is no limit to the number of words in the file.

Your program will accept the filenames as command line parameters, build the puzzle, print the puzzle and the location of each word in the puzzle.

The location of a word is indicated by the column number (1 - 15, starting from the left), row number (1 - 15, starting from the top) and orientation (UP, DOWN, LEFT, RIGHT) from that position in the puzzle.

Sample Run

A sample run of your program should look like the following. Note that the format of the solution is "word (column, row, direction)". linux1[17]% a.out letters.txt words.txt -- CMSC 202 Word Search Solver V1.0 -- The Word Search Puzzle: E H U K X D I C N M Y T Y L F W O C J S K L T I M H O N I I N O T G N I H S A W Z I F N P I R B W N I I W P P I E R C E B M E T V E L I I O K O W O K Q U O W C L E V E L A N D L N V N C C O O R T H T S N U N A A M K H R H F E L S I O N O M D U L N A A N E T X U Q N S U A I O A T N V E O R K B A R R M M P Z V E A N S U A L B E T S Y S D S W G N B I T C L F I O H Z O M Y D E N N E K W F D I A O T N A R G R N V T F E F K R R V F V E E D M B D M J Z The Solution: ADAMS (1, 8, DOWN) CLEVELAND (5, 6, RIGHT) GRANT (8, 14, LEFT) JEFFERSON (14, 15, UP) KENNEDY (12, 13, LEFT) LINCOLN (14, 1, DOWN) PIERCE (10, 4, RIGHT) POLK (3, 11, UP) TRUMAN (15, 11, UP) WASHINGTON (10, 3, LEFT) BOB is not present in the puzzle The files letters.txt and words.txt used to create the sample output are available here. Note that these may not be the same files used to grade your project. You must make sure that your program handles all valid and invalid inputs.

The Importance of Procedural Abstraction

When programming, one of the tricks we use to keep from losing our minds in the face of all this complication is to break the problem that we're solving into manageable subproblems. This is called problem decomposition. The mechanism we have for this in C/C++ is called a function. The idea is that once we have a function to take care of a subproblem, we don't need to worry about how it's done anymore; we know that calling this function will take care of it. In that sense the use of functions in programming is declarative; it tells what will be done when the function is called. Function implementations are procedural; they describe how this particular subproblem will be solved. The trick to picking what should go into a particular function is thinking ahead to the way in which we plan on using the function. At one extreme the entire program is just one function (the problem is broken up into just one subproblem that happens to be the same as the original problem). At the other extreme we have subproblems for every line of code that we write. The difference between a good problem decomposition and a bad one is often the difference between success and failure in programming.

The key is to decompose the problem into fairly large subproblems. Once you have your first level of subproblems, you can treat each of these separate subproblems as a problem of its own and break each of these problems down into its own subproblems. Notice that in this way, the problem decomposition that we're talking about is actually a recursive process.

So What?

In general there are many successful decompositions to any reasonably large problem. To help you practice this skill we're going to add a twist to project 1: For this project, you may not use any of the following three keywords in your project: for, while, and goto. As a general rule you shouldn't be using any gotos anyway, but it's extra-explicit for this program. By this we mean you are not allowed to use any builtin looping constructs in your program.

Ouch.

Before you panic, think about what we just discussed: procedural abstraction. If you can break your program into reasonable subproblems (functions), your use of those functions will be the same whether they were written iteratively or recursively. Remember, when we use functions all we care is what they do; not how they manage to accomplish that task. If you break your problem into good logical subproblems and make sure you solve them correctly, your program should work like a charm.

Requirements

Your program must:

Handle the command line arguments correctly
Use no explicit loops in the source code that you hand in (i.e. do NOT use the keywords 'for', 'while' or 'goto').
Print the word search puzzle with blank columns for readability
Print each word to be found and its location (column, row, orientation) in the word search puzzle
If any word can't be found, say so
Exit gracefully if either file cannot be opened
Use C++ input and output (i.e., for console I/O use cin and cout and NOT printf, scanf; for file I/O use ifstream and NOT FILEs and fread)

Your program may assume

If the word search puzzle file can be opened, it is a correct word search file.
This means that it has exactly 15 line and each line has 15 characters plus newline
If the word file can be opened, it contains one word per line and each word is between 4 and 15 characters (inclusive). There is no limit on the number of words which may be in the file.

Sample Program

A sample executable (and sample input files) is available in the directory /afs/umbc.edu/users/s/m/smitchel/pub/cs202/spring01/Project1/ on the linux.gl.umbc.edu systems. Please use it to help understand how the program should behave under certain conditions. When in doubt, make it behave like the sample program! Note: The program is an executable file compiled for linux, so the odds are fairly high that it won't run as is on your home machine. Coding Standards For this project you must follow the class coding standards. As noted above, for this project, you must write your program in C++ using C++ input/output. You may use whatever non-looping language features that you like. Using Code You Didn't Write laiming authorship of code that you didn't write is plagiarism and will be dealt with as academic dishonesty. You should not use code that you didn't write; it defeats the learning experience of the project. Compiling and Testing Your Program Remember, your program must compile and run using the g++ compiler on the LINUX machines (linux.gl.umbc.edu) using the -ansi and -Wall switches. For example, to compile and link bob.C, use the command line g++ -ansi -Wall bob.C but to compile without linking, use the -c switch as with the cc compiler g++ -c -ansi -Wall bob.C If your program does not compile or does not generate the correct output, you will not receive full credit for this project. Grading The grade for this project will be broken down as follows: 50% Correctness This tests that your program behaves the same way that the sample does. 30% Design Your code has no loops and represents a "good" top-down design 20% CMSC 202 standards Your code follows the CMSC 202 standards Submitting Your Project When you have finished and tested your project you can submit it electronically using submit. The project name for this assignment is Proj1 (note the upper-case P). As an example, to submit your files, you would type: submit cs202 Proj1 file.1 file.2 ... file.n More complete documentation for submit and related commands can be found here. You should replace all of the file.x's above with your real file names. Remember -- if you make any change to your program, no matter how insignificant it may seem, you should recompile and retest your program before submitting it. Even the smallest typo can cause compiler errors and a reduction in your grade. Last modified: 04 February 2001