Homework 7: Word Search

Assigned

• November 13, 2024

Due

• November 18, 2024 10:30pm

Collaboration

Regular policies for collaboration apply to this homework assignment. Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone else.

Submitting

Submit your completed word-puzzle.c file, a working Makefile, and tests.txt to Gradescope under the corresponding assignment. You may submit as many times as you like up until the deadline.

Overview

In this assigment you will write a program that solves a word-find puzzle, similar to those found in newspapers.

The input data will be a grid of characters (the puzzle board) followed by 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.

You will practice many concepts from class to complete this assignment, but one of the newer things we’ve learned is reading fomatted input.

Specifications

Put your program in a file named word-puzzle.c.

File input & Puzzle Format

Your program should use an argument to main to specify the name of the file to read from. Review a past lab if you’ve forgotten how to use command line arguments. Then you will need to open and read the file, review the relevant lab on files if needed.

Here is an example of how to run the program:

$ ./word-puzzle puzzle1.txt

The first line of a puzzle file will be the dimensions of the grid: two positive integers, representing the number of rows and number of columns, respectively. The puzzle board is given next. It will consist of a matrix of 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.

You may assume that any puzzle we use to test your code will be in the correct format.

Program output

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.

$ ./word-puzzle puzzle-1.txt

THEORY (8, 2) vertical
STRING (5 4) horizontal
ARRAY (6, 5) vertical
GRINNELL (12 1) horizontal
COMPUTER (1 1) horizontal
PHYSICS (8, 3) vertical
CALCULUS (7, 7) vertical
ALGEBRA (5, 11) vertical
SCHEME (8, 15) vertical
NETWORK (4 3) horizontal
PROGRAM (2 4) horizontal
EQUATION (4, 14) vertical
MEMORY (3 1) horizontal
LOGIC (6, 8) vertical
SYSTEM (0 5) horizontal
          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       

Decomposition and Style

This program will likely be more complex than those we’ve written before. You are required to carefully consider the organization and style of your finished program before turing it in. You should decompose your program into smaller functions for readability and maintainability. Here are some basic guidelines to ensure your program is well-decomposed:

• Loops may not be more than doubly nested. That is, one loop nested inside another is fine, but any deeper nesting is not allowed except via function calls.
• Programs may only have one loop at each block level, except via function calls.

Here are some examples to clarify these constraints:

/* 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 ()
     {
       ...
     }
   }
 }

Other Requirements

In this assignment you will need to use variable length arrays (VLAs). This means that the size of your arrays will need to be stored as a variable that we only know at runtime after reading in the file. There should be no hard coded upper bounds to the size of the puzzle in your code. The same goes for the size of the word list, there should be no hard coded upper bound. Of course, there is an upper bound on the length of the words themselves (based on the dimension of the grid).

Keep in mind that VLAs may not be returned from functions, though they may be passed as paramaters to other functions for use and modification. Carefully consider how you will declare and store the puzzle information.

Grading

Your assignment will be graded on a scale of 0–100 points based on the following criteria:

• Resources used statement at the top of your .c file, similar as in previous homework (0 points)
• The program includes a working Makefile with correctly-defined targets all, clean, and wordsearch (15 points)
• The implementation correctly reads a file as a command line argument (10 points)
• The implementation follows decomposition requirements outlined in the assignment statement (20 points)
• The implementation correctly finds and displays the solutions to the puzzle (20 points)
• The implementation has no hard-coded limits on the size of the input puzzle or the length of words (15 points)
• The tests.txt file describes a reasonably comprehensive set of tests for the implementation (20 points)
  • 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.
  • You can modify the given example if you’d like for your own testing purposes.
  • Use the tests.txt format from our previous assignment.

Code Quality

There will be potential deductions for any code quality violations. In addition to the requirements about decomposition listed above, there are additional requirements for quality code:

1. Indent the body of all loops and conditionals one level deeper than the code just outside the loop. Be consistent with your indentation style.
2. Use curly braces for every loop or conditional body, regardless of the number of lines.
3. Include comments that explain what your code does. There should be at least one comment by the start of each loop and if–else block that explains what the purpose of that code is. The comment should not simply restate the code; it should add information for a human who reads the code and is confused.
4. Give variables descriptive names that help a reader understand what they will be used for. Likewise, use sensible naming conventions for file names, for matching .h files, etc.
5. Do not read from or display the value of any variable without first initializing it.
6. Your code must compile with no errors and no warnings.
7. Use multifile decomposition where appropriate, include guards in any .h files.

Acknowledgements

This problem is adapted from Henry Walker, supplemental problem 5.