Thursday, 2010-03-25

Notes on Project Euler

Project Euler “is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve.” In other words, you need to get down and program to solve the problem[1].

I’ve recently reached Level 3 (solved over 100 problems) and thought I’d share some notes on what I’ve learned.

PE programming is “pure” programming, as in you’re working with algorithms and not systems. There’s rarely anything more complicated than file access needed. In fact, I’d say you need an aptitude for problem solving rather than programming, and the skills needed to solve PE problems are probably not really translatable to real work out in the real world, where you’re dealing with real people and real hardware and networks. To be sure, nowhere on PE do they say that this is programming in the wider sense, as opposed to Computer Science, but you’d be surprised how many CS grads think it does (I’m mocking you, Haskell nerds!).

The typical PE problem looks amenable to brute force, but it pays to research before jumping in. Wikipedia and Mathworld are great resources for a lot of the problems, often explaining the math behind them and sometimes having the algorithms you need.

Spoilers. I find it pretty hard to concentrate on a problem and not want to know the solution, especially when I’m into “grind” mode and just want to level up (this happens a lot with me and puzzle games too). There are plenty of spoilers around for the early problems (the ones that most people manage to solve) but as you move up they get sparser and sparser, and are usually in languages other than your chosen one. Often it’s enough for me to just get a hint. After you’ve solved a problem, you get access to a forum where others discuss their solutions. This can be an eye opener, but there’s no need to share your crappy solution if you don’t want to.

I use Perl. I thought of using PE to learn another language (Python), but finally I felt it was more fun to explore something I’m pretty proficient in than to learn something else. Perl has all the things you need for these problems (so far), especially as there are tons of libraries for specific applications. One of the more useful is Math::Pari, an interface to the Pari suite of numerical algorithms.

Perl is really nice for stuff like string manipulation and set operations. It’s also really easy to build ad-hoc data structures, although the syntax grows hairy really fast.

Python seems very popular among PE participants. Another popular language among the people who bother to post to answer threads is J), and of course Haskell has some vocal devotees.

I find it challenging and fun to work on these problems, and I encourage you to do the same!

[1] although there are some wizards who manage with pencil and paper, at least for the earlier problems.