Lab 3: C Programming Post-Lab
This is the post-lab activity for Lab 3: C Programming. It focuses on dynamic memory allocation, pointers, file I/O, and string manipulation.
Word Search Puzzle 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:
In that input file, you could search for the following words:
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!
As part of your homework, you must submit a test case that represents both normal program operation and boundary cases. This test case has two components:
- A sample search puzzle with dimensions of at least 20x20
- A sample program input containing words to search for (covering both normal cases and boundary cases).
Note: I will run this test input file using Unix input redirection to have your program read from this test file instead of the standard input, i.e. the keyboard. For example,
unix> ./your_program < test_case.txt
Be sure to actually test that your test case functions in this manner.
- 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 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), zero points will be awarded.
- You must use the following GCC options in your Makefile to set the compiler to a very picky mode: -std=c99 -Wall -Wextra
- -std=c99 (Use the more modern C99 standard for the C language)
- -Wall and -Wextra (Turn on all warnings. By viewing and fixing issues that generate warnings, you will produce better, safer, C code)
- 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.
- The name of your binary should be word_search
- You cannot use global variables.
- You must use dynamic memory allocation to store the grid, since there is no limit provided on grid size!
- Tip: In C, a two-dimensional array is simply an array of arrays. Use this concept when dynamically allocating memory for the grid.
- 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.
- 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.
- A demo program that uses dynamic memory allocation is provided for your reference. It can be compiled and run with gcc dynamic_2d_array.c -std=c99 -o dynamic_2d_array. The method used (creating an array of arrays) is based on information at the C FAQ site.
- Need C programming resources? Visit the class Resources page
Post-Lab Report - Wrapup:
(1) What was the best aspect of this lab?
(2) What was the worst aspect of this lab?
(3) How would you suggest improving this lab in future semesters?
(1) Check your full lab report into version control, and push to BitBucket
(2) Check your lab and post-lab code (including all Makefiles 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.
This post-lab will be graded out of 100 points, with the following breakdown:
- Warning: If your program produces any warnings during compilation (with the three specified options), 5 points will be deducted.
- Warning: If your program doesn't compile, zero points will be awarded.
- 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!
- Division of program into functions: 10 pts
- Function efficiency: 5 pts
- Use of header (.h) and source (.c) files: 5 pts
- Use of WordSearch structure: 10 pts
- File input from test puzzle file: 10 pts
- Dynamic memory allocation for grid: 15 pts
- Prompt for words until the user enters exit: 5pts
- Find words horizontally (across a row): 5pts
- Find words vertically (down a column): 5pts
- Find words in that are left diagonal, left top to bottom right: 10pts
- Find words in that are right diagonal, left bottom to top right: 5pts
- Find the words in reverse: 5 pts
- Test case (including functioning with input redirection): 10 pts
With thanks to Joanne Selinski, John Hopkins University, for project inspiration.