2
PURE PUZZLES

In this chapter, we’ll start dealing with actual code. While intermediate programming knowledge will be needed for later chapters, the programming skills required in this chapter are as simple as can be. That doesn’t mean that all of these puzzles will be easy, only that you should be able to focus on the problem solving and not the programming syntax. This is problem solving at its purest. Once you figure out what you want to do, translating your thoughts into C++ code will be straightforward. Remember that reading this book, in itself, provides limited benefit. You should work through any problem that appears nontrivial to you as we discuss it, trying to solve it yourself before reading about my approach. At the end of the chapter, try some of the exercises, many of which will be extensions of the problems we discuss.

Review of C++ Used in This Chapter

This chapter uses the basic C++ with which you should already be familiar, including the control statements if, for, while and do-while, and switch. You may not yet be comfortable writing code to solve original problems with these statements—that’s what this book is about, after all. You should, however, understand the syntax of how these statements are written or have a good C++ reference handy.

You should also know how to write and call functions. To keep things simple, we’ll use the standard streams cin and cout for input and output. To use these streams, include the necessary header file, iostream, in your code, and add using statements for the two standard stream objects:

#include <iostream>
using std::cin;
using std::cout;

For brevity, these statements won’t be shown in the code listings. Their inclusion is assumed in any program that uses them.

Output Patterns

In this chapter, we will work through three main problems. Because we’ll be making extensive use of the problem division and reduction techniques, each of these main problems will spawn several subproblems. In this first section, let’s try a series of programs that produce patterned output in a regular shape. Programs like these develop loop-writing skills.

Here’s another great example of the importance of constraints. If we ignore the requirement that we can use only two output statements, one that produces a single hash symbol and one that produces an end-of-line, we can write a Kobayashi Maru and solve this problem trivially. With that constraint in place, however, we’ll have to use loops to solve this problem.

You may already see the solution in your head, but let’s assume that you don’t. A good first weapon is reduction. How can we reduce this problem to a point where it’s easy to solve? What if the pattern was a whole square instead of half of a square?

This may be enough to get us going, but suppose we didn’t know how to tackle this either. We could reduce the problem further, making a single line of hash symbols instead of the square.

Now we have a trivial problem that can be solved with a for loop:

for (int hashNum = 1; hashNum <= 5; hashNum++) {
   cout << "#";
}
cout << " ";

From here, return to the previous reduction, the full square shape. The full square is simply five repetitions of the line of five hash symbols. We know how to make repeating code; we just write a loop. So we can turn our single loop into a double loop:

for (int row = 1; row <= 5; row++) {
   for (int hashNum = 1; hashNum <= 5; hashNum++) {
      cout << "#";
   }
   cout << " ";
}

We’ve placed all of the code from the previous listing in a new loop so that it repeats five times, producing five rows, each row a line of five hash symbols. We’re getting closer to the ultimate solution. How do we modify the code so that it produces the half-square pattern? If we look at the last listing and compare it to our desired half-square output, we can see that the problem is in the conditional expression hashNum <= 5. This conditional produces the same line of five hash symbols on each row. What we require is a mechanism to adjust the number of symbols produced on each row so that the first row gets five symbols, the second row gets four, and so on.

To see how to do this, let’s make another reduced program experiment. Again, it’s always easiest to work on the troublesome part of a problem in isolation. For a moment, let’s forget about hash symbols and just talk about numbers.

We must find an expression ➊ that is 5 when row is 1, 4 when row is 2, and so on. If we want an expression that decreases as row increases, our first thought might be to stick a minus sign in front of the values of row by multiplying row by –1. This produces numbers that go down, but not the desired numbers. We may be closer than we think, though. What’s the difference between the desired value and the value given by multiplying row by –1? Table 2-1 summarizes this analysis.

Table 2-1: Computation of Desired Value from Row Variable

Row	Desired Value	Row * –1	Difference from Desired Value
1	5	–1	6
2	4	–2	6
3	3	–3	6
4	2	–4	6
5	1	–5	6

The difference is a fixed value, 6. This means the expression we need is row * -1 + 6. Using a little algebra, we can simplify this to 6 - row. Let’s try it out:

for (int row = 1; row <= 5; row++) {
   cout << 6 - row << " ";
}

Great—it works! If this hadn’t worked, our mistake probably would have been minor, because of the careful steps we have taken. Again, it’s very easy to experiment with a block of code that is this small and simple. Now let’s take this expression, and use it to limit the inner loop:

for (int row = 1; row <= 5; row++) {
   for (int hashNum = 1; hashNum <= 6 - row; hashNum++) {
      cout << "#";
   }
   cout << " ";
}

Using the reduction technique requires more steps to get from the description to the completed program, but each step is easier. Think of using a series of pulleys to lift a heavy object: You have to pull the rope farther to get the same amount of lift, but each pull is much easier on your muscles.

Let’s tackle another shape problem before moving on.

We’re not going to go through all the steps we used on the previous problem, because we don’t need to. This “Sideways Triangle” problem is analogous to the “Half of a Square” problem, so we can use what we have learned from the latter in the former. Remember the “start with what you know” maxim? Let’s start by listing skills and techniques from the “Half of a Square” problem that can be applied to this problem. We know how to:

• Display a row of symbols of a particular length using a loop

• Display a series of rows using nested loops

• Create a varying number of symbols in each row using an algebraic expression instead of a fixed value

• Discover the correct algebraic expression through experimentation and analysis

Figure 2-1 summarizes our current position. The first row shows the previous “Half of a Square” problem. We see the desired pattern of hash symbols (a), the line pattern (b), the square pattern (c), and the number sequence (d) that will transform the square pattern to the half-a-square pattern. The second row shows the current “Sideways Triangle” problem. We again see the desired pattern (e), the line (f), a rectangle pattern (g), and a number sequence (h).

