Triple Hunting

Detecting Triples (C++)

According to the problem statement, a triple is any multiple of 3. From past experience, we expect to detect triples using either the division or modulo operator.

Upon further consideration, we notice that a number is a multiple of 3 exactly when it leaves a remainder of 0 when divided by 3. Hence the following psuedocode:

• C++

if (the_number % 3 == 0) {
    // the_number is a triple
} else {
    // the_number is not a triple
}

...correctly detects whether a given number is a triple.

Counting and collecting the triples

We set ourselves an intermediate goal of collecting all the triple locations into an array.

(Why? It would be simple enough to print out all the triple locations as we read through the input. However, the problem asks for us to begin by printing out the number of triples. We won't know what this is until we've gone through all the input. So we need somewhere to save our results in the meantime. In general, it's a useful technique to put intermediate results somewhere so that we can do further work with them later.)

Let's assume we've already read all the numbers into an array:

• C++

for (int i = 0; i < nNumbers; i++) {
    fscanf(inputFile,"%d",&input_array[i]);
}
// TODO: count and collect the triples
// TODO: write the output

We want to declare a new array triples[] that is going to hold all the triples.

• C++

int triples[MAX_N];

We don't know how many triples there will be, so we make a conservative guess and create enough space to store n different triple locations. We may not end up needing all that space, but it is better to set aside more space than we need than to run out of space. (Declaring an array that is too small and trying to store values past its end will likely result in a crash, or worse!)

Now, our code to count and collect the triples will look something like this:

• C++

for (int i = 0; i < nNumbers; i++) {
    if (input_array[i] % 3 == 0) {
        // TODO: the number is a triple... now what?
    }
}

Here comes the tricky part. How do we fill in the triples array correctly?

One way of thinking about this is to pick a specific case, or a specific point during the loop, and ask ourselves, what should our program be doing right now?. Let's pretend we're partway into the program and we've already found six triples, at the 2nd, 4th, 5th, 9th, 12th, and 13th locations in the array respectively.

The "???"s mark the remaining approximately 49,994 elements of the array which we made space for but aren't using right now. Depending on various factors about how the program is compiled and run, these "???"s could be anything: perhaps '0's, perhaps random gibberish, perhaps [17, 18, 19, ...].

Because we need our program to be able to tell the difference between misleading gibberish and actual triple locations, it's clear we'll need a variable to keep track of how many triples we've found and stored in the array so far. Let's call this variable nTriples. Right now:

Now, say our program discovers its next triple at the 18th position in the array. Then afterwards we want the following state:

What values have changed here? If we wanted to explicitly code this change in the array, we might write:

triples[6] = 18;
nTriples = 7;

But now let's think about that in the context of the loop we're trying to write. nTriples has clearly been incremented by 1. triples[6] has been set to the location in the loop we're up to (i in the example code above). And, interestingly, 6 is the initial value of nTriples! In fact, the value of nTriples tells us where the next "unused" location in the array is.

So we can write the following instead:

triples[nTriples] = i;
nTriples++;

Or, if you find it easier to read:

nTriples++;
triples[nTriples-1] = i;

We can put that into the empty spot we left in our loop. We need to make sure that nTriples is initialised to 0. Putting it all together:

• C++

nTriples = 0;
for (int i = 0; i < nNumbers; i++) {
    // nTriples = the number of triples we've found so far
    // there are nTriples values in the triples[] array
    if (input_array[i] % 3 == 0) {
        // the number is a triple
        triples[nTriples] = i;
        nTriples++;
    }
}

(There is potentially a bug in the above code. But it depends exactly what we're trying to do. We'll discuss that more later.)

You'll notice I added an extra comment at the beginning of the loop: "nTriples = the number of triples we've found so far / there are nTriples values in the triples[] array". This is a reminder of how the code is supposed to behave and serves a couple of purposes:

• While we're writing code, it reminds us what the variables mean. It's a convenient place to put a reminder.
• If we're looking for bugs later, having written down how the code is supposed to behave gives us a good starting point. A bug might be caused if code before the loop misbehaves (e.g. if nTriples was initialised to 2). A bug might be caused by later parts of the program expecting different behaviour or states than the ones the code actually produces.
• If we're changing or reusing the code later, having made a note of what the variables mean saves us time instead of having to figure it all out again. (Even after a day or two it's easy to forget little details about code you've written!)

It's often good practice to add these kinds of comments to your code, explaining what a variable means at a point in time. Don't overdo it: add just enough notes to help your own understanding/reading of your code. How much that is will vary from person to person.

Presenting the Answers

The problem statement outlines two cases we need to handle differently: the case where there were no triples, and the case where there were some.

The value of nTriples is exactly what we need to branch on.

• C++

if (nTriples == 0) {
    fprintf(outputFile, "Nothing here!\n");
} else {
    fprintf(outputFile, "%d\n", nTriples);
    // TODO: print the list of triples, separated by spaces
}

As for printing a space separated list of numbers, we might try the following:

for (int i = 0; i < nTriples; i++) {
    fprintf(outputFile, "%d ", triples[i]);
}
fprintf(outputFile, "\n");

This prints all the triples on one line, followed by a newline. But this is slightly off! Consider what would get printed based on our earlier example (where triples = [2, 4, 5, 9, 12, 13, 18, ...], and nTriples = 7):

This is almost what we want, except that there's a space at the end of the line where there shouldn't be one.

As it happens, the training site is a little forgiving of extra spaces at the end of lines. But rather than rely on this, let's try to print the output correctly to begin with. There are two major approaches we can take.

Method 1: print the first or last element outside of the loop

Thanks to our if statement, we know that there's at least one item in the triples array. So we can safely do this:

• C++

fprintf(outputFile, "%d", triples[0]);
for (int i = 1; i < nTriples; i++) {
    fprintf(outputFile, " %d", triples[i]);
}
fprintf(outputFile, "\n");

...or this:

• C++

for (int i = 0; i < nTriples - 1; i++) {
    fprintf(outputFile, "%d ", triples[i]);
}
fprintf(outputFile, "%d\n", triples[nTriples - 1]);

Trace through both of these code snippets. How do they print the space-separated list correctly?

Method 2: use an if statement inside the loop

Instead of handling the "special case" of the first or last element outside of the loop, we can use an if statement to do the same thing inside the loop:

• C++

for (int i = 0; i < nTriples; i++) {
    fprintf(outputFile, "%d", triples[i]);
    if (i == nTriples - 1) {
        fprintf(outputFile, "\n");
    } else {
        fprintf(outputFile, " ");
    }
}

Putting this all together nearly gives us a working solution to Triple Hunting.

...a bug?

If I assembled all the pieces we used above and tried running it on the first sample case, I'd get the following output:

4
1 3 4 6

This is incorrect, but it's close to being the correct answer! The second line of output should read "2 4 5 7", but instead every location our program printed out was 1 less than it was supposed to be. Our program has an off-by-one error.

How did this happen? Well, our program put the first triple (the number 12, in the 2nd position in the array) into input_array[1], the second position in the input_array array. (Recall that array indices are 0-based: the first value is at position 0, the second at position 1, and so on.)

Then, when the program detects that the 12 is a triple in the main loops, it adds a 1 (instead of a 2) to the triples array to mark the triple's position. Then during output writing, "1" is what the program prints out instead of "2".

Off-by-one errors like this are a very common form of bug. (Perhaps one part of a program starts numbering things at 0, but another part expects it to start numbering at 1. Or, perhaps one part of a program interpret "between 10 and 20" exclusively, meaning it doesn't count 10 or 20 as "between 10 and 20", but another part treats them inclusively.)

For the program we've written, there are at least three ways to fix this bug:

1. Add the missing +1 during output

   fprintf(outputFile, "%d", triples[i]+1);

   The rest of the program uses 0-based counting when reasoning about arrays. We add 1 to the output at the very last minute so that the rest of our data can be 0-based.

   If we're taking this approach, we should add a comment to the triples array declaration making it very clear that the numbers inside it are 0-based positions.

2. Add the missing +1 when we fill in the triples array

   triples[nTriples] = i + 1;

   We are only using the triples array for output, so we put the correct output values into it to begin with.

   If we're taking this approach, we should add a comment to the triples array declaration making it very clear that the numbers inside it are 1-based positions.

3. Change the main loop so that i goes from 1 to n

   for (int i = 1; i <= nNumbers; i++) {
       // nTriples = the number of triples we've found so far
       // there are nTriples values in the triples[] array
       if (input_array[i-1] % 3 == 0) {
           ...
       }
   }

   Instead of modifying i, we could make sure it has the correct value to begin with by looping between 1 and n (instead of 0 and n-1), inclusive.

   If we're taking this approach, we should add a comment to the triples array declaration making it very clear that the numbers inside it are 1-based positions. We also need to be very careful that we're still accessing the elements of input_array as if it is 0-based.

All of these approaches are equally valid and carry their own pros and cons. Whichever you choose to go with, it's important to remember which approach you've taken! Write comments and document the parts of your code that care about what i or the values in input_array mean. This is all simple enough to remember now when you're dealing with a short program with only three or four variables, but good commenting becomes invaluable when your programs get more complicated.

Once we've fixed that bug, we have a working solution for Triple Hunting.