Pattern debugging lab

Why this matters

Shape programs often look almost right. A diamond has the correct points but one extra row, or a pyramid leans to one side. Finding the one line that causes the problem is a skill you will use on code you did not write. Shapes are a good place to learn it, because you can see the mistake with your own eyes.

The most common cause is an off-by-one error. This is a mistake where a counter, a loop limit or a count is one too high or one too low. A loop runs one time too many, or a row gets one star too many. Nearly every bug in this lesson is an off-by-one error.

Words used in this lesson

• Off-by-one error. A bug where a value is one more or one less than it should be.
• Boundary. The first or last value a loop uses. Most off-by-one errors happen at a boundary.
• Expected output. The exact text the program should print. You write it before you run the program.
• Loop limit. The test that decides whether a loop runs again. i < n stops when i reaches n. i <= n runs once more, when i equals n.
• Diff. A tool that compares two text files line by line and reports the lines that differ. On Linux and macOS, the command is diff.
• Standard library. The toolbox that comes with C++. This lesson uses std::string to build rows of stars and spaces, and std::cout to print them.

Labs 1 and 2 count rows from 1, because a picture is easier to read that way. Lab 3 counts from 0, as C++ does. Check where each loop starts before you change anything.

The method

Use the same five steps for every debugging problem in this lesson.

1. Write the expected output first. Write the text on paper before you read the broken code. For a diamond with n = 3, the expected output has 5 rows with 1, 3, 5, 3 and 1 stars. The expected output is your judge. If you start from the broken code, you may decide that its output is correct.
2. Count the rows. A diamond for n has 2 * n - 1 rows. A pyramid for n has n rows. A wrong row count is the fastest clue to a loop limit error.
3. Find the first wrong line. Compare the program output with the expected output, from top to bottom. Stop at the first row that differs. Later rows may be wrong for the same reason, so do not start there.
4. Read the loop that prints that row. Check the start value, the limit and the formula that gives the count. Ask two questions. Does the loop start where the first row starts? Does it stop where the last row stops?
5. Change one thing and compare again. A change that fixes two unrelated things at once hides the cause. Run the program after each change and compare it with the expected output.

For a long shape, a diff saves time. Save the expected output and the program output as text files, then run diff on them. The diff shows exactly which lines differ.

Lab 1: the broken diamond

A diamond for n = 3 has 5 rows. The top half grows 1, 3, 5 stars. The bottom half shrinks back to 3 and then 1 star. The middle row has the widest shape, 5 stars, and it should appear once.

Here is the expected output for n = 3:

  *
 ***
*****
 ***
  *

Here is a program that tries to print it. The bug is in one line.

#include <iostream>
#include <string>
 
int main() {
    const int n = 3;
    for (int i = 1; i <= n; ++i) {
        std::cout << std::string(n - i, ' ') << std::string(2 * i - 1, '*') << '\n';
    }
    for (int i = n; i >= 1; --i) {
        std::cout << std::string(n - i, ' ') << std::string(2 * i - 1, '*') << '\n';
    }
}

Compiled with g++ -std=c++20 -Wall, the program prints:

  *
 ***
*****
*****
 ***
  *

Follow the method. Step 2: the program printed 6 rows, and the diamond needs 2 * 3 - 1, which is 5. The row count is wrong, and that is the first clue.

Step 3: the first three rows match. The fourth row differs. It is a second copy of the widest row.

Step 4: the first loop runs i from 1 to 3. It prints the rows with 1, 3 and 5 stars, including the middle row. That loop is correct. The second loop starts at i = n, which is 3, so it prints the 5-star row again. The bottom half should start one row higher, at n - 1, which is 2. The fixed second loop is:

for (int i = n - 1; i >= 1; --i) {
    std::cout << std::string(n - i, ' ') << std::string(2 * i - 1, '*') << '\n';
}

Step 5: change that one line and run the program again. The output now matches the expected output.

To check with a diff, save the expected output to a file and the program output to another file. Then compare them. For the broken program, diff reports:

3a4
> *****

The line 3a4 means: after line 3 of the first file, add line 4 of the second file. The line starting with > is the extra line in the second file. The diff tells you where the extra row is. It does not tell you why the row is there. That reasoning is your job.

Lab 2: the unbalanced pyramid

A pyramid for n = 4 has 4 rows. Row 1 has one star, row 2 has three, row 3 has five, and row 4 has seven. Every row has an odd number of stars, so each row has a single star in the middle. The leading spaces are n - i, so the top star sits at column 3, counting columns from 0.

Here is the expected output:

   *
  ***
 *****
*******

Here is a broken version. The bug is in one number.

#include <iostream>
#include <string>
 
int main() {
    const int n = 4;
    for (int i = 1; i <= n; ++i) {
        std::cout << std::string(n - i, ' ') << std::string(2 * i, '*') << '\n';
    }
}

Its output is:

   **
  ****
 ******
********

Step 2: the row count is correct, 4 rows. Step 3: the first row differs. The expected first row has one star, and this one has two.

Step 4: the star count formula is 2 * i. For row 1 that gives 2. The correct formula is 2 * i - 1, which gives 1. This is an off-by-one error in the count. Every row prints one star too many, and every count is even. No row has a single star in the middle.

The effect on the shape is easy to measure. In the broken output, the top row has stars at columns 3 and 4. The middle of those two stars is at column 3.5. In the expected output, the top star is at column 3. The bottom row of the broken output runs from column 0 to column 7, so its middle is also 3.5, while the expected bottom row runs from column 0 to column 6 with its middle at 3. Every row is shifted half a column to the right.

