Project Euler Problem #6

CodeProject
Time for Problem 6. (Don't worry. This one is fairly simple.)

The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

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

To me, this one screams brute force. In fact, I think it would be insulted if I executed any more brain power to develop a non-brute force method. So brute force it is.

First we need to find the sum of the squares for 1-100. We can do this using Enumerables and lamda expressions and have it all in one handy dandy line of code:

 var sumOfSquares = (long)Enumerable.Range(1, 100).Sum(i => Math.Pow(i, 2));

All this does is generate an enumeration of all numbers from 1 to 100 and sum each square.

Now for the square of the sum:

 var squareOfSum  = (long)Math.Pow(Enumerable.Range(1, 100).Sum(), 2);

This is very similar to the previous, but we just grab the square of the sum of the number enumeration. That's it.

Now we can combine it all and retrieve our final answer:

 var sumOfSquares = (long)Enumerable.Range(1, 100).Sum(i => Math.Pow(i, 2));
 var squareOfSum = (long)Math.Pow(Enumerable.Range(1, 100).Sum(), 2);
 return squareOfSum - sumOfSquares;

And now we have our difference between the sum of squares and the square of the sum!
Awesome.

Project Euler Problem #5

CodeProject
Ready or not, here comes problem five!

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

This one really doesn't require that much explanation. I suppose we could easily brute force this one also, but that just isn't my style. So I'll just go ahead and show the final return statement that gives us the answer:

 return Enumerable.Range(1, 20).Aggregate(this.LeastCommonDivisor);

....Alright....that's it. Lets go home.

No?

Okay fine. Let me explain a bit. We are using the 'Aggregate' Extension here on our range of 1-20. The 'Aggregate' method will take our recursive method 'LeastCommonDivisor'.

Here is that function:

 private int LeastCommonDivisor(int i, int j)
 {
 	return (i == 0) || (j == 0) ? 0 : (i / this.GreatestCommonDivisor(i, j)) * j;
 }

That function also makes reference to this function to recursively find the greatest common divisor:

 private int GreatestCommonDivisor(int i, int j)
 {
 	return (j == 0) ? i : this.GreatestCommonDivisor(j, i % j);
 }

Now our 'Aggregate' method will calculate the smallest positive number that is evenly divisible by all of the numbers from 1 to 20.

This problem was not that enjoyable to me but oh well. I found some great references by Basildon Coder and Functional Fun. From these guys I was able to figure something out. Anyways here it is. Do with it what you will.

Project Euler Problem #4

CodeProject
Moving on along with these Project Euler problems, Problem 4 states this:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

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

This just reeks of a brute force method. But that is fine. I don't think it will be that strenuous.

First we need a function that determines if a computed number is a palindrome. This is what I came up with:

 public bool IsPalindromic(string item)
 {
     return item.SequenceEqual(item.Reverse());
 }

Here we will take in a string representation of a number (or anything really) and use the handy 'SequenceEqual' and 'Reverse' extension methods. Now I actually read somewhere that the 'Reverse' method bogs down performance more than using any other method, but it wasn't enough to affect my performance so I kept it just because it is short and concise.

Now we have to iterate through all the possibilities and check if the given product is a palindrome. There are two ways I can do this:

Lambda:

 return Enumerable.Range(100, 900)
     .Select(i => Enumerable.Range(i, 1000 - i)
         .Where(j => newTools.IsPalindromic((i * j).ToString()))
         .Select(j => i * j)
         .OrderBy(j => j)
         .LastOrDefault())
     .Max();

Or Linq:

 return (from i in Enumerable.Range(100, 900)
         from j in Enumerable.Range(i, 1000 - i)
         let product = i * j
         where newTools.IsPalindromic(product.ToString())
         select product).Max();

Upon first glance the Linq option seems a lot cleaner and easier to read. And it might be. I guess I have no preference because both run just about as fast and return the correct answer, so it just depends on preference.

There ya go. Easy as pie.

Dependency Injection For Dummies (aka Me)

CodeProject
For me, Dependency Injection used to be this wild crazy slick design pattern that I could probably never implement. Well, I was recently on a project for a client that ended up being a perfect situation for a Dependency Injection type implementation. The system was comprised of several assemblies that contained their own implementation. Of course that part is not foreign to me nor should it be to any mediocre developer. However, we ran into the issue of needing to add more of these assemblies in the future and the possibility of removing some. This all needed to happen without re-building/re-deploying the entire solution. Thus.....Dependency Injection. So I taught it to myself.

In the project I was on, we ended up using an Abstract class as our base instead of an Interface. Other than the preference of using Abstract classes, we found that there were some methods that could be common to several assemblies but not every one. So having an Abstract class made sense so that we could include some implementation in the class but also have the option to override it in the assemblies we needed it for.

All this to say, I have decided to play around with Dependency Injection for my Project Euler obsession.



The way I set it up was to have each Problem as its own assembly with a Common assembly and then a User Interface. In the Common assembly, I have added an Abstract class (Problem) that has one method (Answer) that returns a long. Each Problem assembly will inherit from this base Problem class and use that Answer method to return all my answers. Which brings up another reason for Abstract Classes (or Interfaces); they act as contracts for any assembly that inherit from them. This insures that as long as they implement the right method; another assembly could be added and work without any issues. However, it does not stop me from returning the wrong answer because of my problematic logic :). Anyways, my main reason for using Dependency Injection was to basically limit the amount of assemblies I had to reference in my executing assembly. That would have been a mess.

