Project 0: Crossword Puzzle - Spring 2024

There are no late submission folders for Project 0. You must turn it in on-time to receive credit.

Due: Tuesday Feb 13, before 9:00 pm

Objectives

  • Review the procedures to access the GL servers and to compile programs on GL.
  • Review C++ memory management (allocating and deallocating memory dynamically).
  • Use Valgrind to check for memory leaks.
  • Learn how to write test cases for a project.
  • Practice how to analyze and clarify a project's requirements.
  • To ensure that you are able to submit project files on GL.

Introduction

In this project, you will complete a C++ class. Furthermore, you will write a tester class and a test program and use Valgrind to check that your program is free of memory leaks. Finally, you will submit your project files on GL. If you have submitted programs on GL using shared directories (instead of the submit command), then the submission steps should be familiar.

In this project we develop the core part of an app. The app will be used generate crossword puzzles.

The Puzzle class enforces the manipulation of the required data structure. You are assigned the task to implement the Puzzle class. An object of the Puzzle class contains a 2D table. The following figure presents a sample crossword puzzle stored in the object. The example shows the output of the dump function in a terminal. In this presentation the row numbers and column numbers are provided to facilitate the debugging. For the simplicity the array is populated with random characters. There are no meaningful words in the puzzles this class generates. The wording of a crossword puzzle will be performed by the user of the Puzzle class.

The following figure represents the main data structure in this project. It is a 2d structure storing the state of a puzzle table.

Assignment

Step 1: Create your working directory

Create a directory in your GL account to contain your project files. For example, cs341/proj0.

Step 2: Copy the project files

You can right-click on the file linkes on this page and save-as in your computer. Then, transfer the files to your GL account using SFTP.

For this project, you are provided with the skeleton .h and .cpp files, a sample driver, and the output of driver program:

  • puzzle.h - The interface for the Puzzle class.
  • puzzle.cpp - The skeleton for the Puzzle class implementation.
  • driver.cpp - The sample driver/test program.
  • driver.pdf - The output of sample driver/test program.

Step 3: Complete the Puzzle class

You need to implement the Puzzle class according to the requirements. For the requirements please refer to the Specifications, The Table Rules, and Additional Requirements sections on this page.

Step 4: Test your code

You need to test your implementation properly and adequately. For a description of testing please refer to the Testing section on this page. Moreover, a sample test function has been provided in the file driver.cpp for your reference.

Step 5: Check for memory leaks

Run your test program using Valgrind. For example, assuming you have compiled mytest.cpp, producting the executable mytest.out, run the command 

   valgrind mytest.out

If there are no memory leaks, the end of the output should be similar to the following: 

   ==8613== 
            ==8613== HEAP SUMMARY:
            ==8613==     in use at exit: 0 bytes in 0 blocks
            ==8613==   total heap usage: 14 allocs, 14 frees, 73,888 bytes allocated
            ==8613== 
            ==8613== All heap blocks were freed -- no leaks are possible
            ==8613== 
            ==8613== For lists of detected and suppressed errors, rerun with: -s
            ==8613== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

The important parts are “in use at exit: 0 bytes” and “no leaks are possible.” The last line is also important as memory errors can lead to leaks.

Step 6: Link your shared directory

Please take this step as soon as you receive the notification indicating the shared submission folders are ready. Leaving this step to the last minute can prevent you from submitting your work on time. For example, you may lose your network connection at the moment of due time. Please note:
  * No other method of submission will be accepted due to such a problem.
  * No late submission will be accepted due to such a problem.

Follow the instructions on the Project Submission page to make a symbolic link to the shared directory in your home directory.

Step 7: Submit your files

See the “What to Submit” section, below.

The Table Rules

The following rules are part of the project requirements.

  • The minimum size of a table is 10 x 10.
  • Every row or column contains multiple separator cells.
  • The number of separators in a row or a column is between 0 and 3.

Specifications