At this point, we will have no problem producing (f) because it is almost the same as (b). And we should be able to produce (g) because it is just (c) with more rows and one fewer symbol per row. Finally, if someone were to give us the algebraic expression that would produce the number sequence (h), we would have no difficulty creating the desired pattern (e).

Thus, most of the mental work required to create a solution for the “Sideways Triangle” problem has already been done. Furthermore, we know exactly what mental work remains: figuring out an expression to produce the number sequence (h). So that’s where we should direct our attention. We could either take the finished code for the “Half of a Square” problem and experiment until we can produce the desired numbered sequence or take a guess and make a table like Table 2-1 to see whether that jogs our creativity.

Figure 2-1: Various components needed to solve the shape problems

Let’s try experimenting this time. In the “Half of a Square” problem, subtracting the row from a larger number worked well, so let’s see what numbers we get by running row in a loop from 1 to 7 and subtracting row from 8. The result is shown in Figure 2-2 (b). That’s not what we want. Where do we go from here? In the previous problem, we needed a number that went down instead of up, so we subtracted our loop variable from a greater number. In this problem, we need to go up first and then down. Would it make sense to subtract from a number in the middle? If we replace the 8 - row in the previous code with 4 - row, we get the result in Figure 2-2 (c). That’s not right either, but it looks like it could be a useful pattern if we don’t look at the minus signs on the last three numbers. What if we used the absolute value function to remove those minus signs? The expression abs(4 - row) produces the results in Figure 2-2 (d). We’re so close now—I can almost taste it! It’s just that we are going down first and then up when we need to go up first and then down. But how do we get from the number sequence we have to the number sequence we need?

Let’s try looking at the numbers in Figure 2-2 (d) in a different way. What if we count the empty spaces instead of the hash marks, as shown in Figure 2-2 (e)? Column (d) is the right pattern of values if we count the empty spaces. To get the right number of hash marks, think of each row as having four boxes, and then subtract the number of empty spaces. If each row has four boxes of which abs(4 - row) are empty spaces, then the number of boxes with hash marks will be given by 4 - abs(4 - row). That works. Plug it in, and try it out.

Figure 2-2: Various components needed to solve the “Sideways Triangle” problem

We have avoided most of the work for this problem through analogy and have solved the rest through experimentation. This one-two punch is a great approach when a new problem is very similar to another you can already solve.

Input Processing

The previous programs only produced output. Let’s change things up and try programs that are all about processing the input. Each of these programs shares one constraint: The input will be read character by character, and the program must process each character before reading the next one. In other words, the programs will not store the characters in a data structure for later processing but process as they go.

In this first problem, we’ll perform identification number validation. In the modern world, almost everything has an identification number, such as an ISBN or a customer number. Sometimes these numbers have to be entered by hand, which introduces the potential for error. If a mistakenly entered number doesn’t match any valid identification number, the system can easily reject it. But what if the number is wrong, yet valid? For example, what if a cashier, attempting to credit your account for a product return, enters another customer’s account number? The other customer would receive your credit. To avoid this situation, systems have been developed to detect mistakes in identification numbers. They work by running the identification number through a formula that generates one or more extra digits, which become part of an extended identification number. If any of the digits are changed, the original part of the number and the extra digits will no longer match, and the number can be rejected.

The process sounds a little complicated, but an example will make everything clearer. Our program will only validate an identification number, not create the check digit. Let’s walk through both ends of the process: computing a check digit and validating the result. This process is demonstrated in Figure 2-3. In part (a), we compute the check digit. The original identification number, 176248, is shown in the dashed-line box. Every other digit, starting from the rightmost digit of the original number (which, after the addition of the check digit, will be the second rightmost), is doubled. Then each digit is added together. Note that when doubling a digit results in a two-digit number, each of those digits is considered separately. For example, when 7 is doubled to produce 14, it’s not 14 that is added to the checksum, but 1 and 4 individually. In this case, the checksum is 27, so the check digit is 3 because that’s the digit value that would make the overall sum 30. Remember, the checksum of the final number should be divisible by 10; in other words, it should end in 0.

Figure 2-3: The Luhn checksum formula

In part (b), we validate the number 1762483, which now includes the check digit. This is the process we will be using for this problem. As before, we double every second digit, starting with the digit to the left of the check digit, and add the values of all digits, including the check digit, to determine the checksum. Because the checksum is divisible by 10, this number validates.

Breaking Down the Problem

The program that will solve this problem has several separate issues we will have to handle. One issue is the doubling of digits, which is tricky because doubled digits are determined from the right end of the identification number. Remember, we’re not going to read and store all of the digits and then process. We’re going to process as we go. The problem is that we’ll be getting the digits left to right, but we really need them right to left in order to know which digits to double. We would know which digits to double if we knew how many digits were in the identification number, but we don’t because the problem states that the identification number is of arbitrary length. Another issue is that doubled numbers 10 and greater must be treated according to their individual digits. Also, we have to determine when we’ve read the whole identification number. Finally, we have to figure out how to read the number digit by digit. In other words, the user is going to enter one long number, but we want to read it as though the digits were entered as separate numbers.

Because we always want to have a plan, we should make a list of these issues and tackle them one by one:

• Knowing which digits to double

• Treating doubled numbers 10 and greater according to their individual digits

• Knowing we’ve reached the end of the number

• Reading each digit separately

To solve problems, we’ll be working on individual pieces before writing a final solution. Thus, there is no need to work on these issues in any particular order. Start with the issue that looks the easiest or, if you want a challenge, the one that looks the most difficult. Or just start with the one that’s the most interesting.

