Project Euler

Project Euler is an internet-based mathematical and programming challenge that has been running for the last ten years. Problems set on the site range from incredibly easy to (mostly) very difficult. I’m currently at “Level 3”, having solved 110 of the problems, including some of the more recent difficult ones.

It’s a bit tricky to write about this little hobby of mine as one of the conditions of taking part is that one doesn’t give away the answers.

I think that’s pretty fair as it has made me try a lot harder to solve the problems where answers were unavailable.

This is an image from Problem 331 - Cross Flips. I’m the 54th person to have solved it and quite proud of the fact! Although the piece of code I finished with (in my language of choice for speed and efficiency, C++) is relatively small, I wrote a lot more along the road to solving this problem.

A friend suggested to me that surely using a computer to solve this kind of problem is “cheating”? You just tell it what to do and it does it. Well, yes, you do tell it what to do but that is the challenge. Coming up with the correct instructions to solve a problem such as the one given is difficult.

Generally it’s not too tricky to come up with a program that will solve small examples of the problem but the site usually requires solutions for problem sizes that can’t be handled by a simple naive solution.

For example, the Cross Flips puzzle asks for solutions up to and including a board size that is 2,147,483,617 disks across. That means that in total the board will have 2,147,483,617 times 2,147,483,617 disks which is 4,611,685,885,283,402,689 disks altogether.

Although a modern computer can do a few million calculations per second, that’s nowhere near enough to produce a result in the space of a lifetime if you want to do a calculation for every disk on the board. Hence a clever solution is required!

I’d like to think my answer to the problem is reasonably smart, although some of the other people who solved this problem managed to do so with programs that ran a lot faster than mine. One of the nice things about getting the answer is that this gives access to a forum on the Project Euler site where you can discuss your solution and post your answer.

So, what is the answer? If you want to see what I came up with you’ll just have to work it out for yourself then check out my code in the Project Euler forum. Sorry!