Word Search

Summary

You search a grid of characters to find words from a list.

Objectives

• Practice using
  • formatted input
  • two-dimensional arrays,
• Reinforce knowledge of arrays, strings, and pointers
• Consider problem decomposition

Introduction

You will write a program that solves a "word-find" puzzle similar to puzzles that can be found in newspapers and magazines, as shown in the example below.

The input data will be a grid of characters (the puzzle board) followed and a list of words. The object of the puzzle is to search the puzzle board for the words in the word list. Words may appear in the puzzle board horizontally or vertically (but not diagonally). Horizontal words will run left to right; vertical words will run top to bottom. Words will not "wrap around" in either direction, so for example, a word could not occupy columns {15,16,1,2}. Each word will appear at most once in the puzzle board.

Program Details

The following sections detail the input and output format of your program, followed by some internal representation requirements.

Puzzle Specifications

Puzzle boards will be read from the standard input, which you already know how to read in your programs. You may send files to a program's standard input at the shell prompt using the input redirection operator <, as in the following example.

./wordsearch < puzzle-file

The first line of a puzzle file should be the dimensions of the grid—two positive integers, representing the height and width, respectively.

The puzzle board is given next. It will consist of a matrix of H×W upper-case letters, with a single space between each character on each row.

Next the file will contain a list of upper-case words, each on a separate line, and each of which could fit within the puzzle board. The number of words is not specified, so your program should read until the end of the file is reached. There will be no blank lines anywhere in the file.

16 16
G R N L R S Y S T E M E E O M R
O C O M P U T E R E H I A I C U
R A I M P R O G R A M A N R R R
Q M E M O R Y A N T C R N T T M
L A O N E T W O R K R O H H E U
G T R Y S T R I N G I A E G Q E
R R R N E A N Y L Y I L E E U R
T R P T A R E C O S S G I T A A
R L T P A R N A G O M E R U T S
E I H H T A G L I K L B S R I C
N T E Y T Y I C C M C R M I O H
Y R O S A H N U U G R A E D N E
P G R I N N E L L U U C A R S M
C G Y C E K E U R S S B A S L E
C N S S R E R S O U R R T P R B
C N P O C N R M R U A I G A S O
THEORY
STRING
ARRAY
APPLE
GRINNELL
COMPUTER
PHYSICS
CALCULUS
ALGEBRA
TIGER
SCHEME
NETWORK
PROGRAM
HOUSE
EQUATION
MEMORY
SLEEP
LOGIC
SYSTEM
PIANO

Program Output

Given the puzzle, your program should print a solution in two formats. First, it should print each word found (in any order), followed by its starting location in the puzzle (in row, column format) and its orientation. Next, it should print a visual key to the puzzle, which is a version of the puzzle board matrix containing only the words which your program has found. All other characters of the board should be removed.

The output for the example above might thus be as follows.

./wordsearch < word-search-puzzle.txt

SYSTEM (0,5) horizontal
LOGIC (6,8) vertical
MEMORY (3,1) horizontal
EQUATION (4,14) vertical
PROGRAM (2,4) horizontal
NETWORK (4,3) horizontal
SCHEME (8,15) vertical
ALGEBRA (5,11) vertical
CALCULUS (7,7) vertical
PHYSICS (8,3) vertical
COMPUTER (1,1) horizontal
GRINNELL (12,1) horizontal
ARRAY (6,5) vertical
STRING (5,4) horizontal
THEORY (8,2) vertical
          S Y S T E M           
  C O M P U T E R               
        P R O G R A M           
  M E M O R Y                   
      N E T W O R K         E   
        S T R I N G   A     Q   
          A     L     L     U   
          R   C O     G     A   
    T P   R   A G     E     T S 
    H H   A   L I     B     I C 
    E Y   Y   C C     R     O H 
    O S       U       A     N E 
  G R I N N E L L             M 
    Y C       U               E 
      S       S                 

Program Notes

Variable-Length Arrays

Like statically declared variables, but unlike dynamically allocated memory, C's variable length arrays (VLA) may not be returned from functions. Once they go out of scope, their memory is reclaimed.

However, VLAs may be passed as parameters to other functions for use and modification.

You should keep these details in mind as you consider how to declare your puzzle grids, which should not have any hard-coded upper bound on their size.

Word Lists

Likewise, your program should have no hard-coded upper bound on the size of the word list. Of course, the upper bound on the length of the words themselves is the maximal grid dimension.

Decomposition

Decomposing complex programs into small modules is essential to readability, maintainability, not to mention correctness. To ensure your program is well-decomposed, you must follow these constraints:

• Loops may not be more than doubly-nested. That is, one loop nested inside another is appropriate, but any deeper nesting is not allowed except via abstraction—function calls.
• Programs may have only one loop at each block level, except when abstracted by function calls.
• However, you may not use the C library functions strstr, strchr, or strrchr.

The following examples serve to clarify these constraints. As a result, your program will likely require several functions, making the result should be much easier to read and understand.

/* WRONG -- the two loops are at the same level. 
   Place each loop in separate functions. */
for ()
 {
   ...
 }
for ()
 {
   ...
 }

/* OK -- the two loops are at different levels */
for ()
 {
   for ()
   {
     ...
   }
 }


/* WRONG -- the two nested loops are at the same level. 
   Place each nested loop in a separate function. */
for ()
 {
   for ()
   {
     ...
   }
   for ()
   {
     ...
   }
 }


/* WRONG -- loops are triply nested, one level too deep.
   Place at least one loop in a separate function. */
for ()
 {
   for ()
   {
     for ()
     {
       ...
     }
   }
 }

Test Cases

As part of your write up, describe a set of cases that would be appropriate for testing this program. (Since designing these puzzles is non-trivial, you need not submit a puzzle of your own containing your tests, but describe what situations you would want to test.) To thoroughly test your code, you may modify the example above it if there are cases missing from it.

An (overly-simplified) list of problem circumstances might look something like this:

• include a horizontal word
• include a vertical word

Grading

In addition to the general grading guidelines for evaluation, the assignment is worth 30 points. As review, you may wish to contrast the general rubric's structural examplars for factoring and length.

• [2 points] Functions give clear, complete pre- and post-conditions
• [1 points] Assertions verify pre-conditions
• [10 points] Reads input completely and correctly
• [2 point] Reads puzzle board dimensions from input
• [1 point] Creates appropriately sized puzzle board(s)
• [3 points] Reads puzzle board from input
• [2 points] Reads words from input
• [2 points] Verifies input and handles errors appropriately
• [6 points] Correctly locates words in the puzzle
• [3 points] Locates horizontal words
• [3 points] Locates vertical words
• [5 points] Produces correctly formatted output
• [2 points] Prints location and orientation of located words
• [3 points] Prints solution board
• [6 points] Tests demonstrate correctness
• [2 points] Test plan enumerates the range of problem circumstances
• [2 points] Test cases include specific inputs and expected outcome(s)
• [1 point] Transcripts demonstrate functionality with test runs
• [1 point] Statement argues why the program is correct

A five point penalty will apply to any submission that includes personally identifying information anywhere other than the references/honesty file.