Let’s begin by tackling the doubled digits that are 10 and greater. This is a situation where problem constraints make things easier rather than more difficult. Computing the sum of the digits of an arbitrary integer could be a good amount of work by itself. But what is the range of possible values here? If we start with individual digits 0–9 and double them, the maximum value is 18. Therefore, there are only two possibilities. If the doubled value is a single digit, then there’s nothing more to do. If the doubled value is 10 or greater, then it must be in the range 10–18, and therefore the first digit is always 1. Let’s do a quick code experiment to confirm this approach:

   int digit;
   cout << "Enter a single digit number, 0-9: ";
   cin >> digit;
➊ int doubledDigit = digit * 2;
   int sum;
➋ if (doubledDigit >= 10) sum = ➌1 + doubledDigit % 10;
   else sum = doubledDigit;
➍ cout << "Sum of digits in doubled number: " << sum << " ";

This is straightforward code: the program reads the digit, doubles it ➊, sums the digits of the doubled number ➋, and outputs the sum ➍. The heart of the experiment is the calculation of the sum for a doubled number that is greater than 10 ➌. As with the calculation of the number of hash marks needed for a particular row in our shapes problems, isolating this calculation to a short program of its own makes experimentation easy. Even if we don’t get the correct formula at first, we’re sure to find it quickly.

Before we scratch this issue off our list, let’s turn this code into a short function we can use to simplify future code listings:

int doubleDigitValue(int digit) {
   int doubledDigit = digit * 2;
   int sum;
   if (doubledDigit >= 10) sum = 1 + doubledDigit % 10;
   else sum = doubledDigit;
   return sum;
}

Now let’s work on reading the individual digits of the identification number. Again, we could tackle a different issue next if we wanted, but I think this issue is a good choice because it will allow us to type the identification number naturally when testing the other parts of the problem.

If we read the identification number as a numeric type (int, for example), we’d just get one long number and have a lot of work ahead of us. Plus, there’s a limit to how big an integer we can read, and the question says the identification number is of arbitrary length. Therefore, we’ll have to read character by character. This means that we need to make sure we know how to read a character representing a digit and turn it into an integer type we can work with mathematically. To see what would happen if we took the character value and used it in an integer expression directly, take a look at the following listing, which includes sample output.

   char digit;
   cout << "Enter a one-digit number: ";
➊ digit = cin.get();
   int sum = digit;
   cout << "Is the sum of digits " << sum << "? ";

➋ Enter a one-digit number: 7
   Is the sum of digits 55?

Note that we use the get method ➊ because the basic extraction operator (as in cin >> digit) skips whitespace. That’s not a problem here, but as you’ll see, it would cause trouble later. In the sample input and output ➋, you see the problem. All computer data is essentially numeric, so individual characters are represented by integer character codes. Different operating systems may use different character code systems, but in this text we’ll focus on the common ASCII system. In this system, the character 7 is stored as the character code value 55, so when we treat the value as an integer, 55 is what we get. We need a mechanism to turn the character 7 into the integer 7.

In the shape problems of the previous section, we had a variable with one range of values that we wanted to convert to another range of values. We made a table with columns for the original values and desired values and then checked the difference between the two. This is an analogous problem, and we can use the table idea again, as in Table 2-2.

Table 2-2: Character Codes and Desired Integer Values

Character	Character Code	Desired Integer	Difference
0	48	0	48
1	49	1	48
2	50	2	48
3	51	3	48
4	52	4	48
5	53	5	48
6	54	6	48
7	55	7	48
8	56	8	48
9	57	9	48

The difference between the character code and the desired integer is always 48, so all we have to do is subtract that value. You might have noticed that this is the character code value for the zero character, 0. This will always be true because character code systems always store the digit characters in order, starting from 0. We can therefore make a more general, and more readable, solution by subtracting the character 0 rather than using a predetermined value, like 48:

char digit;
cout << "Enter a one-digit number: ";
cin >> digit;
int sum = digit - '0';
cout << "Is the sum of digits " << sum << "? ";

Now we can move on to figuring out which digits to double. This part of the problem may take several steps to figure out, so let’s try a problem reduction. What if we initially limited ourselves to a fixed-length number? That would confirm our understanding of the general formula while making progress toward the ultimate goal. Let’s try limiting the length to six; this is long enough to be a good representation of the overall challenge.

As before, we can reduce even further to make getting started as easy as possible. What if we changed the formula so that none of the digits is doubled? Then the program only has to read the digits and sum them.

Because we know how to read an individual digit as a character, we can solve this fixed-length, simple checksum problem pretty easily. We just need to read six digits, sum them, and determine whether the sum is divisible by 10.

char digit;
int checksum = 0;
cout << "Enter a six-digit number: ";
for (int position = 1; position <= 6; position ++) {
   cin >> digit;
   checksum += digit - '0';
}
cout << "Checksum is " << checksum << ". ";
if (checksum % 10 == 0) {
   cout << "Checksum is divisible by 10. Valid. ";
} else {
   cout << "Checksum is not divisible by 10. Invalid. ";
}

From here, we need to add the logic for the actual Luhn validation formula, which means doubling every other digit starting from the second digit from the right. Since we are currently limiting ourselves to six-digit numbers, we need to double the digits in positions one, three, and five, counting from the left. In other words, we double the digit if the position is odd. We can identify odd and even positions using the modulo (%) operator because the definition of an even number is that it is evenly divisible by two. So if the result of the expression position % 2 is 1, position is odd and we should double. It’s important to remember that doubling here means both doubling the individual digit and also summing the digits of the doubled number if the doubling results in a number 10 or greater. This is where our previous function really helps. When we need to double a digit according to the Luhn formula, we just send it to our function and use the result. Putting this together, just change the code inside the for loop from the previous listing:

for (int position  = 1; position <= 6; position++) {
   cin >> digit;
   if (position % 2 == 0) checksum += digit - '0';
      else checksum += doubleDigitValue(digit - '0'),
}