Step 5: change 2 * i to 2 * i - 1. The output becomes the expected output above.

Lab 3: one loop, one extra row

Labs 1 and 2 used two loops. This lab builds the same diamond with one loop, and it shows a different kind of loop limit bug.

Each row i has a distance k from the middle row. For the first n rows, k is i. For the rest, k counts back down. The number of stars is 2 * k + 1, and the number of spaces is n - 1 - k. Here is the correct version for n = 3:

#include <iostream>
#include <string>
 
int main() {
    const int n = 3;
    for (int i = 0; i < 2 * n - 1; ++i) {
        int k = i < n ? i : 2 * n - 2 - i;
        std::cout << std::string(n - 1 - k, ' ') << std::string(2 * k + 1, '*') << '\n';
    }
}

Its output is:

  *
 ***
*****
 ***
  *

The line int k = i < n ? i : 2 * n - 2 - i; uses the conditional operator. It picks one of two values. The question mark separates the test from the first choice, and the colon separates the first choice from the second. In words: if i is less than n, use i. Otherwise use 2 * n - 2 - i.

Now change the loop limit from i < 2 * n - 1 to i <= 2 * n - 1:

for (int i = 0; i <= 2 * n - 1; ++i) {

The loop now runs one extra time, with i = 5. Compiled and run, the program stops with an error:

terminate called after throwing an instance of 'std::length_error'
  what():  basic_string::_M_create

The exit code was 134, which means the program stopped with an abort. When the output goes to a file or a pipe, no rows are printed. The output waits in a buffer, which is a small holding area in memory, and an abort does not flush that buffer. In a terminal, the five rows appear before the error. The exact message text can change between compilers.

The cause is at i = 5. The formula gives k = 2 * 3 - 2 - 5, which is -1. The star count 2 * k + 1 is then -1, and std::string cannot be built with a negative count. The space count n - 1 - k is 3, which is fine. Only the star count is negative.

The fix is to change <= back to <. A loop that should run m times from 0 needs the limit i < m.

Notice that this bug crashed the program. The bug in Lab 1 printed a plausible shape with one extra row. Some off-by-one errors make a wrong picture, and others make the program stop. Both are found the same way: compare the output with the expected output, then read the loop.

Common mistakes

Mistake 1: the top loop stops one row early

This program tries to print the top of a pyramid for n = 4:

for (int i = 1; i < n; ++i) {
    std::cout << std::string(n - i, ' ') << std::string(2 * i - 1, '*') << '\n';
}

Its output is:

   *
  ***
 *****

The widest row, which has 7 stars, is missing. The loop stops at i < n, so i never reaches n. The fix is i <= n. The row count is the check: a pyramid for n = 4 has 4 rows, and this output has 3.

Mistake 2: a space count that is one too small

The spaces formula is a common place for an off-by-one error. This version adds one extra space to every row:

for (int i = 1; i <= n; ++i) {
    std::cout << std::string(n - i + 1, ' ') << std::string(2 * i - 1, '*') << '\n';
}

For n = 3, its output is:

   *
  ***
 *****

The expected output for n = 3 starts with two spaces, *. Every row here has one extra space, so the whole shape sits one column to the right. The stars are correct, so counting stars alone will not find this bug. Compare the position of the first star in the first row, which is column 2 in the expected output and column 3 here.

Mistake 3: a negative count

If a loop runs past its last row, a formula such as std::string(n - i, ' ') can get a negative count. std::string cannot build a negative count, so the program throws the same std::length_error that Lab 3 showed. A negative count is a sign that a loop limit is wrong. Fix the loop limit, not the formula.

Practice

Each exercise is followed by its answer.

1. The bottom loop of the Lab 1 program starts at n. For n = 4, how many rows does the program print in total? The expected total is 7.

Show the answer

The top loop prints 4 rows, for i from 1 to 4. The bottom loop starts at 4 and prints 4 rows, for i from 4 down to 1. The total is 8. The expected count is 2 * 4 - 1, which is 7.

2. A pyramid for n = 4 uses the top loop for (int i = 1; i < n; ++i). Which row is missing, and what should it contain?

Show the answer

The widest row is missing. It should contain 7 stars and no leading spaces, which is *******. The loop must use i <= n.

3. Lab 3 crashes when i = 5. Show the arithmetic that gives a negative star count.

Show the answer

The distance is k = 2 * 3 - 2 - 5, which is -1. The star count is 2 * k + 1, which is 2 * -1 + 1, which is -1.

4. Predict the output of the fixed Lab 1 program with n = 2. Write it before you run the program, then check by running it.

Show the answer

The top loop prints * and ***. The bottom loop starts at n - 1, which is 1, and prints *. Compiled and run, the output is:

 *
***
 *

5. A student writes the pyramid spaces as n - i + 1 for n = 3. Predict the first row. Then state the expected first row.

Show the answer

With i = 1, the spaces are 3 - 1 + 1, which is 3. The first row is *. The expected first row has 2 spaces, so it is *. The student's version shifts every row one column to the right.

Summary

• Write the expected output first, then count the rows. A wrong row count points to a loop limit.
• Find the first row that differs, then read only the loop that prints that row.
• A diamond for n has 2 * n - 1 rows. A pyramid for n has n rows, and row i of a pyramid has 2 * i - 1 stars.
• Use i < n for a loop that should run n times from 0, and i <= n for a loop that should run from 1 through n.
• Save the expected and actual output as text files and compare them with diff when a shape is long.