Lab 4: C Programming Project

Overview

This C programming project focuses on dynamic memory allocation, pointers, file I/O, and string manipulation.

Program Description

In this homework assignment, you will write a program to solve a word search puzzle. An example puzzle is shown below, along with the search words. The goal of the puzzle is to find each search word. The trick is that the search words are surrounded by random characters. Further, the search words can appear forwards, backwards, horizontally, vertically, or diagonally (in either direction)!

This program will read a puzzle from a text file saved to disk. The first line of the file should contain the dimensions of the grid (rows, then columns). On subsequent lines, the actual grid of characters should be provided. The input may contain upper and lower case characters, but you should convert them all to lower case when you read them. Here is an example input file:

10 7
ABCDEFt
SsGKLaN
OPpRcJW
PLDrJWO
ELKJiIJ
SLeOJnL
happyTg
BEoREEa
JFhSwen
ALSOEId

In that input file, you could search for the following words:

happy
and
hope
spring
cat
new

When launched, your program should print a welcome message and prompt the user for the name of the input file. If that file exists, open the file and read in the first line (containing the grid size). Because the size of the grid is variable, you must use dynamic memory allocation to create an array (of characters) large enough. (See the demo program under Resources for dynamic memory use). Populate the array with the input grid, and convert all characters to lower case at the same time.

During normal operation, your program should repeatedly display the grid on the screen, and then prompt the user for a word to find. For each word, your program should search the grid for the word. A word could appear in the grid forwards or backwards, horizontally, vertically or diagonally (either direction), with the characters in the proper order in adjacent cells. Further, different words might share characters. Search for the word in all directions if necessary (8 total including the reverse of the word) and say whether or not it was found. In order to indicate where a word was found, change its characters to upper case in the grid. This change should persist through future word search iterations. When you are finished, the user should be able to "search" for the special word "exit" in order to instruct the program to terminate. Remember to release dynamic memory before exiting!

Requirements: Makefile

You must create a Makefile for your program (with the name Makefile). I should be able to enter the directory containing your code and type "make" to trigger compilation. If the Makefile is broken, or if I need to type anything else (or dig into the source code to figure out how to compile your program), your program will be returned to you with no grade assigned.

Use the following GCC options in your Makefile to set the compiler to a very picky mode:

-std=c99 (Use the more modern C99 standard for the C language)
-Wall and -Wextra (Turn on all warnings and extra warnings. By viewing and fixing issues that generate warnings, you will produce better, safer, C code)
Warning: Don't delete the existing -c flag flag in the Makefile example from the previous lab! (It is essential to Makefile operation)

Configure your Makefile so that the name of your program binary is word_search

Makefile grading nodes:

If your program produces any warning during compilation (with these options), 5 points will be deducted.
If your program doesn't compile on my virtual machine (and the error is such that your code wouldn't compile on any of your classmate's machines either!), zero points will be awarded.

Requirements: Memory Structures

Use a two-dimensional array of characters to store the current state of the grid. You must use dynamic memory allocation to store this array, since there is no limit to grid size. Remember to release dynamic memory before exiting! How can this be accomplished? In C, a two-dimensional array is simply an array of arrays, and you can allocate a single-dimensional array using malloc() or calloc(). This method is documented at the C FAQ site.

Tip: A demo program that uses dynamic memory allocation is provided for your reference. Note that it stores an array of integers, while you will want an array of characters. It can be compiled and run with the command:
unix> gcc dynamic_2d_array.c -std=c99 -o dynamic_2d_array

Requirements: Test Case

As part of this lab, you must submit a test case that demonstrates your program operation, including both valid and invalid human input. This test case has two components:

A sample search puzzle file with dimensions of at least 20x20
A sample human input file that contains test values that a human would enter on the keyboard (covering both normal cases and boundary/error cases)

Here is an example of what a test case should look like. The sample search puzzle file used in the demo above could be stored in the file search_puzzle.txt:

10 7
ABCDEFt
SsGKLaN
OPpRcJW
PLDrJWO
ELKJiIJ
SLeOJnL
happyTg
BEoREEa
JFhSwen
ALSOEId