We’ve accomplished a lot on this problem so far, but there are still a couple of steps to go before we can write the code for arbitrary-length identification numbers. To ultimately solve this problem, we need to divide and conquer. Suppose I asked you to modify the previous code for numbers with 10 or 16 digits. That would be trivial—you’d only have to change the 6 used as the upper bound of the loop to another value. But suppose I asked you to validate seven-digit numbers. That would require a small additional modification because if the number of digits is odd and we are doubling every digit starting from the second on the right, the first digit on the left is no longer doubled. In this case, you need to double the even positions: 2, 4, 6, and so on. Putting aside that issue for the moment, let’s figure out how to handle any even-length number.

The first issue we face is determining when we have reached the end of the number. If the user enters a multidigit number and presses ENTER and we’re reading the input character by character, what character is read after the last digit? This actually varies based on the operating system, but we’ll just write an experiment:

cout << "Enter a number: ";
char digit;
while (true) {
   digit = cin.get();
   cout << int(digit) << " ";
}

This loop runs forever, but it does the job. I typed in the number 1234 and pressed ENTER. The result was 49 50 51 52 10 (based on ASCII; this will vary based on the operating system). Thus, 10 is what I’m looking for. With that information in hand, we can replace the for loop in our previous code with a while loop:

   char digit;
   int checksum = 0;
➊ int position = 1;
   cout << "Enter a number with an even number of digits: ";
➋ digit = cin.get();
   while ➌(digit != 10) {
     ➍if (position % 2 == 0) checksum += digit - '0';
       else checksum += doubledDigitValue(digit - '0'),
     ➎digit = cin.get();
     ➏position++;
   }
   cout << "Checksum is " << checksum << ". ";
   if (checksum % 10 == 0) {
      cout << "Checksum is divisible by 10. Valid. ";
   } else {
      cout << "Checksum is not divisible by 10. Invalid. ";
   }

In this code, position is no longer the control variable in a for loop, so we must initialize ➊ and increment it separately ➏. The loop is now controlled by the conditional expression ➌, which checks for the character code value that signals the end-of-line. Because we need a value to check the first time we go through the loop, we read the first value before the loop begins ➋ and then read each subsequent value inside the loop ➎, after the processing code.

Again, this code will handle a number of any even length. To handle a number of any odd length, we’d need only to modify the processing code, reversing the logic of the if statement condition ➍ in order to double the numbers at the even positions, rather than the odd positions.

That, at least, exhausts every possibility. The length of the identification number must be odd or even. If we knew the length ahead of time, we would know whether to double the odd positions or the even positions in the number. We don’t have that information, however, until we have reached the end of the number. Is a solution impossible given these constraints? If we know how to solve the problem for an odd number of digits and for an even number of digits but don’t know how many digits are in the number until we’ve read it completely, how can we solve this problem?

You may already see the answer to this problem. If you don’t, it’s not because the answer is difficult but because it is hidden in the details. What we could use here is an analogy, but we haven’t seen an analogous situation so far. Instead, we’ll make our own analogy. Let’s make a problem that is explicitly about this very situation and see whether staring the problem in the face helps us find a solution. Clear your mind of preconceptions based on the work so far, and read the following problem.

This is a simple problem, one that doesn’t seem to have any complications at all. We just need one variable that counts the positive numbers and another variable that counts the negative numbers. When the user specifies the request at the end of the program, we just need to consult the proper variable for the response:

int number;
int positiveCount = 0;
int negativeCount = 0;
for (int i = 1; i <= 10; i++) {
   cin >> number;
   if (number > 0) positiveCount++;
   if (number < 0) negativeCount++;
}
char response;
cout << "Do you want the (p)ositive or (n)egative count? ";
cin >> response;
if (response == 'p')
   cout << "Positive count is " << positiveCount << " ";
if (response == 'n')
    out << "Negative count is " << negativeCount << " ";

This shows the method we need to use for the Luhn checksum problem: Keep track of the running checksum both ways, as if the identification number is an odd length and again as if it is an even length. When we get to the end of the number and discover the true length, we’ll have the correct checksum in one variable or the other.

Putting the Pieces Together

We’ve now checked off everything on our original “to-do” list. It’s time to put everything together and solve this problem. Because we’ve solved all of the subproblems separately, we know exactly what we need to do and can use our previous programs as reference to produce the final result quickly:

   char digit;
   int oddLengthChecksum = 0;
   int evenLengthChecksum = 0;
   int position = 1;
   cout << "Enter a number: ";
   digit = cin.get();
   while (digit != 10) {
      if (position % 2 == 0) {
         oddLengthChecksum += doubleDigitValue(digit - '0'),
         evenLengthChecksum += digit - '0';
      } else {
         oddLengthChecksum += digit - '0';
         evenLengthChecksum += doubleDigitValue(digit - '0'),
      }
      digit = cin.get();
      position++;
   }
   int checksum;
➊ if ((position - 1) % 2 == 0) checksum = evenLengthChecksum;
   else checksum = oddLengthChecksum;
   cout << "Checksum is " << checksum << ". ";
   if (checksum % 10 == 0) {
      cout << "Checksum is divisible by 10. Valid. ";
   } else {
      cout << "Checksum is not divisible by 10. Invalid. ";
   }

Note that when we check to see whether the length of the input number is odd or even ➊, we subtract 1 from position. We do this because the last character we read in the loop will be the terminating end-of-line, not the last digit of the number. We could also have written the test expression as (position % 2 == 1), but that’s more confusing to read. In other words, it’s better to say “if position - 1 is even, use the even checksum” than “if position is odd, use the even checksum” and have to remember why that makes sense.

