Skip to main content
deleted 100 characters in body
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237

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

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

Thanks for your help. If you have any more comments on my style or methods, they are appreciated!

My solution, updated in response to Jamal and vnp:

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

Thanks for your help. If you have any more comments on my style or methods, they are appreciated!

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

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

added 817 characters in body
Source Link
  • 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.

Thanks for your help. If you have any more comments on my style or methods, they are appreciated!

  • 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.

Thanks for your help. If you have any more comments on my style or methods, they are appreciated!

Post Made Community Wiki by Jamal
Source Link

My solution, updated in response to Jamal and vnp:

#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;
}