Project Euler problem 8
Find the largest product of any 13 digit number within a larger number.
Solution
The first thing we need to decide is how to read in the input number.
Read the whole input. This has the advantage of allowing us to create a 13 digit moving window. However, we don't know how large the input will be (assuming we're not hardcoding the length of the puzzle), so allocating sufficient memory would be difficult. We could make a guess and gradually reallocate a larger block when it is exceeded, but that seems like a lot of work for a relatively straightforward problem.
Read one digit at a time. This is possibly less efficient from an I/O point of view, but it does mean that we only need to hold a fixed number of digits (13) in memory at any one time. Since we know this at compile time, we can create an array of the current digits. This has the bonus of being allocated on the stack automatically, so no memory management is required.
Our first step is to read the first 13 digits, to populate our buffer. getchar does most of the work for us, reading from stdin. We need to check the following:
- How many digits read so far - we don't want to read more than 13 (
DIGIT_COUNT), as this will overflow our buffer. - Whether we have reached the end of the input (
EOF), otherwise the program will continue indefinitely. - If the character read is a digit, because we want to ignore any other characters (e.g. newlines).
We also need to convert the return value of getchar from an int representation to the decimal value of the digit. The conventional way to do this is to subtract the value of the character literal '0' (which is represented as int, not char). This assumes that the characters 0-9 are sequential, which is the case for all encodings in widespread use, and also required by the C standard:
In both the source and execution basic character sets, the value of each character after 0 in the above list of decimal digits shall be one greater than the value of the previous.
If you want a historical example of an encoding which does not meet the standard, take a look at the Baudot code.
All of this is possible with a while loop:
#define DIGIT_COUNT 13
int digits[DIGIT_COUNT];
int digits_read = 0;
int c = 0;
while (digits_read < DIGIT_COUNT && (c = getchar()) != EOF) {
if (isdigit(c)) {
digits[digits_read] = c - '0';
digits_read++;
}
}
The next step is to calculate the product of the digits in the buffer, update the largest product, and get the next character. For safety we also check first whether the buffer contains 13 digits - if not then the input is too small and we can skip over this section.
We use a do...while loop as we want to check the buffer at least once, and our termination test comes at the end.
int64_t largest_product = 0;
int64_t current_product = 1;
if (digits_read == DIGIT_COUNT) {
do {
// Calculate current product
current_product = 1;
for (int d = 0; d < DIGIT_COUNT; d++) {
current_product *= digits[d];
}
if (current_product > largest_product) {
largest_product = current_product;
}
c = getchar();
if (c != EOF && isdigit(c)) {
// Move all digits down one space, and
// add the latest one at the end
for (int d = 0; d < DIGIT_COUNT; d++) {
digits[d] = digits[d+1];
}
digits[DIGIT_COUNT - 1] = c - '0';
}
} while (c != EOF);
}
Note that we use the int64_t type for the product, as this guarantees a 64 bit integer, whereas int does not - even on a 64 bit platform. The reason for this is that the largest possible product of 13 digits is if every digit was 9, i.e. 9^13. This exceeds the maximum size of a 32 bit integer, causing an overflow which would give an incorrect result (e.g. a negative number). However, we still use a signed integer for consistency with the rest of the code, otherwise we would have to cast the return value of getchar.
The full solution is:
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <stdint.h>
#include <inttypes.h>
#define DIGIT_COUNT 13
int main() {
int digits[DIGIT_COUNT];
int digits_read = 0;
int c = 0;
int64_t largest_product = 0;
int64_t current_product = 1;
while (digits_read < DIGIT_COUNT && (c = getchar()) != EOF) {
if (isdigit(c)) {
digits[digits_read] = c - '0';
digits_read++;
}
}
if (digits_read == DIGIT_COUNT) {
do {
// Calculate current product
current_product = 1;
for (int d = 0; d < DIGIT_COUNT; d++) {
current_product *= digits[d];
}
if (current_product > largest_product) {
largest_product = current_product;
}
c = getchar();
if (c != EOF && isdigit(c)) {
// Move all digits down one space, and
// add the latest one at the end
for (int d = 0; d < DIGIT_COUNT; d++) {
digits[d] = digits[d+1];
}
digits[DIGIT_COUNT - 1] = c - '0';
}
} while (c != EOF);
}
printf("%" PRIi64 "\n", largest_product);
return EXIT_SUCCESS;
}