This is the longest code listing we’ve looked at so far, but I don’t need to annotate everything in the code and describe how each part works because you’ve already seen each part in isolation. This is the power of having a plan. It’s important to note, though, that my plan is not necessarily your plan. The issues I saw in the original description of the problem and the steps I took to work through those issues are likely to differ from what you would’ve seen and done. Your background as a programmer and the problems you have successfully completed determine which parts of the problem are trivial or difficult and thus what steps you need to take to solve the problem. There may have been a point in the previous section where I took what looked like a needless detour to figure out something that was already obvious to you. Conversely, there may have been a point where I nimbly skipped over something that was tricky for you. Also, if you’d worked through this yourself, you might have come up with an equally successful program that looked quite different from mine. There is no one “right” solution for a problem, as any program that meets all constraints counts as a solution, and for any solution, there is no one “right” way of reaching it.

Seeing all the steps that we took to reach the solution, along with the relative brevity of the final code, you might be tempted to try to trim steps in your own problem-solving process. I would caution against this impulse. It’s always better to take more steps than to try to do too much at once, even if some steps seem trivial. Remember what the goals are in problem solving. The primary goal is, of course, to find a program that solves the stated problem and meets all constraints. The secondary goal is to find that program in the minimal amount of time. Minimizing the number of steps isn’t a goal, and no one has to know how many steps you took. Consider trying to reach the summit of a steep hill that has a shallow but long and winding path. Ignoring the path and climbing the hill directly from the base to the peak will certainly require fewer steps than following the path—but is it faster? The most likely outcome of a direct climb is that you give up and collapse.

Also remember the last of my general rules for problem solving: Avoid frustration. The more work you try to do in each step, the more you invite potential frustration. Even if you back off a difficult step and break it up into substeps, the damage will have been done because psychologically you’ll feel like you’re going backward instead of making progress. When I coach beginning programmers in a step-by-step approach, I sometimes have a student complain, “Hey, that step was too easy.” To which I reply, “What are you complaining about?” If you’ve taken a problem that initially looked tough and broken it down into pieces so small that every piece is trivial to accomplish, I say: Congratulations! That’s just what you should hope for.

Tracking State

The last problem we’ll work through for this chapter is also the most difficult. This problem has a lot of different pieces and a complicated description, which will illustrate the importance of breaking down a complex problem.

Table 2-3: Punctuation Decoding Mode

Number	Symbol
1	!
2	?
3	,
4	.
5	(space)
6	;
7	"
8	'

As with the Luhn validation formula, we’re going to walk through a concrete example to make sure we have all the steps straight. Figure 2-4 demonstrates a sample decoding. The original input stream is shown at the top. The processing steps proceed from the top down. Column (a) shows the current number in the input. Column (b) is the current mode, cycling from uppercase (U) to lowercase (L) to punctuation (P). Column (c) shows the divisor for the current mode. Column (d) is the remainder of dividing the current divisor in column (c) into the current input from column (a). The result is shown in column (e), either a character or, if the result in (d) is 0, a switch to the next mode in the cycle.

As with the previous problem, we can start by explicitly considering the skills we’ll need to craft a solution. We need to read a string of characters until we reach an end-of-line. The characters represent a series of integers, so we need to read digit characters and convert them to integers for further processing. Once we have the integers, we need to convert the integer into a single character for output. Finally, we need some way to track the decoding mode so we know whether the current integer should be decoded into a lowercase letter, uppercase letter, or punctuation. Let’s turn this into a formal list:

• Read character by character until we reach an end-of-line.

• Convert a series of characters representing a number to an integer.

• Convert an integer 1–26 into an uppercase letter.

• Convert an integer 1–26 into a lowercase letter.

• Convert an integer 1–8 into a punctuation symbol based on Table 2-3.

• Track a decoding mode.

The first item is something we already know how to do from the previous problem. Furthermore, although we only dealt with individual digits in the Luhn validation formula, I suspect some of what we did there will also be helpful on the second item of our list. The finished code for the Luhn algorithm is probably still fresh in your mind, but if you put the book down between that problem and this one, you’ll want to go back and review that code. In general, when the description of a current problem “rings bells,” you’ll want to dig out any similar code from your archives for study.

Figure 2-4: Sample processing for the “Decode a Message” problem

Let’s get down to business on the items that remain. You may have noticed that I’ve made each of the conversions a separate item. I suspect that converting a number into a lowercase letter is going to be very similar to converting a number into an uppercase letter, but perhaps converting to a punctuation symbol will require something different. In any case, there’s no real downside to chopping up the list too finely; it just means you’ll be able to cross things off the list more often.

Let’s start with those integer-to-character conversions. From the Luhn formula program, we know the code required to read a character digit 0–9 and convert it to an integer in the range 0–9. How can we extend this method to deal with multidigit numbers? Let’s consider the simplest possibility: two-digit numbers. This looks straightforward. In a two-digit number, the first digit is the tens digit, so we should multiply this individual digit by 10, and then add the value of the second digit. For example, if the number were 35, after reading the individual digits as characters 3 and 5, and converting these to the integers 3 and 5, we would obtain the overall integer we need by the expression 3 * 10 + 5. Let’s confirm this with code:

cout << "Enter a two-digit number: ";
char digitChar1 = cin.get();
char digitChar2 = cin.get();
int digit1 = digitChar1 - '0';
int digit2 = digitChar2 - '0';
int overallNumber = digit1 * 10 + digit2;
cout << "That number as an integer: " << overallNumber << " ";

That works—the program outputs same two-digit number that we put in. We encounter a problem, however, when we try to extend this method. This program uses two different variables to hold the two character inputs, and while that causes no problems here, we certainly don’t want to extend that as a general solution. If we did, we would need as many variables as we have digits. That would get messy, and it would be difficult to modify if the range of possible numbers in the input stream varied. We need a more general solution to this subproblem of converting characters to integers. The first step to finding that general solution is to reduce the previous code to just two variables—one char and one int:

   cout << "Enter a two-digit number: ";
