Problem 8 :: Project Euler (Solution)

[lxXTaCoXxl]

I think this is the first actual discussion thread of code on a coder's website I've actually ever seen, and I'm the one posting it. (HA!) So basically; I got bored and found a website called Project Euler. It has a bunch of "mathematical" problems to solve. Eight pages and I believe 50 problems per page. Well I've been jumping back and forth between pages all day solving the problems out of boredom. Well, I came across this one and just had to share my work. It was the first time I've ever implemented the .Substring(int, int) method before so it gave me a little bit of problems at first, but I figured it out and got the answer. I'm deciding to share my source code as well as the answer to the problem. I just wanted to know other's thoughts on the topic and see if there is a way (which I'm sure there is) to shorten the source code, or even a completely different way of solving this problem.

The problem is: Find the highest product of 5 consecutive digits in the 1000 digit number.
Answer: 40,824 with 994 possible other answers, and the consecutive digits being 9,9,8,7,9.

Source:

            private string OneThousandDigitNumber = "7316717653133062491922511967442657474235534
            919493496983520312774506326239578318016984801869478851843858615607891129494954595017
            379583319528532088055111254069874715852386305071569329096329522744304355766896648950
            445244523161731856403098711121722383113622298934233803081353362766142828064444866452
            387493035890729629049156044077239071381051585930796086670172427121883998797908792274
            921901699720888093776657273330010533678812202354218097512545405947522435258490771167
            055601360483958644670632441572215539753697817977846174064955149290862569321978468622
            482839722413756570560574902614079729686524145351004748216637048440319989000889524345
            065854122758866688116427171479924442928230863465674813919123162824586178664583591245
            665294765456828489128831426076900422421902267105562632111110937054421750694165896040
            807198403850962455444362981230987879927244284909188845801561660979191338754992005240
            636899125607176060588611646710940507754100225698315520005593572972571636269561882670
            428252483600823257530420752963450";

            private void button1_Click(object sender, EventArgs e) {
                List<int> Possibles = new List<int>();
                List<string> Pos2 = new List<string>();

                for (int i = 0; i < OneThousandDigitNumber.Length - 5; i++) {
                    int Temp = 0;
                    string Temp2 = "";

                    Temp = Convert.ToInt32(OneThousandDigitNumber.Substring(i, 1));
                    Temp *= Convert.ToInt32(OneThousandDigitNumber.Substring(i + 1, 1));
                    Temp *= Convert.ToInt32(OneThousandDigitNumber.Substring(i + 2, 1));
                    Temp *= Convert.ToInt32(OneThousandDigitNumber.Substring(i + 3, 1));
                    Temp *= Convert.ToInt32(OneThousandDigitNumber.Substring(i + 4, 1));

                    Temp2 = OneThousandDigitNumber.Substring(i, 1);
                    Temp2 += OneThousandDigitNumber.Substring(i + 1, 1);
                    Temp2 += OneThousandDigitNumber.Substring(i + 2, 1);
                    Temp2 += OneThousandDigitNumber.Substring(i + 3, 1);
                    Temp2 += OneThousandDigitNumber.Substring(i + 4, 1);

                    Possibles.Add(Temp);
                    Pos2.Add(Temp2);
                }

                int Highest = 0;
                string High2 = "";

                for (int i = 0; i < Possibles.Count; i++) {
                    if (Possibles[i] > Highest) {
                        Highest = Possibles[i];
                        High2 = Pos2[i];
                    }
                }

                MessageBox.Show("The highest possible product of five consecutive digits in the 
                one thousand digit number is: " + Highest.ToString() + "\nWith " + 
                Possibles.Count.ToString() + " possibles.\nThe consecutive digits were: " + High2);
            }

So what are the thoughts of other programmers on the site?

Love to hear some replies!
Jamie

[Momerath]

Couple things you could do to speed this up:

You don't need to save all the values then find the largest, just keep track of the current largest as you calculate the values.

You convert every character to an int multiple times, see if you can figure out how to just convert them one time.

