Project Euler #8 - "largest product in a series"

Question

This code works when compiled on gcc 4.8.2.

I would appreciate any comments on my style and the readability of my code, and any improvements that I could make to make the code more readable and/or performant.

Problem: Largest product in a series

Solution:

/*
 * file:    pe_008.cc
 * title:   Largest product in a grid
 * date:    October 2, 2014
 * 
 * note:    The largest possible product of 13 consecutive digits
 *          in a decimal number is 9^13. log_2(9^13) = ~41.2, so we
 *          will need to use a 64-bit integer to represent the product.
 * 
 * note 2:  Since some of the elements in the series are 0. The product
 *          of the digits in the 13-digit subseries will be 0 if any of
 *          the elements are 0. This means that if we see a 0, we can
 *          skip ahead by 13 digits, but we have to cache the nonzero
 *          digits that we skip over.
 */

#include <fstream>
#include <iostream>
using namespace std;

const int DIGITS_IN_PRODUCT = 13;

int main() {
  // read series.txt into a string without newline characters
  ifstream ifs("../series.txt");
  string series;
  while (ifs.good()) {
    string line;
    getline(ifs, line);
    series += line;
  }
  ifs.close();
  // take the product of the first 13 elements in the string
  uint64_t product = 1;
  uint64_t max_product;
  uint8_t product_digits[DIGITS_IN_PRODUCT];
  for (size_t i = 0; i < DIGITS_IN_PRODUCT; i++) {
    product_digits[i] = series[i] - '0';
    product *= product_digits[i];
  }
  max_product = product;
  int zero_for_next = 0;
  for (size_t i = DIGITS_IN_PRODUCT; i < series.length(); i++) {
    // use the modulo operator to minimize overwrites
    product_digits[i % DIGITS_IN_PRODUCT] = series[i] - '0';
    if (series[i] == '0') {
      zero_for_next = DIGITS_IN_PRODUCT;
      continue;
    } else if (zero_for_next < 1) {
      product = 1;
      // the order in which the product is taken is not important
      for (uint8_t digit : product_digits) {
        product *= digit;
      }
      if (product > max_product) {
        max_product = product;
      }
    }
    zero_for_next--;
  }
  cout << max_product << endl;
}

Answer 1

• This is probably not a good idea:

  while (ifs.good()) {
    string line;
    getline(ifs, line);
    series += line;
  }
  

  You should be checking the stream itself, not the current state of the stream. This can be done by putting the stream read (getline() in this case) inside the loop statement.

  Also, as getline() (which uses line) will be moved out of scope after this change, you'll need to initialize line before the loop.

  string line;
  
  while (getline(ifs, line)) {
      series += line;
  }
  

  This will both attempt the read and determine if it was successful. If it wasn't, specifically if the end of the file has been reached, then it will fail, and the loop will terminate. See this answer for more info.

• Your compiler should've warned you about this type-mismatch:

  for (size_t i = 0; i < DIGITS_IN_PRODUCT; i++)
  

  The loop counter type should be an int to match the constant's type.

Answer 2

Few points maybe not related directly to PE8.

• A code assumes that at least 13 digits are present; the for (size_t i = 0; i < DIGITS_IN_PRODUCT; i++) loop will break for shorter inputs.

• It is OK to increment i by DIGITS_IN_PRODUCT as soon as a zero is encountered. Adding a state (such as zero_for_next) to a loop usually means that the loop should needs refactoring.

• Recalculating the whole product on a window shift is wasteful. Divide a current product by a digit shifted out, and multiply it by a digit shifted in. 2 operations instead of 13.

Answer 3

My solution, updated in response to @Jamal and @vnp:

• Eliminated the while (ifs.good()) loop and replaced it with while (getline(ifs, line))
• Changed the type of DIGITS_IN_PRODUCT from const int to const size_t. This eliminates compiler warnings for signed/unsigned integer comparisons.
• Added a conditional to check that the string series is at least as long as DIGITS_IN_PRODUCT
• Added a function refill_window that refills the window and updates the index in the main loop if one of the elements in the string series turns out to be '0'. It it encounters another zero during refill, it calls itself.
• Now uses divide-substitute-multiply to update product
• Added a function window_product to compute product in a single sweep where necessary, i.e. after initializing or refilling the window.

Both solutions run in about 1ms, so I can't tell which is faster using bash time.

#include <fstream>
#include <iostream>
using namespace std;

const size_t DIGITS_IN_PRODUCT = 13;

void refill_window(string &series, size_t &i, uint8_t* window);
uint64_t window_product(uint8_t* window);

int main() {
  // read series.txt into a string without newline characters
  ifstream ifs("../series.txt");
  string series, line;
  while (getline(ifs, line)) {
    series += line;
  }
  ifs.close();
  if (series.size() < DIGITS_IN_PRODUCT) {
    cout << "Error: series.txt contains too few elements." << endl;
    exit(2);
  }
  uint8_t window[DIGITS_IN_PRODUCT];
  for (size_t i = 0; (i < DIGITS_IN_PRODUCT) && (i < series.length());
       i++) {
    if (series[i] == '0') {
      refill_window(series, i, window);
      break;
    }
    window[i] = series[i] - '0';
  }
  uint64_t product = window_product(window);
  uint64_t max_product = product;
  for (size_t i = DIGITS_IN_PRODUCT; i < series.length(); i++) {
    if (series[i] == '0') {
      refill_window(series, i, window);
      product = window_product(window);
    } else {
      product /= window[i % DIGITS_IN_PRODUCT];
      window[i % DIGITS_IN_PRODUCT] = series[i] - '0';
      product *= window[i % DIGITS_IN_PRODUCT];
    }
    if (product > max_product) {
      max_product = product;
    }
  }
  cout << max_product << endl;
}

void refill_window(string &series, size_t &i, uint8_t* window) {
  i++;
  for (size_t j = 0;
       (j < DIGITS_IN_PRODUCT) && (i < series.length()); j++, i++) {
    if (series[i] == '0') {
      refill_window(series, i, window);
      return;
    }
    window[i % DIGITS_IN_PRODUCT] = series[i] - '0';
  }
  i--; // correct for final increment in for loop.
}

uint64_t window_product(uint8_t* window) {
  uint64_t product = 1;
  for (size_t i = 0; i < DIGITS_IN_PRODUCT; i++) {
    product *= window[i];
  }
  return product;
}