➊ char digitChar = cin.get();
➋ int overallNumber = (digitChar - '0') * 10;
➌ digitChar = cin.get();
➍ overallNumber += (digitChar - '0'),
   cout << "That number as an integer: " << overallNumber << " ";

We accomplish this by doing all the calculations on the first digit before reading the second digit. After reading the first character digit ➊ in one step, we convert to an integer, multiply by 10, and store the result ➋. After reading the second digit ➌, we add its integer value to the running total ➍. This is equivalent to the previous code while using only two variables, one for the last character read and one for the overall value of the integer. The next step is to consider extending this method to three-digit numbers. Once we do that, we’re likely to see a pattern that will allow us to create a general solution for any number of digits.

When we try this, though, we encounter a problem. With the two-digit number, we multiplied the left digit by 10 because the left digit was in the tens position. The leftmost digit in a three-digit number would be in the hundreds position, so we would need to multiply that digit by 100. Then we could read in the middle digit, multiply it by 10, add it to the running total, and then read in the last digit and add it, as well. That should work, but it’s not heading us in the direction of a general solution. Do you see the problem? Consider the previous statement: The leftmost digit in a three-digit number would be in the hundreds position. For a general solution, we won’t know how many digits are in each number until we reach the next comma. The leftmost digit in a number with an unknown quantity of digits can’t be labeled in the hundreds position or any other position. So how do we know what multiplier to use for each digit before adding to the running total? Or do we need another approach entirely?

As always, when stuck, it’s a good idea to create a simplified problem to work on. The issue here is not knowing how many digits the number is going to have. The simplest problem that deals with this issue would be one that has just two possible digit counts.

This issue of not knowing the count of characters until the end but needing the count right from the beginning is analogous to the issue in the Luhn formula. In the Luhn formula, we didn’t know whether the identification number had an odd or even length. In that case, our solution was to calculate the results two different ways and choose the appropriate one at the end. Could we do something like that here? If the number is either three or four digits, there are only two possibilities. If the number has three digits, the leftmost digit is the hundreds digit. If the number has four digits, the leftmost digit is the thousands digit. We could compute as if we had a three-digit number and as if we had a four-digit number and then choose the right number at the end, but the problem description allows us to have only one numeric variable. Let’s relax that restriction to make some progress.

Now we can put the “compute it both ways” method to work. We’ll process the first three digits two different ways and then see whether there is a fourth digit:

   cout << "Enter a three-digit or four-digit number: ";
   char digitChar = cin.get();
➊ int threeDigitNumber = (digitChar - '0') * 100;
➋ int fourDigitNumber = (digitChar - '0') * 1000;
   digitChar = cin.get();
   threeDigitNumber += (digitChar - '0') * 10;
   fourDigitNumber += (digitChar - '0') * 100;
   digitChar = cin.get();
   threeDigitNumber += (digitChar - '0'),
   fourDigitNumber += (digitChar - '0') * 10;
   digitChar = cin.get();
   if ➌(digitChar == 10) {
       cout << "Number entered: " << threeDigitNumber << " ";
   } else {
      ➍fourDigitNumber += (digitChar - '0'),
        cout << "Number entered: " << fourDigitNumber << " ";
   }

After reading the leftmost digit, we multiply its integer value by 100, and store it in our three-digit variable ➊. We also multiply the integer value by 1,000, and store it in our four-digit variable ➋. This pattern continues for the next two digits. The second digit is treated both as a tens digit in a three-digit number and as a hundreds digit in a four-digit number. The third digit is treated as both a ones and a tens digit. After reading the fourth character, we check to see whether it’s an end-of-line by comparing it to the number 10 ➌ (as in the previous problem, this value may vary per operating system). If it is an end-of-line, the input was a three-digit number. If not, we still need to add the ones digit to the total ➍.

Now we need to figure out how to get rid of one of the integer variables. Suppose we removed the variable fourDigitNumber entirely. The value of threeDigitNumber would still be correctly assigned, but when we reached a point where we needed fourDigitNumber, we wouldn’t have it. Using the value in threeDigitNumber, is there some way to determine the value that would have been in fourDigitNumber? Suppose the original input was 1234. After reading the first three digits, the value in threeDigitNumber would be 123; the value that would have been in fourDigitNumber is 1230. In general, since the multipliers for fourDigitNumber are 10 times those of threeDigitNumber, the former would always be 10 times the latter. Thus, only one integer variable is needed because the other variable can just be multiplied by 10 if necessary:

cout << "Enter a three-digit or four-digit number: ";
char digitChar = cin.get();
int number = (digitChar - '0') * 100;
digitChar = cin.get();
number += (digitChar - '0') * 10;
digitChar = cin.get();
number += (digitChar - '0'),
digitChar = cin.get();
if (digitChar == 10) {
   cout << "Number entered: " << number << " ";
} else {
   number = number * 10 + (digitChar - '0'),
   cout << "Number entered: " << number << " ";
}

Now we have an exploitable pattern. Consider expanding this code to handle five-digit numbers. After computing the right value for the first four digits, we would repeat the same process we followed for reading the fourth character instead of displaying the result immediately: Read a fifth character, check to see whether it’s an end-of-line, display the previously computed number if it is—otherwise, multiply by 10, and add the digit value of the current character:

cout << "Enter a number with three, four, or five digits: ";
char digitChar = cin.get();
int number = (digitChar - '0') * 100;
digitChar = cin.get();
number += (digitChar - '0') * 10;
digitChar = cin.get();
number += (digitChar - '0'),
digitChar = cin.get();
if (digitChar == 10) {
   cout << "Number entered: " << number << " ";
} else {
   number = number * 10 + (digitChar - '0'),
   digitChar = cin.get();
   if (digitChar == 10) {
      cout << "Number entered: " << number << " ";
   } else {
      number = number * 10 + (digitChar - '0'),
      cout << "Number entered: " << number << " ";
   }
}

At this point, we could easily expand the code to handle six-digit numbers or numbers with fewer digits. The pattern is clear: If the next character is another digit, multiply the running total by 10 before adding the integer digit value of the character. With this understanding, we can write a loop to handle a number of any length:

   cout << "Enter a number with as many digits as you like: ";
➊ char digitChar = cin.get();
➋ int number = (digitChar - '0'),
➌ digitChar = cin.get();
   while ➍(digitChar != 10) {
      ➎number = number * 10 + (digitChar - '0'),
      ➏digitChar = cin.get();
   }
   ➐cout << "Number entered: " << number << " ";

Here, we read the first character ➊, and determine its digit value ➋. Then we read the second character ➌ and reach the loop, where we check to see whether the most recently read character is an end-of-line ➍. If not, we multiply the running total in the loop by 10, and add the current character’s digit value ➎ before reading the next character ➏. Once we reach the end-of-line, the running total variable number contains the integer value for us to output ➐.

That handles the conversion of one series of characters to its integer equivalent. In the final program, we’ll be reading a series of numbers, separated by commas. Each number will have to be separately read and processed. As always, it’s best to start by thinking about a simple situation that demonstrates the issue. Let’s consider the input 101,22[EOL], where [EOL] is explicitly marking the end-of-line for clarity. It would be enough to modify the test condition of the loop to check for either the end-of-line character or a comma. Then we would need to place all the code that processes one number inside a larger loop that continues until all the numbers have been read. So the inner loop should stop for [EOL] or a comma, but the outer loop should stop only for [EOL]:

➊ char digitChar;
   do {
       digitChar = cin.get();
       int number = (digitChar - '0'),
       digitChar = cin.get();
       while ((digitChar != 10) && (digitChar != ',')) {
           number = number * 10 + (digitChar - '0'),
           digitChar = cin.get();
       }
       cout << "Number entered: " << number << " ";
   } while ➋(digitChar != 10);

This is another great example of the importance of small steps. Although this is a short program, the wheels-within-wheels nature of the double loop would have made for tricky code if we had tried to write this from scratch. It’s straightforward, though, when we arrive at this code by taking a step from the previous program. The declaration of digitChar ➊ is moved to a separate line so that the declaration is in scope throughout the code. The rest of the code is the same as the previous listing, except that it’s placed inside a do-while loop that continues until we reach the end-of-line ➋.

With that part of the solution in place, we can focus on processing the individual numbers. The next item on our list is converting a number 1–26 to a letter A–Z. If you think about it, this is actually a reversal of the process we used to convert the individual digit characters to their integer equivalents. If we subtract the character code for 0 to translate from the 0–9 character code range to the 0–9 integer range, we should be able to add a character code to translate from 1–26 to A–Z. What if we added 'A'? Here’s an attempt along with a sample input and output:

cout << "Enter a number 1-26: ";
int number;
cin >> number;
char outputCharacter;
outputCharacter = ➊number + 'A';
cout << "Equivalent symbol: " << outputCharacter << " ";

Enter a number 1-26: 5
Equivalent letter: F

That’s not quite right. The fifth letter of the alphabet is E, not F. The problem occurs because we are adding a number in the range that starts from 1. When we were converting in the other direction, from a character digit to its integer equivalent, we were dealing with a range that started from 0. We can fix this problem by changing the computation ➊ from number + 'A' to number + 'A' - 1. Note that we could look up the character code value for the letter A (it’s 65 in ASCII) and simply use one less than that value (for example, number + 64 in ASCII). I prefer the first version, though, because it’s more readable. In other words, if you come back to look at this code later, you can more quickly remember what number + 'A' - 1 does than what number + 64 does because the appearance of 'A' in the former will remind you of converting to uppercase letters.

Having sorted that out, we can easily adapt this idea to convert to lowercase letters by changing the computation ➊ to number + 'a' - 1. The punctuation table conversion is not as concise because the punctuation symbols in the table do not appear in that order in ASCII or any other character code system. As such, we’re going to have to handle this through brute force:

   cout << "Enter a number 1-8: ";
   int number;
   cin >> number;
   char outputCharacter;
