Monday, June 21, 2010

"Project Euler Problem 18" (Not a Spoiler Alert)

I registered at Project Euler some time ago but never seemed to take the time to work on any of the problems.

That changed some months ago when I installed a new version of the IDE that I use (Microsoft Visual Studio 2010). I also became involved in a project that was using some of the latest and greatest programming languages and technologies from Microsoft (C#, WWF, WCF, WPF) and I found using the new languages and development environments to be very nice.

So I gave Project Euler another try and really got hooked. I am not any smarter than I used to be but with a more powerful tool set I really enjoyed working through the problems more.

And I do become stuck on some of the problems and just have to walk away from them and think about them 'in-the-back-ground' before the solutions comes to me. Which so far has happened.

Problem 18 for some reason really fit this category. I think the reason is that the author of the problem says that the "brute-force" solution is possible but if the problem were a bit bigger then it would be impossible, because no computer on the planet could attack a larger version using the brute-force method.

So, I just could not get my arms around it. That phrase in the problem description: "
... requires a clever method! ;o) ...
" probably contributed.

This weekend I was visiting my daughter in Asheville and after explaining the problem at supper I started thinking about it differently and all my new thoughts seemed to be heading in the same direction: "Straight Down The Tube". Everything I thought of was total junk!

Then this morning on the drive back to Raleigh it just hit me. I was sitting at a picnic table at the rest stop just before you get to Winston Salem on I40 and it came to me.

It turns out the solution was a very simple extension of what I had tried at the very first. Simple extension is really not the right way to say it. The correct way is to say a simplification of what I tried at the beginning.

I find over and over that I make things too complicated and the simple way of looking at it usually turns out to be the right way, but for some reason my brain seems determined to make things more complicated than they are.

I was thinking about posting a link to my solution in this blog post but have now decided against it.

The simple solution is so cool and so clean that I cannot bear to share it with anyone who is still looking for it.

When someone shares with me a solution to a problem and the solution is very much simpler than I thought it would be then I feel a sense of loss. I think "Oh man, I could have figured that out!" I do not want to inflict anyone with that feeling.