So how does it actually work? Alright, fine. I'll get to that now I guess. Here is a part of my App.Config file. This is where we will add a new assembly once created.

 <?xml version="1.0" encoding="utf-8" ?>
 <configuration>
   <configSections>
     <sectionGroup name="spring">
       <section name="context" type="Spring.Context.Support.ContextHandler, Spring.Core"/>
       <section name="objects" type="Spring.Context.Support.DefaultSectionHandler, Spring.Core" />
     </sectionGroup>
   </configSections>
   <spring>
     <context>
       <resource uri="config://spring/objects"/>
     </context>
     <objects xmlns="http://www.springframework.net">
       <description>All Individual Project Euler Problems</description>
       <object name="Problem001" type="ProjectEuler.Problem001.Problem001, ProjectEuler.Problem001" />
       <object name="Problem002" type="ProjectEuler.Problem002.Problem002, ProjectEuler.Problem002" />
       <object name="Problem003" type="ProjectEuler.Problem003.Problem003, ProjectEuler.Problem003" />
       <object name="Problem004" type="ProjectEuler.Problem004.Problem004, ProjectEuler.Problem004" />
       <object name="Problem005" type="ProjectEuler.Problem005.Problem005, ProjectEuler.Problem005" />
       <object name="Problem006" type="ProjectEuler.Problem006.Problem006, ProjectEuler.Problem006" />
       <object name="Problem007" type="ProjectEuler.Problem007.Problem007, ProjectEuler.Problem007" />
       ............etc etc
     </objects>
   </spring>
 </configuration>

So this will be the only place we have the change something in order for a newly created assembly to work. (Granted that the DLL is in the executing bin folder.)

Here is the code to place in my executing assembly to grab all the configurations in the configuration file:

 using Spring.Context;

 IApplicationContext context = ContextRegistry.GetContext();

Then I can use a for loop to grab the names of all the configured assemblies and use the 'GetObject' method to retrieve the object from the passed assembly name and cast it to the type of our Abstract class (Problem). Then viola, I call my 'Contracting Method' (Answer()) and I can get the answer to any assembly that is placed in the configuration file AND implements the Abstract class without changing my main code or re-compiling.

 foreach(string problem in context.GetObjectDefinitionNames())
 {
     var answer = (Problem)context.GetObject(problem);
     Console.WriteLine(answer.Answer());
 }

I think that just about gives a BASIC walk-through of how I have learned to use Dependency Injection.

Fun stuff.

Project Euler Problem #3

CodeProject
Time for Project Euler Problem 3.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Ah. Prime numbers. This should be fun.

Well first I think we need a fast and efficient way to generate prime numbers. There are many different to accomplish this, but I think making an iterator class to generate them will be best. It will be very similar to the generator we had for Problem Two to generate the Fibonacci sequence.