➊ switch (number) {
      case 1: outputCharacter = '!'; break;
      case 2: outputCharacter = '?'; break;
      case 3: outputCharacter = ','; break;
      case 4: outputCharacter = '.'; break;
      case 5: outputCharacter = ' '; break;
      case 6: outputCharacter = ';'; break;
      case 7: outputCharacter = '"'; break;
      case 8: outputCharacter = ➋'''; break;
   }
   cout << "Equivalent symbol: " << outputCharacter << " ";

Here, we’ve used a switch statement ➊ to output the correct punctuation character. Note that a backslash has been employed as an “escape” in order to display the single quote ➋.

We have one last subproblem to tackle before putting everything together: switching from mode to mode whenever the most recent value decodes to 0. Remember that the problem description requires us to modulo each integer value by 27 (if we are currently in the uppercase mode or lowercase mode) or 9 (if we are in punctuation mode). When the result is 0, we switch to the next mode. What we need is a variable to store the current mode and logic inside our “read and process the next value” loop to switch modes if necessary. The variable tracking the current mode could be a simple integer, but it’s more readable to use an enumeration. A good rule of thumb: If a variable is only tracking a state and there is no inherent meaning to any particular value, an enumeration is a good idea. In this case, we could have a variable int mode arbitrarily say that the value of 1 means uppercase, 2 means lowercase, and 3 means punctuation. There’s no inherent reason, however, why those values are chosen. When we come back to look at the code later, we’ll have to reacquaint ourselves with the system to make sense of a statement such as if (mode == 2). If we use an enumeration—as in the statement (mode == LOWERCASE)—there is nothing for us to remember because it’s all spelled out. Here’s the code that results from this idea, along with a sample interaction:

enum modeType {UPPERCASE, LOWERCASE, PUNCTUATION};
int number;
modeType mode = UPPERCASE;
cout << "Enter some numbers ending with -1: ";
do {
   cin >> number;
   cout << "Number read: " << number;
   switch (mode) {
      case UPPERCASE:
         number = number % 27;
         cout << ". Modulo 27: " << number << ". ";
         if (number == 0) {
            cout << "Switch to LOWERCASE";
            mode = LOWERCASE;
         }
         break;
      case LOWERCASE:
         number = number % 27;
         cout << ". Modulo 27: " << number << ". ";
         if (number == 0) {
            cout << "Switch to PUNCTUATION";
            mode = PUNCTUATION;
         }
         break;
      case PUNCTUATION:
         number = number % 9;
         cout << ". Modulo 9: " << number << ". ";
         if (number == 0) {
            cout << "Switch to UPPERCASE";
            mode = UPPERCASE;
         }
         break;
   }
   cout << " ";
} while (number != -1);

Enter some numbers ending with -1: 2 1 0 52 53 54 55 6 7 8 9 10 -1
Number read: 2. Modulo 27: 2.
Number read: 1. Modulo 27: 1.
Number read: 0. Modulo 27: 0. Switch to LOWERCASE
Number read: 52. Modulo 27: 25.
Number read: 53. Modulo 27: 26.
Number read: 54. Modulo 27: 0. Switch to PUNCTUATION
Number read: 55. Modulo 9: 1.
Number read: 6. Modulo 9: 6.
Number read: 7. Modulo 9: 7.
Number read: 8. Modulo 9: 8.
Number read: 9. Modulo 9: 0. Switch to UPPERCASE
Number read: 10. Modulo 27: 10.
Number read: -1. Modulo 27: -1.

We have crossed off everything on our list, so now it’s time to integrate these individual code listings to make a solution for the overall program. We could approach this integration in different ways. We might put just two pieces together and build up from there. For example, we could combine the code to read and convert the comma-separated numbers with the mode switching from the most recent listing. Then we could test that integration and add the code to convert each number to the appropriate letter or punctuation symbol. Or we could build up in the other direction, taking the number-to-character listing and turning it into a series of functions to be called from the main program. At this point, we’ve mostly moved beyond problem solving into software engineering, which is a different subject. We made a series of blocks—that was the hard part—and now we just have to assemble them, as shown in Figure 2-5.

Almost every line in this program was extracted from previous code in this section. The bulk of the code ➊ comes from the mode-switching program. The central processing loop ➋ comes from our code to read a series of comma-delimited numbers character by character. Finally, you’ll recognize the code that converts the integers into uppercase letters, lowercase letters, and punctuation ➍. The small amount of new code is marked by ➌. The continue statements skip us to the next iteration of the loop when the last input was a mode-switch command, skipping the cout << outputCharacter at the end of the loop.

Figure 2-5: The assembled solution to the “Decode a Message” problem

While this is a cut-and-paste job, this is the good kind of cut-and-paste job, where you reuse the code you just wrote and therefore completely understand it. As before, think about how easy each step was in this process, versus trying to write the final listing from scratch. Undoubtedly, a good programmer could produce the final listing without going through the intermediate steps, but there would be false steps, times when the code looks ugly, and lines of code commented out and then put back again. By taking the smaller steps, all the dirty work gets done early, and the code never gets too ugly because the code we’re currently working with never gets long or complicated.

Conclusion

In this chapter, we looked at three different problems. In one sense, we had to take three different paths to solve them. In another sense, we took the same route each time because we used the same basic technique of breaking up the problem into components; writing code to solve those components individually; and then using the knowledge gained from writing the programs, or even directly using lines of code from the programs, to solve the original problem. In the chapters that follow, we won’t use this method explicitly for each problem, but the fundamental idea is always there: to chop up the problem into manageable pieces.

Depending on your background, these problems may have initially appeared to lie anywhere on the difficulty spectrum from fiendish to trivial. Regardless of how difficult a problem initially seems, I would recommend using this technique on each new problem you face. You don’t want to wait until you reach a frustratingly difficult problem before trying out a new technique. Remember that one of the goals of this text is for you to develop confidence in your ability to solve problems. Practice using the techniques on “easy” problems and you’ll have lots of momentum for when you hit the hard ones.

Exercises

As before, I urge you to try as many exercises as you can stand. Now that we are fully into the actual programming, working through exercises is essential for you to develop your problem-solving skills.

2-1. Using only single-character output statements that output a hash mark, a space, or an end-of-line, write a program that produces the following shape:

########
 ######
  ####
   ##

2-2. Or how about:

   ##
  ####
 ######
########
########
 ######
  ####
   ##

2-3. Here’s an especially tricky one:

#            #
 ##        ##
  ###    ###
   ########
   ########
  ###    ###
 ##        ##
#            #

2-4. Design your own: Think up your own symmetrical pattern of hash marks, and see whether you can write a program to produce it that follows the shapes rule.

2-5. If you like the Luhn formula problem, try writing a program for a different check-digit system, like the 13-digit ISBN system. The program could take an identification number and verify it or take a number without its check digit and generate the check digit.

2-6. If you’ve learned about binary numbers and how to convert from decimal to binary and the reverse, try writing programs to do those conversions with unlimited length numbers (but you can assume the numbers are small enough to be stored in a standard C++ int).

2-7. Have you learned about hexadecimal? Try writing a program that lets the user specify an input in binary, decimal, or hexadecimal, and output in any of the three.

2-8. Want an extra challenge? Generalize the code for the previous exercise to make a program that converts from any number base-16 or less to any other number base. So, for example, the program could convert from base-9 to base-4.

2-9. Write a program that reads a line of text, counting the number of words, identifying the length of the longest word, the greatest number of vowels in a word, and/or any other statistics you can think of.