Project Euler Problem 8: Largest product in a series

Question

The problem statement is as follows:

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?

My code below solves the problem. I know this enters into the realm of preference but is it taboo to merge the 100 digit number onto a single line as I initially did but commented out, or is the method utilizing StringBuilder for "readability" better?

public class Program
{       
    public static void Main(string[] args)
    {
        //string numbers = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
        string numbers = Get100DigitNumber();

        Console.WriteLine(MaxProductNumericStringOfLength(numbers,13));
    }

    static long ProductOfNumericString(string number)
    {
        long product = 1;
        for (int digit = 0; digit<number.Length ; digit++)
        {
            product *= int.Parse(number[digit].ToString());
        }
        return product;
    }

    static long MaxProductNumericStringOfLength(string numberString, int length)
    {
        long maxSubstring=0;
        long possibleMaxSubstring;
        for (int position = 0; position < numberString.Length-length ; position++)
        {
            possibleMaxSubstring = ProductOfNumericString(numberString.Substring(position,length));

            if (possibleMaxSubstring > maxSubstring)
                maxSubstring=possibleMaxSubstring;
        }

        return maxSubstring;
    }

    static string Get100DigitNumber()
    {
        StringBuilder sb = new StringBuilder();
        sb.Append("73167176531330624919225119674426574742355349194934");
        sb.Append("96983520312774506326239578318016984801869478851843");
        sb.Append("85861560789112949495459501737958331952853208805511");
        sb.Append("12540698747158523863050715693290963295227443043557");
        sb.Append("66896648950445244523161731856403098711121722383113");
        sb.Append("62229893423380308135336276614282806444486645238749");
        sb.Append("30358907296290491560440772390713810515859307960866");
        sb.Append("70172427121883998797908792274921901699720888093776");
        sb.Append("65727333001053367881220235421809751254540594752243");
        sb.Append("52584907711670556013604839586446706324415722155397");
        sb.Append("53697817977846174064955149290862569321978468622482");
        sb.Append("83972241375657056057490261407972968652414535100474");
        sb.Append("82166370484403199890008895243450658541227588666881");
        sb.Append("16427171479924442928230863465674813919123162824586");
        sb.Append("17866458359124566529476545682848912883142607690042");
        sb.Append("24219022671055626321111109370544217506941658960408");
        sb.Append("07198403850962455444362981230987879927244284909188");
        sb.Append("84580156166097919133875499200524063689912560717606");
        sb.Append("05886116467109405077541002256983155200055935729725");
        sb.Append("71636269561882670428252483600823257530420752963450");

        return sb.ToString();
    }
}

Answer 1

A better option is to use a constant expression. The text in 7.15 Constant expressions says:

A constant-expression is an expression that can be fully evaluated at compile-time.

const string number =
    "73167176531330624919225119674426574742355349194934" +
    "96983520312774506326239578318016984801869478851843" +
    "85861560789112949495459501737958331952853208805511" +
    ...
    "71636269561882670428252483600823257530420752963450";

This way the string has not to be constructed at runtime.

Also consider using a project resource for the string or storing the number in a file. See: Adding and Editing Resources (Visual C#)

Answer 2

Efficiency consideration:

Each time you call .Substring(), a new string object is created. String's in C# are immutable (scroll down on https://msdn.microsoft.com/en-us/library/system.string(v=vs.110).aspx). You've already seen your code work on 1000 digit numbers, but in the future someone may want to try it with 10,000 digit numbers (or even more!).

String's can be indexed directly using array notation (i.e. numberString[i]).

---

Speaking of trying your code with other numbers, I like that your code is split into different methods and the number-getting code is separate from the calculating-code. Good Job!

---

Slight nit-pick: Your method Get100DigitNumber is returning a 1000 digit number. Rather than add the missing 0, a better solution would be to come up with a more general name for the method. This will go especially well with Olivier's suggestion to store the number outside the code. That way numbers of varying lengths can be used.

Answer 3

When you've got a hundred characters hardcoded in your code, readability really isn't the issue you should focus on. Don't use the StringBuilder just for the sake of making it cute, especially in cases like the Euler Projects where you want your code to run as fast as possible (At least, that's my objective when I do these!).

