Sunday, November 9, 2008

Problem Solving With Project Euler

Problem Solving

I think most people would agree that problem solving comes in pretty handy when it comes to software development. Knowing what you can infer given a set of data or exactly what you need to provide a feature is key in coming up with a lean solution.


It was a Data Structures and Algorithms T.A. who first convinced me the value of puzzles when it comes to programming. We were trying to come up with a solution for Instant Insanity when a fellow student asked if there was really any value in knowing a solution for a children's game.

The T.A. then made the excellent point that when you brush away all the noise from most business problem you essentially end up with a simple (albeit potentially dull) puzzle. In fact being able to solve Instant Insanity puts you in a great position to solve a lot of constraint based scheduling problems, a family of concerns that many businesses (ie. airlines) can use to save millions of dollars a year. Being able to solve puzzles algorithmically is analogous to solving business problems in code.

Sharpening the Saw

euler_mainSo where do you go about getting good puzzles to solve? A coworker recently pointed me to a site called Project Euler (as in the mathematician). The site boasts a sizable collection of math based problems that are meant to be solved programatically. Once you come up with an answer you can submit it and get immediate feedback. The problems are ranked in terms of difficulty and some of them are guaranteed to get you fact, that's the point!

Once you've solved a problem you also get access to a forum where other developers have solved the problem and discuss their solutions. For myself the merits have been three fold:

  1. You're forced to repeatedly go through the motions of problem decomposition, doing this exercises mental problem solving muscles.
  2. Once you come up with an answer, you can compare your approach to that of thousands of other developers and get some perspective on different approaches.
  3. It's fun.

Consider the following problem (Problem 9). It's the 9th problem in the site's inventory of 216 problems. While finding the solution is far from impossible (in fact 19885 people have already solved it at time or writing) it will get definitely test your problem decomposition skills.

A Pythagorean triplet is a set of three natural numbers, a b c, for which, a2 + b2 = c2.
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Trust me that finding the answer is a journey worth taking. It involves both programming and problem solving, is there any better way to learn?


1 comment:

Norris Ward said...

For me programming is the only way to tackle with this problem to get a solution in an easy way for any numbers. Project Euler is an interesting way to enhance your programming techniques.