Let's solve Triple Hunting.
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:
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.
We set ourselves an intermediate goal of collecting all the triple locations into a list.
(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 a list:
input_list = []
for i in range(nNumbers):
input_list.append(int(inputFile.readline().strip()))
# TODO: count and collect the triples
# TODO: write the output
We want to declare a new list triples
that is going to hold all the triples.
triples = []
Now, as we go through the list, our code to count and collect the triples will look something like this:
nTriples = 0;
for i in range(nNumbers):
# nTriples = the number of triples we've found so far
# there are nTriples values in the triples list
if input_list[i] % 3 == 0:
# the number is a triple
triples.append(i)
nTriples += 1
}
}
(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 list
". This is a
reminder of how the code is supposed to behave and serves a
couple of purposes:
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.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.
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.
if nTriples == 0:
outputFile.write("Nothing here!\n")
else:
outputFile.write("{}\n".format(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 i in range(nTriples):
outputFile.write("{} ".format(triples[i])
outputFile.write("\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):
"2 4 5 9 12 13 18 \n"
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.
Thanks to our if
statement, we know that there's at least one item
in the triples
list. So we can safely do this:
outputFile.write("{}".format(triples[0]));
for i in range(1, nTriples):
outputFile.write(" {}".format(triples[i]))
outputFile.write("\n")
...or this:
for i in range(0, nTriples - 1):
outputFile.write("{} ".format(triples[i]))
outputFile.write("{}\n".format(triples[nTriples - 1]))
Trace through both of these code snippets. How do they print the space-separated list correctly?
if
statement inside the loopInstead 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:
for i in range(nTriples):
outputFile.write("{}".format(triples[i]))
if i == nTriples - 1:
outputFile.write("\n")
else:
outputFile.write(" ")
Putting this all together nearly gives us a working solution to Triple Hunting.
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 input_list) into input_list[1]
, the second
position in input_list
. (Recall that list 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
list 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:
Add the missing +1 during output
outputFile.write("{}".format(triples[i]+1))
The rest of the program uses 0-based counting when reasoning about lists. 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.
Add the missing +1 when we fill in the triples
list
triples[nTriples] = i + 1
We are only using the triples
list 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.
Change the main loop so that i
goes from 1 to nNumbers
for range(1, nNumbers+1): # nTriples = the number of triples we've found so far # there are nTriples values in the triples[] array if input_list[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_list
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_list
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.
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:
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.
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:
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.
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:
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.
triples
= [2, 4, 5, 9, 12, 13, ???, ???, ...]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:
triples
= [2, 4, 5, 9, 12, 13, ???, ???, ...]
nTriples
= 6Now, say our program discovers its next triple at the 18th position in the array. Then afterwards we want the following state:
triples
= [2, 4, 5, 9, 12, 13, 18, ???, ???, ...]
nTriples
= 7What 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:
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:
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.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.
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.
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):
printf("2 4 5 9 12 13 18 \n");
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.
Thanks to our if
statement, we know that there's at least one item
in the triples
array. So we can safely do this:
fprintf(outputFile, "%d", triples[0]);
for (int i = 1; i < nTriples; i++) {
fprintf(outputFile, " %d", triples[i]);
}
fprintf(outputFile, "\n");
...or this:
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?
if
statement inside the loopInstead 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:
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.
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:
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.
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.
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.