A method name should always reflect an action. Otherwise you'll you a property. So, if we focus on this, we should change MaxProductNumericStringOfLength to something like FindHighestProductOfConsecutiveNumbers.

Now, this algorithm is about numbers, not characters. You used the string because it would be sooo long to create an array with all the int, but you need to change that as "soon" as possible in your algorithm.

Meaning, the FindHighestProductOfConsecutiveNumbers should receive a int[] or an IEnumerable<int>, to your choice.

string numberString = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

//Call ToArray if you want it or not!
IEnumerable<int> numbers = numberString.Select(n => (int)(n - '0'));

Doing this, you'll be able to work with what you really want : Numbers. Your code will reflect your intent much better this way.

Answer 4

Aside from the concern of storing the string,

converting each character to an int is more easily done by simply subtracting 0 from the char value.

a rolling product rather than multiplying 13 digits for each new segment is quite a bit more efficient.

any segment that contains a 0 can automatically be discounted since the product will be 0. One way to take care of this is by splitting the string using 0 as the separator and removing empty strings. Using the LINQ extension Where gives one the option of eliminating any string less than 13 characters.

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

static long GetMaxProduct(int segment)
{
    var segments = data.Split(new char[] { '0' },System.StringSplitOptions.RemoveEmptyEntries)
                       .Where(x => x.Length >= segment);
    long maxProduct = 1;
    foreach(string s in segments)
    {
        int i = 0;
        long product = 1;
        for (; i < segment; i++)
        {
            product *= s[i] - '0';
        }
        for (; i < s.Length;i++)
        {
            product = (product / (s[i - segment] - '0')) * (s[i] - '0');
            if(product > maxProduct)
            {
                maxProduct = product;
            }
        }
    }
    return maxProduct;
}

Answer 5

You are parsing each char to int several times.

I think a rolling product would be more efficient
This is O(n) where you are O(n * 13)

private static long MaxProduct2(string input, int len)
{
    if (string.IsNullOrEmpty(input))
    {
        input = "73167176531330624919225119674426574742355349194934" +
            "96983520312774506326239578318016984801869478851843" +
            "85861560789112949495459501737958331952853208805511" +
            "12540698747158523863050715693290963295227443043557" +
            "66896648950445244523161731856403098711121722383113" +
            "62229893423380308135336276614282806444486645238749" +
            "30358907296290491560440772390713810515859307960866" +
            "70172427121883998797908792274921901699720888093776" +
            "65727333001053367881220235421809751254540594752243" +
            "52584907711670556013604839586446706324415722155397" +
            "53697817977846174064955149290862569321978468622482" +
            "83972241375657056057490261407972968652414535100474" +
            "82166370484403199890008895243450658541227588666881" +
            "16427171479924442928230863465674813919123162824586" +
            "17866458359124566529476545682848912883142607690042" +
            "24219022671055626321111109370544217506941658960408" +
            "07198403850962455444362981230987879927244284909188" +
            "84580156166097919133875499200524063689912560717606" +
            "05886116467109405077541002256983155200055935729725" +
            "71636269561882670428252483600823257530420752963450";
    }
    if (input.Length < len)
    {
        throw new IndexOutOfRangeException();
    }

    long maxProduct = 0;
    foreach (string segment in input.Split(new char[] { '0' }))
    {
        if(segment.Length < len)
        {
            continue;
        }
        //Debug.WriteLine(segment);
        int[] products = new int[segment.Length];
        int count = 0;
        foreach (char c in segment)
        {
            products[count] = int.Parse(c.ToString());
            count++;
        }
        long product = 1;
        for (int i = 0; i < products.Length; i++)
        {
            product *= products[i];
            if (i == len - 1)
            {
                maxProduct = product;
            }
            else if (i >= len)
            {                      
                product /= products[i - len]; 
            }
            if (maxProduct < product)
            {
                maxProduct = product;
            }
        }
    }
    return maxProduct;
}