cplusplus.co.il

Project Euler

Posted on: 14/12/2009

I know I’m a little late, but I’ve only recently discovered the interesting site of projecteuler.net. For anybody not familiar with it, Project Euler is a site offering a vast collection of programming puzzles of mathematical nature for anybody to solve. It has a ranking system for its members, allowing every member to see others’ statistics with solving the offered puzzles. Most of the puzzles are pretty hard, even for the gifted mathematicians among us, and the majority of them can not be solved using brute force methods (it would just take far too long), so usually an efficient algorithm is required. Once you solve a problem you gain access to a forum thread about the problem, its solution, and the various techniques and algorithms other users came up with.

This site got me all hooked up. After three days I can proudly present myself as a Level-1 user (which means I’ve only solved 26 problems out of the total 268 offered on the site) – but I’m planning to work on it and get some more stuff done, so stay tuned! My nickname on the site is romanke, just in case you’re curious.

I would like to present (with no spoilers) two interesting puzzles I’ve solved, that show two very different approaches to solving the questions at hand:

  • Problem 15 – One of my favourite mathematical fields is Combinatorics, so naturally this problem was very fun to solve. It resembles (a little) a topic called Catalan Numbers (the monothonic paths representation in particular), altough the required solution is much simpler. With that said, the most efficient algorithmic solution to this problem took me like  a minute to figure out and implement.
  • Problem 12 – This puzzle, on the other hand, I treated differently. I reached this problem pretty late at night and therefore did not want to spend much time working out an efficient solution. Although sketching a working brute-force solution in Python (this is the place to admit that although I much prefer C++, I used a little Python for the simpler and non-performance-hungry problems on the site) was a no-brainer and took like a few minutes, actually generating the solution with this program was a no-go: after around 30mins of execution on my laptop, a result was no-where to be found. I had two options: either call it a day, or figure out a more algorithmic approach. Or there’s another solution; I figured I may just as well try the same brute-force algorithm in C++! Implementation took around 3minutes and there I was — ready to execute. After roughly 4mins of execution I had the result ready. Success.

As a matter of fact, the help section clearly states that all problems are solvable in under a minute of computation on just about any reasonable hardware and programming language, assuming you have a correct mathematical algorithm. So long run times are just an indication of a wrong approach.. But when it’s reasonable and a correct answer is found, I’m not going to argue 🙂

To wrap it up, the site is extremely addictive and fun (or is it only me?) so I strongly encourage you all to join me (and many others) on Project Euler!

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

%d bloggers like this: