5
\$\begingroup\$

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;
}
\$\endgroup\$
0
3
\$\begingroup\$
  • 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.

\$\endgroup\$
3
  • \$\begingroup\$ That's a good catch, except that I need to initialize line outside the scope of the while loop. It now looks like this:string series, line; while (getline(ifs, line)) { series += line; } \$\endgroup\$ Oct 3 '14 at 3:54
  • \$\begingroup\$ @castle-bravo: Oh yeah, I forgot to change that part, so I'll do it now. Thanks! \$\endgroup\$
    – Jamal
    Oct 3 '14 at 3:58
  • \$\begingroup\$ “while( !feof( file ) )” is always wrong The same rule applies to if (ifs.good()) \$\endgroup\$ Oct 3 '14 at 6:24
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Hey vnp, thanks for the tips. I refactored my code and would like to know what you think. The new version checks against the size of the input, increments i by DIGITS_IN_PRODUCT as soon as zero is encountered using a recursive function, and recalculates using division and multiplication. See the answer that I just posted. \$\endgroup\$ Oct 3 '14 at 6:44
0
\$\begingroup\$

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;
}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.