The class Puzzle has multiple member variables as the following list:

  • m_puzzle is 2D array which stores the characters in every cell. The sizes of this data structure are specified by the member variables m_numRows and m_numCols.

Puzzle::Puzzle(int rows, int cols)
This is the constructor. It initializes all member variables and it allocates required memory if neccessary. If the user passes invalid parameters such as a negative size the constructor creates an empty object. There are certain requirements for the parameters that are passed to the constructor. If any of the requirements is not satisfied the constructor creates an empty object. For the requirements of these parameters one may refer to the section "The Table Rules" on this page.
Puzzle::~Puzzle()
This is the destructor and it deallocates the memory.
void Puzzle::clear()
This function deallocates all memory and re-initializes all member variables to default values. It clears the current object to an empty object.
void Puzzle::fill(int seed)
This function populates the table cells with random characters and proper number of separators. Dumping the object after calling this function will render a randomly created puzzle. The parameter seed can be used as the seed value for the random number generator. This function can be called multiple times to generate everytime a new set of information. The Puzzle class uses the Random class to generate random characters.
bool Puzzle::appendRight(const Puzzle& rhs)
This function appends the rhs object to the right of the current object. The append operation only happens if both objects have the same number of rows or either object is empty. If the operation is successful the function returns true otherwise it returns false. The function allows for self-append, an object can be appended to the right of itself. Please note, appending requires reallocation of memory.
bool Puzzle::appendBottom(const Puzzle& bottom)
This function appends the bottom object to the bottom of the current object. The append operation only happens if both objects have the same number of columns or either object is empty. If the operation is successful the function returns true otherwise it returns false. The function allows for self-append, an object can be appended to the bottom of itself. Please note, appending requires reallocation of memory.
bool Puzzle::reCreate(int rows, int cols, int seed)
This function re-creates a Puzzle object and fills it with random information. If the current object is already created this function clears the object and creates a new object. If the requirements are not satisfied such as the minimum number of rows and columns the function does not make any changes to the current object. If a new object is created the function returns true otherwise it returns false.
Puzzle::Puzzle(const Puzzle& rhs)
The copy constructor creates a deep copy of rhs. Reminder: a deep copy means the current object has the same information as rhs object, however, it has its own memory allocated. The new copy must be an exact copy of rhs.
const Puzzle& Puzzle::operator=(const Puzzle& rhs)
The assignment operator creates a deep copy of rhs. Reminder: a deep copy means the current object has the same information as rhs object, however, it has its own memory allocated. Moreover, an assignment operator needs protection against self-assignment. The new copy must be an exact copy of rhs.
void Puzzle::dump()
This function prints the puzzle to the standard output. The implementation of this function is provided. You do not need to modify this function. This function is for debugging purposes. Do not call this function in the test program that you'll submit. The function prints the UTF character \u2731 (namely HEAVY ASTERISK) as the separator character. If you are using a Windows computer for development you can use ASCII characters such as "#" since Windows shell does not support utf-8 encoding by default. The File windows.pdf provides instruction to activate the support of UTF characters.

Additional Requirements

  • The class declaration (Puzzle) in puzzle.cpp may not be modified in any way. No additional libraries may be used.
  • You are not allowed to use STL template containers in the Puzzle class.
  • You are allowed to use STL template containers in your test functions.
  • The Puzzle class functions must be written in puzzle.cpp; in particular, they must not be written “in-line.”
  • Private helper functions may be added, but must be declared in the private section of the Puzzle class. There is a comment indicating where private helper fuction declarations should be written.
  • The class Random is included in the file puzzle.h to facilitate the implementation of random numbers. You can use the RANDOM type random numbers in a specific range.
  • You should read through the coding standards for this course.