Then, the sample human input file could be stored in the file human_input.txt. Note that this file is exactly what a person would type at the keyboard while running the program! This is the same input that was used to run the demo program output above.

search_puzzle.txt
happy
error
hope
exit

The human input file can be run using Unix input redirection. Via this mechanism, your program can automatically read from this file instead of standard input (i.e. the keyboard) with no code changes required! The command to accomplish this is simple:

unix>  ./word_search < human_input.txt

Be sure to test that your test case functions in this manner.

Note: When you use input redirection, the input will not be echoed on the screen in the same way that keyboard input is echoed. It is OK if your program output looks a little strange in this mode. You don't need to adjust your program code to accommodate this.

Requirements: Other

I will compile and test your program in a Linux virtual machine that meets the installation process followed at the beginning of the semester. Don't relay on anything that wouldn't be in this default installation!
You must implement the program in C
You cannot use global variables.
You must use both header files (.h) and source files (.c) where appropriate
You must create a C structure for a datatype called WordSearch that is saved in a header file. The following information (at a minimum) should be contained in this structure

Number of rows in the grid
Number of columns in the grid
Actual grid of characters

You must use functions with WordSearch parameters. The actual division of the program into functions is up to you. Suggested functions include: create a grid, read a grid, search horizontally, etc...

The function prototypes must appear in the header file(s)
The function definitions must appear in the source file(s)

You cannot write duplicate search functions for "forwards" and "backwards". Instead, you must reverse the word itself, and then call your original 4 search functions (horizontal, vertical, diagonal 1, diagonal 2)
You must not search the grid excessively! Efficiency is important. For example, if you find a word, save the location and direction of the word so that you can efficiently change it to uppercase letters.
All source files must be commented, including your name and email address.
Feel free to use fancier text editors or IDEs that auto-indent your code and provide other convenience features. Just note, however, that you still must have a Makefile that allows your project to be compiled by typing make at the command line! (i.e. I will not install any IDEs on my computer, and still should be able to compile your project).

Geany (fancy code text editor) - install via sudo apt-get install geany
CodeBlocks (cross-platform IDE) - install via sudo apt-get install codeblocks

Requirements

You must submit a test case (described above) including sample puzzle input file and sample program input file.
All source files must be commented, including your name and email address.

Getting Started

First, go to the directory that will hold your project.

unix>  cd ~/bitbucket/2014_fall_ecpe170/lab04

Second, write your program in this directory! It's easy...

Here is one way to approach this lab in a step-by-step manner:

Create a .c file for source code and .h file for header information. Put in a few lines of code - just enough to compile and produce some output.
Create the Makefile - you'll need this to compile your program! Base this off of the advanced "Makefile-4" from the previous lab, but call it Makefile here.
Test the Makefile
Create a Word Search puzzle file (or copy the example above for a fast start)
Add these files to your version control repository, and commit a new changeset. Be careful - don't include any of the temporary files your text editor might create! Those end in a tilde (~).
Write file I/O code - Read in the crossword puzzle file and echo the output on the screen (for debugging)
Test file I/O code
Commit a new changeset to version control
Write dynamic memory code - Save the Word Search puzzle a dynamic array created based on the demo program code.
Test dynamic memory code
Commit a new changeset to version control
Write the game play logic
Test game play logic
Commit a new changeset to version control
... and so on ...

Resources

Need C programming resources? Visit the class Resources page

Submission

(1) Check all of your code (including Makefile and test cases) into version control, and push to BItBucket.
Want to test your submission to ensure you don't lose points due to version control errors? You could do a checkout of your repository into a different directory. Then, verify that all files are present and that you can still compile this copy of your project in its new location.

Warning: Don't be sloppy and add too many files to version control! 5 points will be deducted if intermediary files (i.e. .o object files) end up in your repository.
Warning: Don't be sloppy and add too few files to version control! Zero points will be awarded if missing source code or Makefiles prevent your program from compiling and running!
Warning: Make sure your Makefile has the exact name "Makefile", so that I can compile your program simply by typing "Make" in the directory.

With thanks to Joanne Selinski, John Hopkins University, for project inspiration.