You are here: Home / Past Courses / Fall 2012 - ECPE 177 / Homework / Homework 3 - C Programming on Linux

Homework 3 - C Programming on Linux

Objective: Gain familiarity with the C programming language, including dynamic memory allocation, pointers, file I/O, and string manipulation.  No network programming is required for this homework assignment. (That is coming next - in the projects!)

 

Word Search Problem

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)!

hw2 - Word Search Puzzle

 

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.

Example data file (e.g. data.txt):

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!

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:

  1. A sample search puzzle with dimensions of at least 20x20
  2. A sample program input containing words to search for (covering both normal cases and boundary cases). This file contains everything that the user would type to run your program.

Example test case file (e.g. test_case.txt):

data.txt
happy
and
hope
spring
cat
new
exit

I will run this test input file using Unix input redirection to have your program read from this text 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.  This should not require you to change your program in any way.

     

    Homework Requirements

    • I will compile and test your program in a Linux virtual machine that has the Eclipse CDT (C Development Tools) installed.  Don't relay on anything that wouldn't be in this basic installation!
    • You must implement the program in C and use the following GCC options in Eclipse 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)
      • These options are set in Project -> Properties -> C/C++ Build -> Settings -> Tool Settings -> GCC C Compiler. Check the box for Wall in the "Warnings" category, and add -std=c99 -Wextra in the box in the "Miscellaneous" category
      • If your program produces any warning during compilation (with these options), 5 points will be deducted.
      • If your program doesn't compile on the class server, zero points will be awarded.
    • 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.

     

    Resources

    • 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

     

    Submission

    The Eclipse IDE can package up your entire project into a Zip-compressed archive file. Inside the archive are all of your source files along with a "Makefile" indicating how your project is to be compiled and executed.  This is a common way in which Linux applications are distributed in source code form. I can uncompress, build, and run your project with the following commands

    unzip yourproject.zip
    cd yourproject/Debug
    make
    ./yourprogram 

     

    To produce the archive, go to File->Export->General->Archive File.  Select your project to include in the archive and provide a filename. Upload the resulting compressed file to Sakai. Be sure that both files in your test case are also uploaded to Sakai!

     

    Grading

    This assignment will be graded out of 100 points, with the following breakdown:

    • If your program produces any warnings during compilation (with the three specified options), 5 points will be deducted.
    • If your program doesn't compile, zero points will be awarded.
    • 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: 10 pts

     

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