Project Euler

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 which discusses 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 favorite mathematical fields is Combinatorics, so naturally this problem was very fun to solve. It resembles (a little) a topic called Catalan Numbers (the monotonic paths representation in particular), although the required solution is much simpler.
  • 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 nowhere 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!

Leave a Reply

Your email address will not be published. Required fields are marked *