Here is our generator class:

 public class Primes : IEnumerable<long>
 {
     private List<long> _primes;

     public Primes()
     {
         _primes = new List<long>();
         _primes.Add(2);
     }

     public IEnumerator<long> GetEnumerator()
     {
         Func<long, bool> IsPrime = n => _primes.TakeWhile(i => i <= (long)Math.Sqrt(n)).Count(i => (n % i).Equals(0)).Equals(0);

         yield return 2;
         long next = 3;

         while (true)
         {
             if (IsPrime(next))
             {
                 _primes.Add(next);
                 yield return next;
             }
             next += 2;
         }
     }

     IEnumerator IEnumerable.GetEnumerator()
     {
         return GetEnumerator();
     }
 }

Now that we have our generator, all we have to do is generate primes up to the square root of 600851475143 and then take the largest factor. Easy enough.

 long number = 600851475143;
 return new Primes().TakeWhile(i => i < (long)Math.Sqrt(number)).Where(i => (number % i).Equals(0)).Last();

Project Euler Problem #2

CodeProject
So these Project Euler problems have become quite addictive. I've actually already completed quite a few of them. However, this post will be devoted to problem number dos.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

So this problem is asking us to find all the terms in the Fibonacci sequence that are even and under 4,000,000. Then we have to sum all of those terms.

Alright, first we have to figure out the best way to generate our terms to use. The idea of the sequence is pretty straightforward. We start with two terms, 0 and 1, and then we can use an iterator block to return the second term to an enumerable object. Finally, we can set the second term to itself plus the first and set the first term equal to the new second minus the first.....confusing enough? Yea. Maybe this will help.

 public IEnumerable<long> Fibonacci()
 {
     long a = 0;
     long b = 1;

     while(true)
     {
         yield return b;

         b = a + b;
         a = b - a;
     }
 }

So now we have a Fibonacci generator!

So our final answer can be achieved by using a lambda expression with a 'TakeWhile' extension.

 Tools newTools = new Tools();
 return newTools.Fibonacci().TakeWhile(i => i > 4000000).Where(i => newTools.IsEven(i)).Sum();

I have placed my Fibonacci Generator and the IsEven function in a "Tools" class. This will be my common assembly that will be used in each problems class. I've implemented Dependency Injection on my solution just for the fun of it and will probably go over it in another post sometime. Who knows.

Anyways, for good measure, here is my IsEven function:

 public bool IsEven(long number)
 {
     return (number % 2 == 0);
 }

Project Euler Problem #1

CodeProject
Alright, here we go on Project Euler. Time for the first problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

That doesn't sound quite that hard. Right? The first problem couldn't possibly be hard.

Well let's break it down. All the numbers that are multiples of 3 or 5 under 10 are 3, 5, 6 and 9. Or in other words, 3, 5, 6 and 9 are the only numbers (under 10) that are divisible by 3 or 5 and leave no remainder behind.

So now we have to find all the numbers under 1000 that satisfy the same requirement. And then sum those numbers.

At first thought I suppose it would be easy enough to create a loop that goes through each possibility and adds the number to a list if it passes the divisible test.

Something like this:

 List<int> multiples = new List<int>();

 for (int i = 1; i < 1000; i++)
 {
     if ((i % 3 == 0) || (i % 5 == 0))
     {
         multiples.Add(i);
     }
 }

 return multiples.Sum();

Simple enough right? Well yes and for this simple type of problem, it won't really have any affect on performance. However, I wanted the least amount of lines as possible. I had recently discovered the wonderful world of lambda expressions and I feel that I should use them as often as I can. (for better or for worse)

So here is my solution:

 return Enumerable.Range(1, 999).Where(i => (i % 3).Equals(0) || (i % 5).Equals(0)).Sum();

Ah. Enumerables. By using the 'Range' extension I can retrieve an enumerable list of ints to select from. The 'Where' extension method will ensure that I only retrieve the numbers that are multiples of 3 or 5. And finally, the 'Sum' extension will return the sum of all the numbers left.

Or if we want to get really fancy, we could create a lambda function delegate to make things a bit more readable:

 Func<int, int, bool> IsMultiple = (int i, int j) => (i % j).Equals(0);
 return Enumerable.Range(1, 999).Where(i => IsMultiple(i, 3) || IsMultiple(i, 5)).Sum();

However, the previous solution will do in this case.

Simple and concise. KISS principle in action.