Project Euler – Lattice Path (Part 4)

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.

recursive_algorithm_repetitions

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.

recursive_algorithm_memoization

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

One thought on “Project Euler – Lattice Path (Part 4)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s