Testing

  • The sample driver.cpp file will not be accepted as a test file.
  • The name of the test file must be mytest.cpp.
  • The mytest.cpp file contains the Tester class, and the main function.
  • The test cases must be implemented in the Tester class, and must be called in the main function.
  • Every test function returns true or false to indicate the pass or fail.
  • A dump() function is provided for debugging purposes, visual inspections will not be accepted as test cases.

You must write and submit a test program along with the implementation of your project. To test your project class, you implement your test functions in the Tester class. The Tester class resides in your test file. You name your test file mytest.cpp. It is strongly recommended that you read the testing guidelines before writing test cases. A sample test program including Tester class, and sample test functions are provided in driver.cpp. You add your Tester class, test functions and test cases to mytest.cpp. You must write a separate function for every test case.

Any program should be adequately tested. Adequate testing includes testing the functionaly for normal cases, edge cases and error cases. The following list presents some examples for this project:

  • Trying to create a Puzzle object with -5 rows and 5 columns is an error case.
  • Trying to create a Puzzle object with 10 rows and 10 columns is an edge case.
  • Trying to create a Puzzle object with 12 rows and 14 columns is a normal case.

The following presents a non-exhaustive list of tests for this project. Please note, you need to test your work adequately.

  • Test whether the constructor works correctly for an error case, e.g. it creates an empty object if the user tries to create an object with -5 rows and -10 columns.
  • Test whether the constructor works correctly for an normal case, e.g. it creates memory and initilizes all member variables to the proper values, if the user tries to create an object with 12 rows and 12 columns.
  • Test whether reCreate(...) works correctly for an error case, e.g. it does not modify the object if the user tries to create an object with 8 rows and 8 columns.
  • Test whether reCreate(...) works correctly for an normal case, e.g. it creates memory and initilizes all member variables to the proper values, if the user tries to create an object with 12 rows and 14 columns.
  • Test whether appendRight(...) is working correctly for a normal case, i.e. appending two normal objects.
  • Test whether appendRight(...) is working correctly for an error case, i.e. two objects have different number of rows.
  • Test whether appendRight(...) is working correctly for appending a normal object to an empty object.
  • Test whether appendRight(...) is working correctly for appending an empty object to a normal object.
  • Test whether appendRight(...) is working correctly for appending an object to itself.
  • Test the assignment operator for an edge case, e.g. trying to assign an empty object to an object with regular data.
  • Test the assignment operator for a normal case.

Sample Test Function

The following algorithm tests whether the copy constructor works correctly for a normal case:

  1. Create a normal object,
  2. Create a copy of previous object using the copy constructor,
  3. Check whether m_puzzle of original object and copy object point to different memory locations,
  4. Check whether the corresponding member variables of both objects carry the same values,
  5. Check whether all corresponding row pointers are different.

The sample implementation for the above algorithm is provided in the driver.cpp file.

What to Submit

You must submit the following files to the proj0 submit directory:

  • puzzle.h
  • puzzle.cpp
  • mytest.cpp (Note: This file contains the declaration and implementation of your Tester class as well as all your test cases.)

If you followed the instructions in the Project Submission page to set up your directories, you can submit your code using the following command: 

   cp puzzle.h puzzle.cpp mytest.cpp ~/cs341proj/proj0/

Grading Rubric

The following presents a course rubric. It shows how a submitted project might lose points.

  • Conforming to coding standards make about 10% of the grade.
  • Your test program is worth 50%. If you submit the sample driver program as your test program or no test program is submitted there will be 50% deduction.
  • Correctness and completeness of your test cases (mytest.cpp) make about 15% of the grade.
  • We have written test cases to test your submission without knowing anything about your code. Therefore, it is extremely important that your submission conforms to the specified requirements. Passing tests make about 30% of the grade.
  • There is a 5% deduction for every modification that we need to perform to compile and run your work. For example, if we need to rename your file from myTest.cpp to mytest.cpp the deduction will be applied.

If the submitted project is in a state that receives the deduction for all above items, it will be graded for efforts. The grade will depend on the required efforts to complete such a work.