Flex you grey matter by solving some Project Euler problems

To mix things up a bit I’ve been solving some project Euler coding problems recently. For those of you unfamiliar, project Euler is a series of challenging mathematical/computer programming problems that get progressively more difficult. The problems build on each other, once you solve the first problem you unlock a concept that you will need to solve a future problem. I’m really enjoying it and I’d recommend it to any programmer – it gets you flexing the old grey matter and solving problems in different ways.

I’ve decided to tackle the problems in C# using 3 different approaches as follows. Later I plan to circle back and solve them again using a dynamic language to compare the two experiences.

(1) Brute Force 

To start with I dumb it down and apply a brute force algorithm. This helps me to understand the problem and this gives me a benchmark for comparing against the other approaches. While brute forcing the solution is by no means the best approach I find this to be a good starting point and it makes me appreciate the elegant solutions even more when I get to them.

(2) LINQ Expressions

LINQ  isn’t the first thing that jumps to mind when you think about solving mathematical problems but its turns out that focusing on writing an elegant LINQ solution rather than an efficient mathematical solution can result in some really expressive and concise code.

Here’s some examples

“What is the largest prime factor of the number 600851475143”

        public string LinqSolve()
        {
             return Factors.GetFactors(600851475143).ToList().Where(x => x.IsPrime()).OrderBy(x => x).Last().ToString();
        }

“Find the largest palindrome made from the product of two 3-digit numbers”

        public string  LinqSolve()
        {
            var factors = Enumerable.Range(100, 900);
            var maxlargestPallindrome = factors.SelectMany(x => factors.Select(y => x * y)).Where(x => x.ToString().Reverse().SequenceEqual(x.ToString())).Max();
            return maxlargestPallindrome.ToString();
        }

“Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.”

        public string LinqSolve()
        {        
            return (Math.Pow(Enumerable.Range(1,100).Sum(),2) - Enumerable.Range(1,100).Sum(n=>n*n)).ToString(CultureInfo.InvariantCulture);
        }

(3) Algebraic / Propeller Head Approach

Finally I’m solving the problem using the magic of mathematics. You need to understand the mathematics behind the problem to come up the most optimised solution.

 

Solving project Euler problem requires a mixture of math, coding techniques, joy and pain. Here are my solutions , if you are interested I’d encourage you to get stuck in and try for yourself.

May the source be with you!

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s