Project Euler is an online programming exercise database. There are over 300 problems that relate to number theory, simulations, graph theory, statistics, etc. Given a problem, you have to find a solution that runs in a reasonable amount of time, usually about one minute at most. Some problems range from very simple programming problems (i.e. “find the maximum value”) to much more challenging algorithm design questions (i.e. “write an algorithm to solve this searching problem, knowing that a brute-force approach would take years to finish”).

Although not as formal as the ACM Collegiate Programming Challenges, Project Euler is great fun and presents a ton of good algorithms questions. I just finished problem 18, where you have find the highest-valued path (a sum of nodes) knowing that a path must start from the top and only bottom-adjacent nodes may be traversed. I immediately though of all the graph-theory questions I had during my experience with the programming team here at Penn State, but then realized this isn’t a graph-theory problem: it’s a back-propagation problem! This is where the fun lies in these problems – most simple up-front solutions are grosly under-performant and if your solution is brute-force, it would take years to finish. If you take a few minutes and approach the problem from completely different ways and with different subjects, you can see that there are always optimal solutions! The fun with Project Euler is the practice you get with algorithm creation and implementation.

With problem 18, I realized I shouldn’t be finding the maximum-valued path but instead should focus on this path’s value. It’s a subtle difference, but completely changed my approach to the problem. Instead of looking top-down at the data structure and thinking of paths, I looked bottom-up and saw that one could find the maximum-valued path by “merging” paths backwards. For each node, I looked at the two bottom-adjacent nodes. I then took whichever of the two that were the largest, and add it to this location. I did this for each node, for each row going from the second-to-lowest row all the way to the top. By doing this, I was finding the maximum local values backwards, merging them row-by-row. Once this was done, the top-most node contained the most optimal path’s value.

A brute force approach would of taken about O(2^n) time, but with my approach I only took O(n^2) with a very small constant because of the triangle-shape reducing the number of elements per row at the top! My only issue with Project Euler at this point is that there are no real-time problems, meaning that I would love to apply the algorithms I write against other data-sets. Currently, with the problems I’ve seen, they only provide one set of input, while the ACM Collegiate Programming Challenges force you to submit your code so that it runs against an unknown amount (usually much much more than you might expect) which forced you to write some very tight code. Otherwise, Project Euler is a great site for challenging programming and algorithms problems.