This is how I spent my Monday evening.

 

My blog post Project Euler – Lattice Path (Part 3) showed an implementation of a recursive solution to the lattice path problem in Java.

Major problem was the performance of the algorithm. Working fine for small grids, but lasting forever for the actual 20 x 20 grid.

The recursive nature of the algorithm creates a tree structure.

Unfortunately, already computed values are computed again.

This is no big deal for a 2 x 2 grid. Only the value for (1, 1), which is 2, gets computed twice.

But for a larger grid, walking all tree branches without a sanity check (“Hey, this road looks familiar. I must have been here before.”), the repeated recursive computation causes the performance issue.

For a 3 x 3 grid the values for (2, 1), (1, 1), (2, 2) and (1, 2) have to be computed twice.

For a 4 x 4 grid it’s the values for (3, 1), (2, 1), (1, 1), (3, 2), (2, 2), (1, 2), (3, 3), (2, 3) and (1, 3).

For a 5 x 5 grid…you get the idea.

Pim Spelier introduces an optimization for the recursive algorithm, memoization:

In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. (Wikipedia)

So let’s try caching.

Et voilà, down to 0 seconds from previously 10+ minutes.

While working on another blog post about the lattice path problem my hard drive suffered from a terminal meltdown. Sadly all work lost.

Tomorrow I will take my iMac to my local Apple Store’s Genius Bar.

Meanwhile, while watching Zoolander on TV (what a great movie by the way), I took a quick shot at another Project Euler problem about Pythagorean triplets.

I did some research about constructing Pythagorean triplets, but in the end I had to realize that a very simple brute force solution exists.

There might be better way to do this. But I keep this for another blog post. Typing on my laptop is way less fun and Hansel requires my attention anyway.

I use a 2×2 grid trying to explain a recursive solution to problem number 15.

Credit for the algorithm goes to Pim Spelier, who wrote a nice solution on Project Euler, which is downloadable as PDF once you have submitted the correct answer.

The idea is to assign a tuple to each grid point, starting with (0,0) at the upper left corner. First row (0,0), (0,1), (0,2). Second row (1,0), (1,1)…you get the idea. The bottom right corner is (2,2).

Now we turn the grid into Pascal’s triangle.

Looking at the grid this way, it is now more transparent how the grid actually is a Pascal’s triangle. Starting from the top left corner, only one possible route exists to each grid point marked with a “1”. A grid point marked with a “2” can be reached by taking two different routes. Guess how many routes lead to a grid point with a “3”.

The number of lattice paths through the grid is the sum of the paths to (2,1) and (1,2): 3 + 3 = 6.

You can see that for every tuple containing a 0 like (0,0) or (2.0) and so on, we must return 1.

Every other grid point number is the sum of the two numbers directly above it.

This leads to the following recursive algorithm.

The function is called 11 times.

Unfortunately this solution has a “minor” flaw, which is performance. Calculating the lattice path for a 20×20 grid on my iMac G5 takes over 10 minutes.

A better performing algorithm will be the topic of an upcoming blog post.