If you ever have a zero (0) is your 'group of five' the result will always be zero. When you find a zero, skip over them (don't check all five possible values, you know they are all zero).

-----

Of course this code should be running in a fraction of a second anyway, but if you had to do a string with millions of characters ... :)

[Momerath]

Here is a solution I came up with:

        private void Momerath() {
            int result = (from i in NextValue()
                          select i).Max();

            Console.WriteLine("Maximum value is {0}", result);
        }

        private IEnumerable<int> NextValue() {
            Queue<int> que = new Queue<int>(from c in OneThousandDigitNumber.ToArray() select Int32.Parse(c.ToString()));
            Queue<int> group = new Queue<int>();
            int result = 1;
            while (que.Count > 0) {
                int val = que.Dequeue();
                if (val == 0) {
                    result = 1;
                    group.Clear();
                } else {
                    group.Enqueue(val);
                    result *= val;
                    while (group.Count > 5) {
                        result /= group.Dequeue();
                    }
                    if (group.Count == 5) yield return result;
                }
            }
        }

Timing yours and mine (over 10000 iterations, otherwise it's hard to see the difference :)) resulted in 16110 milliseconds for your solution and 5132 milliseconds for mine. I removed the output from both as displaying the value 10,000 times just slowed them down and didn't provide any information as to the algorithm speed.

[Momerath]

And another one. This one is actually slower (13299 milliseconds for 10,000 iterations) but uses the Parallel library. It's slower as creating all the tasks takes much longer than each individual task.

private void Momerath2() {
    ConcurrentBag<int> bag = new ConcurrentBag<int>();

    Parallel.For(0, OneThousandDigitNumber.Length - 4, act =>
        {
            int value = Int32.Parse(OneThousandDigitNumber.Substring(act, 1)) *
                        Int32.Parse(OneThousandDigitNumber.Substring(act+1, 1)) *
                        Int32.Parse(OneThousandDigitNumber.Substring(act+2, 1)) *
                        Int32.Parse(OneThousandDigitNumber.Substring(act+3, 1)) *
                        Int32.Parse(OneThousandDigitNumber.Substring(act+4, 1));
            bag.Add(value);
        });

    int result = bag.Max();
    Console.WriteLine("value is {0}", result);
}

[TrustyTony]

Interesting, as my solution splitting the string at zeroes and testing the subsequences longer than 4, took around 2.457 ... 2.751 ms in Python (including split and conversion of the 837 digits to integers before check)

[lxXTaCoXxl]

How are you measuring the speeds of the algorithms? I've been looking but can't find anything. I find the solutions you posted interesting. :)

See I would love some more acutal discussion threads on source code solutions. This is a must for me and my team. It allows other people to see the programming styles of other programmers and learn from them. It's always been a good thing to me. :D

[hericles]

come on man, don't put up your euler solutions. Other people that can't solve it are just going to copy your answer which just weakens the site. You can see other people's solutions on the site once you've solved a particular problem anyway.
I've noticed the Python solutions on the site are always blisteringly fast.

[Momerath]

don't put up your euler solutions

The solutions are all over the internet. There is even a site that just has the answers (no code) so you can just type them in.

[Momerath]

This is the code I use to time solutions

using System;
using System.Diagnostics;

namespace BlogEulerC {
    class Program {
        static void Main(string[] args) {
            Stopwatch sw = new Stopwatch();
            ISolution s = new Problem0008();

            int limit = 10000;

            sw.Start();
            for (int i = 0; i < limit; i++) {
                s.Solve();
            }
            sw.Stop();

            Console.WriteLine("--------------");
            Console.WriteLine("Solution took {0} milliseconds", sw.ElapsedMilliseconds);
            Console.ReadLine();
        }
    }
}

ISolution is an interface with one method, Solve(). Yes, the timing includes the For loop, but it includes it for all timings so it should just be a constant addition to the time. I could create a better timing routine, but haven't had the desire to do so. Maybe I will now :)