(Hopefully) More Than Just Another Blog

The first problem available on the Project Euler site can be found here, and simply states:

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

I was able to do this in one line of code using three of the newer features in .NET 3.5 chained together.

• System.Linq.Enumerable to produce a list of numbers from 1 to 999.

List<int> list = Enumerable.Range(1, 999);

• A lambda statement to filter the list on all the numbers which are multiples of 3 and 5.

list = list.Where(x => x % 3 == 0 || x % 5 == 0);

• An extension function for a List to sum the items it contains.

int result = list.Sum();

When you chain these three commands together (the first two return a list), it produces a single line of code:

   1: int result = Enumerable.Range(1, 999).Where(x => x % 3 == 0 || x % 5 == 0).Sum();

which executes in about 1ms (based on the .NET Stopwatch class’ timings) on my machine.

Before jumping into any problems, I spent a bit of time working out how a typical problem and solution should be structured.

How should a solution behave?

For Project Euler, all solutions are numbers. But I may need something larger than an integer, which has a maximum value of 2,147,483,647. So I’ve built a container class called EulerResult (not very original, I know). The purpose of this class is to return a single value, the type of value returned may vary depending on the problem being encountered. The value in the container is set by the algorithm, as well as flag to represent the type of the value, and this is returned to the calling class.

The EulerResult class is shown below.

   1: public class EulerResult

   2:     {

   3:  

   4:         private int resultInt;

   5:         private long resultLong;

   6:         private double resultDouble;

   7:         private float resultFloat;

   8:  

   9:         public EulerResult()

  10:         {

  11:             

  12:         }

  13:  

  14:         public Type resultType { get; private set; }

  15:  

  16:         public void setInt(int result)

  17:         {

  18:             resultInt = result;

  19:             resultType = typeof(int);

  20:         }

  21:  

  22:         public int getInt() { return resultInt; }

  23:  

  24:  

  25:         public void setLong(long result)

  26:         {

  27:             resultLong = result;

  28:             resultType = typeof(long);

  29:         }

  30:  

  31:         public long getLong() { return resultLong; }

  32:  

  33:         public void setDouble(double result)

  34:         {

  35:             resultDouble = result;

  36:             resultType = typeof(double);

  37:         }

  38:  

  39:         public double getDouble() { return resultDouble; }

  40:  

  41:         public void setFloat(float result)

  42:         {

  43:             resultFloat = result;

  44:             resultType = typeof(float);

  45:         }

  46:  

  47:         public float getFloat() { return resultFloat; }

  48:  

  49:     }

The console application reads the result out of the EulerResult container like this:

   1: private static void DisplayResult(EulerResult e)

   2:        {

   3:            Type t = e.resultType;

   4:  

   5:            if (t == typeof(int))

   6:                Console.WriteLine("Result is: " + e.getInt());

   7:            else if (t == typeof(long))

   8:                Console.WriteLine("Result is: " + e.getLong());

   9:            // and so on

  10:        }

Personally, I’m not entirely sold on working with types here – it works, but is inflexible (What if I want to work with a Foo type down the track? Or what if Long numbers aren’t long enough for some problems?).

Note 1: I’ve already had a “A-ha” moment with respect to dealing with long numbers. I looked at this issue recently and had to put it aside because working with 50-digit numbers is unfeasible using the core .NET classes. Look out for some revisions to this code once I get a working BFNumber class (Big F’n Number that is).

How does a problem behave?

Rather than having each algorithm work as a single method (Problem.Go() for example), I decided to separate the interface into into three separate methods, each serving a distinct purpose.

   1: public interface IEulerProblem

   2: {

   3:     string name { get; }

   4:     void Setup();

   5:     void PreProcessing();

   6:     EulerResult Execute();

   7:  

   8: }

Setup: this method is called to set up any variables and data required for the algorithm to work. Lists of values, variables tracking values, whatever is required to make the algorithm work should be set here.

PreProcessing (for lack of a better word): some algorithms work on the principles of dynamic programming (break the problem down into several sub-problems which are easier to solve on their own) and this method can be used to do any processing that might be required before we can even think about finding the actual solution.

Execute:  Go forth and find the solution, and return it as an EulerResult object.

Of course, not all solutions will need these methods. I’ll try and stick to this convention, so feel free to shout if I stray from my intended path.

Note 2: I want to include some profiling information in the EulerProblem (so that I can clearly see when an algorithm has improved), which will require a base class that each problem inherits from. I’ll update this once I have the changes implemented and working.

Seeing how I’m easing into my new job, I thought I’d spend some downtime on going back over my time spent on some Project Euler problems. I touched on some of these briefly when I did a VS/.NET introduction lecture a few months ago, but that was relating to using LINQ to query objects.

For those who aren’t familiar with the site, its a collection of math-based problems to solve with whatever tools you see fit. There’s also a forum for people to discuss problems. While they leave it up to you to work out the algorithms, you can submit an answer to see if it is correct. I haven’t gotten involved with the community just yet, so I’m speaking from an outsider’s perspective (actually, I’ve been too busy looking at the algorithms to submit any answers).

Ok, time for the fun stuff.

Backstory

This started out as excuse for me to dabble in C# (coming from a university which did Java for most CS assignments and a previous employer which used VB for its projects), and after a while it became a bit of an odyssey in my spare time to solve as many problems as possible using programming and problem-solving skills.

I want to share my experiences with this site, which has been around since 2001 and last week added some new problems to take it over the 200+ mark. Think of it as a walk-through to mathematical problem-solving using programming tools (I’ll try and stay platform-agnostic, but I can’t make any guarantees at the moment).

Hopefully I can be of some experience considering I did a bit of math at university (more theoretical than applications).

Goals

The goal of this series of entries isn’t to demonstrate C#. As I found while working through the problems, the tools will only take you so far. The rest of the way is up to you and your problem-solving skills. There are some times I’ve been writing code and I’ll have to force myself to stop and go back to the design and either refactor or rewrite.

With each problem, I started out with a naive algorithm (say, brute force solution) and tried to modify the algorithm to improve its performance or exploit some known property associated with the solution. I’m not interested in posting slabs of code here (only when it helps) - I want to show you the how and why involved in order to reach a solution. Of course, If I get an idea about a previous problem at 3am down the track, I’ll go back and try it out and post about it.

As others will attest to, I’m a massive proponent of pen-and-paper when in the early stages of solving a problem. If I can get my hands on a scanner, I’ll include some of my hand-written notes about the problems.

Next

I started off by designing a set of classes to enable algorithms to be built in a consistent manner, and then run within  a console application. I’ll touch on the setup before I dive into any problems, because it helps with testing many problems at once.

If you can’t wait for me, just head over to www.projecteuler.net and have a look at some of the questions.

Apologies to anyone who was refreshing waiting for that second entry. I hope you worked out that I forgot about it. Seeing how its been almost six months between my first and second posts, I think I need to cover a lot of what has happened recently:

• Overloaded my schedule because I was one subject away from graduating.
• Hosted an MSP event introducing .NET and Visual Studio to CS students (pizza was enjoyed by all).
• Graduated from university with two degrees.

And now I’m off to Sydney to start a new job with nsquared solutions. Hopefully I’ll be even quicker with the next entry (actually, its already half-written). Stay tuned.

Hey everyone.

Just in case you've stumbled across this space, my name is Brendan Forster and I'm currently studying at Adelaide University.

I started up this site as a brain dump and tracker for my Microsoft Student Partner involvements, so check back from time to time. I'll also post some tips and tricks for assorted .NET projects and hobby stuff I've been working on.

Regards,

Brendan