The 1999 APCS Quilt Question and Commentary

This question is reproduced without permission

I've created a rewording of the quilt problem to address the concerns raised here.

The Preamble

A patchwork quilt can be made by sewing together many blocks, all of the same size. Each individual block is made up of a number of small squares cut from fabric. A block can be represented as a two-dimensional array of non-blank characters, each of which stands for one small square of fabric. The entire quilt can also be represented as a two-dimensional array of completed blocks. The example below shows an array that represents a quilt made of 9 blocks (in 3 rows and 3 columns). Each block contains 20 small squares (of 4 rows by 5 columns). The quilt uses 2 different fabric squares, represented by the characters 'x' and '.'. We consider only quilts where the main block alternates with the same block flipped upside down (i.e., reflected about a horizontal line through the block's center), as in the example below.

Commentary Sewing? Squares cut from fabric? These have nothing to do with the problem. I appreciate that reading a problem statement and determining what's really asked for are useful skills, but not on a timed-test of computer science, please. The term "main block", which is essential in understanding what's going on, isn't defined properly. The sentence "the main block alternates with the same block flipped..." isn't really correct, the main block is a pattern, and this pattern is alternated with its flipped version. A quibble, maybe, but you could make the problem more understandable by being careful.

Here's a particularly egregious line: "(a non-blank character) which stands for one small square of fabric". The fact that a character "stands for" a piece of fabric has nothing to do with the problem, adds nothing to the description, and is information better left out.

Consider the problem of storing and displaying information about a quilt.

Quilt Description

The class Quilt, whose declaration is shown below, is used to keep track of the blocks for an entire quilt. Since the pattern is based on one block, we only store that block and the number of rows and columns of blocks. For the example shown above, we would store the upper left 4 x 5 block, 3 for the number of rows of blocks in the quilt and 3 for the number of columns of blocks in the quilt.

Critique A Quilt object does not "keep track" of the blocks of an entire quilt. It represents a quilt by storing one block and the dimensions of the quilt. That's really a very different concept than "keeping track" although obviously related. "We would store the upper-left 4 x 5 block" doesn't mean anything---you'd store the main block, which happens to be the block shown in the upper-left. The term "main block" should be used in this desription.

class Quilt { public: Quilt(istream & inFile, int rowsOfBlocks, int colsOfBlocks); // constructor, given number of blocks in each row and column apmatrix<char> QuiltToMat(); // returns a matrix with the entire quilt stored in it private: apmatrix<char> myBlock; // stores pattern for one block int myRowsOfBlocks; // number of rows of blocks in the quilt int myColsOfBlocks; // number of columns of blocks in the quilt void PlaceBlock(int startRow, int startCol, apmatrix<char> & qmat); void PlaceFlipped(int startRow, int startCol, apmatrix<char> & qmat); };

Part (A)

Description of Constructor

Wite the code for the constructor that initializes a quilt, as started below. The constuctor reads the block pattern for the main block from a file represented by the parameter inFile. You may assume the file is open and that the file contains the number of rows followed by the number of columns for the block, followed by the characters representing the pattern. For example, the file pattern, which contains the pattern for the first block in the quilt shown above, would look like this.

   4 5
   x...x
   .x.x.
   ..x..
   ..x..

The constructor also sets the number of rows and columns of blocks which make up the entire quilt in the initializer list.

Critique We still don't have a description of "main block", although it becomes clear after reading the postcondition if it wasn't clear before. I don't think there's any ambiguity about what the main block is, but there's no reason not to be precise about its definition from the beginning. This wording also confuses "file" and "stream". If you're going to use an istream parameter, the name shouldn't have anything to do with files, it should be input rather than inFile. Otherwise, make the parameter of type ifstream. Why is the file name pattern mentioned, it's never used again, doesn't contribute anything in the current wording, and makes a reader wonder if she's missed something earlier. The term "first block" is used where it should be "main block".

Finally, the last sentence should be something like "the constructor sets a quilt's rows and columns in the initializer list". The separation of "initializer list" and "number of rows and columns" by "which make up the entire quilt" makes the sentence more difficult to parse than it needs to be.

Complete the constructor below. Assume that the constructor is called only with parameters that satisfy its precondition.

Quilt::Quilt(istream & inFile, int rowsOfBlocks, int colsOfBlocks) : myBlock(0,0), myRowsOfBlocks(rowsOfBlocks), myColsOfBlocks(colsOfBlocks) // pre: inFile is open, rowsOfBlocks > 0, colsOfBlocks > 0 // post: myRowsOfBlocks and myColsOfBlocks are initialized to // the number of rows and columns of blocks that make up // the quilt; myBlock has been resized and initialized to the // block pattern from the stream inFile

Part (B)

Description of PlaceFlipped

Write the private member function PlaceFlipped, as started below. PlaceFlipped is intended to place a flipped (upside-down) version of the block into the matrix qmat with the flipped block's upper-left corner located at the startRow, startCol position in qmat.

For example, if quilt Q contains the block shown in part(A) and if M is a matrix large enough to hold the characters in the whole quilt, then the call

Q.PlaceFlipped(4,10,M); would place the flipped version of Q's quilt block into matrix M as the third block in the second row of quilt blocks. This is the block whose upper-left corner is at position M[4][10]. In the diagram below, the upper-left corner of the flipped block being placed into M is circled.

Critique Why is PlaceFlipped intended to do anything? Doesn't it do something? Verbosity strikes with "upper-left corner located at the startRow, startCol position in qmat". Why not "starts the pattern at qmat[startRow][startCol]". The description uses the phrase "the block" where "main block" should be used.

You may adapt the code of the private member function PlaceBlock, given below, which places the block (not inverted) into the matrix qmat with the block's upper-left corner located at the startRow, startCol position.

void Quilt::PlaceBlock(int startRow, int startCol, apmatrix<char> & qmat) // pre: startRow >= 0; startCol >= 0; // startRow + myBlock.numrows() <= qmat.numrows(); // startCol + myBlock.numcols() <= qmat.numcols(); // post: myBlock has been copied into the matrix // qmat with its upper-left corner at the position // startRow, startCol { int r,c; for(r=0; r < myBlock.numrows(); r++) { for(c=0; c < myBlock.numcols(); c++) { qmat[startRow + r][startCol + c] = myBlock[r][c]; } } } Complete the member function PlaceFlipped below. Assume that PlaceFlipped is called only with parameters that satisfy its precondition. void Quilt::PlaceFlipped(int startRow, int startCol, apmatrix<char> & qmat) // pre: startRow >= 0; startCol >= 0; // startRow + myBlock.numrows() <= qmat.numrows(); // startCol + myBlock.numcols() <= qmat.numcols(); // post: a flipped version of myBlock has been copied into the // matrix qmat with its upper-left corner at the position // startRow, startCol { int r,c; for(r=0; r < myBlock.numrows(); r++) { for(c=0; c < myBlock.numcols(); c++) { } } }

Part (C)

Description of QuiltToMat

Write the member function QuiltToMat, as started below. QuiltToMat returns a matrix representing the whole quilt in such a way that the main block alternates with the flipped version of the main block, as shown in the original example. If Q represents the example quilt, then the call Q.QuiltToMat() would return a matrix of characters with the given block placed starting with the upper-left corner at position 0,0; the flipped block placed with its upper-left corner at position 0,5; the given block placed with its upper-left corner at position 0,10; the flipped block placed with its upper-left corner at position 4,0, and so on.

Critique Here the phrase "given block" appears for the first time. The term "main block" should be used, there's no block given anywhere. In general, the description is lengthier than it needs to be.

In writing QuiltToMat, you may call functions PlaceBlock, and PlaceFlipped specified in part (b). Assume that PlaceBlock and PlaceFlipped work as specified, regardless of what you wrote in part (b).

Complete the member function QuiltToMat below.

apmatrix<char> Quilt::QuiltToMat()

Owen L. Astrachan

Last modified: Thu Jun 3 11:53:56 EDT 1999