Project Euler - 08

[Petcheco]

Hello, guys.

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Here's how I did it:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string Grid_of_Numbers =
"73167176531330624919225119674426574742355349194934"
"96983520312774506326239578318016984801869478851843"
"85861560789112949495459501737958331952853208805511"
"12540698747158523863050715693290963295227443043557"
"66896648950445244523161731856403098711121722383113"
"62229893423380308135336276614282806444486645238749"
"30358907296290491560440772390713810515859307960866"
"70172427121883998797908792274921901699720888093776"
"65727333001053367881220235421809751254540594752243"
"52584907711670556013604839586446706324415722155397"
"53697817977846174064955149290862569321978468622482"
"83972241375657056057490261407972968652414535100474"
"82166370484403199890008895243450658541227588666881"
"16427171479924442928230863465674813919123162824586"
"17866458359124566529476545682848912883142607690042"
"24219022671055626321111109370544217506941658960408"
"07198403850962455444362981230987879927244284909188"
"84580156166097919133875499200524063689912560717606"
"05886116467109405077541002256983155200055935729725"
"71636269561882670428252483600823257530420752963450";

vector<unsigned long int> Numbers_of_the_String(1000);
unsigned long long  int Highest_Product = 0;

void Copy_String(vector<unsigned long int>,string);
void Find_the_Highest_Product(vector<unsigned long int>);
void Show_Value(unsigned long  long int);

void Copy_String(vector<unsigned long int>, string)
{
    string Temporary_Value = "";
    for(int i = 0; i < 1000; i++)
    {
        Temporary_Value = Grid_of_Numbers[i];
        Numbers_of_the_String[i] = stoi(Temporary_Value);
    }
    Find_the_Highest_Product(Numbers_of_the_String);
}

void Find_the_Highest_Product(vector<unsigned long int> Numbers_of_the_String)
{
    unsigned long long  int Product = 1;

    for(int i = 0; i < 1000;i++)
    {

        Product = 1;
        for(int j = i; j < i+13; j++)
        {

        Product = Product * Numbers_of_the_String[j];
            if (Product == 0)
                j = i+13;
        }
         if (Product > Highest_Product)
            {
                Highest_Product = Product;
            }
    }
    Show_Value(Highest_Product);
}

void Show_Value(unsigned long long  int Highest_Product)
{
    cout << "\n\n" << Highest_Product << endl;
}

int main()
{
    Copy_String(Numbers_of_the_String, Grid_of_Numbers);
    return 0;
}

Is there a way to do this challenge without using unsigned long long integers ?

Thank you.

Petcheco

[tinstaafl]

I would suggest not, since the maximum value you might encounter is 9 to the power of 13, which will need a structure that big.

Creating an integer from a char can be more simply done by subtracting the '0' char from the char which will implicitly cast to an int.

Numbers_of_the_String[i] = Grid_of_Numbers[i] - '0';

I would also suggest using the product from the previous batch of digits. Divide out the old first digit and multiply in the new digit. This should ne alot less expensive than creating a new product for each batch of 13 digits.

[rubberman]

Here is the results I come up with: 9*9*9*9*9*9*9*9*9*9*9*9*9 (9^13) == 2541865828329, which definitely requires an unsigned long long. When I tried a simple long unsigned value, the compiler (gcc 4.4.7) complained about an integer overflow.

[rubberman]

@tinstaafl - an interesting adaptation, though I think that even (slightly less than) ~1000 computations will, on current processors, not take enough time to measure, or at least to bother with. If this were frequently done in a production system, then I would agree with your analysis, and that it may be worth it from the performance perspective. I still prefer to start with the KISS principle, and then see if I need to speed things up. My philosophy for software engineering is that first, you make it right, and then you make it fast! :-)

[Petcheco]

I didn't know about that, tinstaafl. Very interesting.

Thanks for your tips.

[Petcheco]

@tinstaffl

How would I implement that idea of yours? Could you provide a small code snipet?

I suppose I would have to multiply the value of the product by the number in the "i" and the number in the "i+12" position and divide by the number in the "i-1" position.

Is that correct?

Thank you.

[tinstaafl]

Here's a function I made a while back for this problem. Another aspect of this problem I forgot about, is that any 13 digit combination that includes a 0 will produce 0 for an answer. This function takes that into account as well:

typedef unsigned long long ull;

ull FindMaxProduct(string input, int digits)
{
    ull maxProduct = 0;
    stringstream ss(input);
    string temp = "";
    while (getline(ss,temp,'0'))
    {
        int size = temp.length();
        if (size >= digits)
        {
            ull tempProduct = 1;
            int i = 0;
            for (; i < digits; i++)
            {
                tempProduct *= (temp[i] - '0');
            }
            if (tempProduct > maxProduct)
            {
                maxProduct = tempProduct;
            }
            for (; i < size; i++)
            {
                tempProduct = ((tempProduct / (temp[i - digits] - '0')) * (temp[i] - '0'));
            }
            if (tempProduct > maxProduct)
            {
                maxProduct = tempProduct;
            }
        }
    }
    return maxProduct;
}

[Petcheco]

Thanks, mate. I'll try and understand your code.