Project Euler – Lattice Path (Part 5)

Apart from the recursive solutions an iterative approach for solving the lattice path problem exists as well.

Again full credit goes to Pim Spelier. I really need to find this guy online. So I can properly link to him.

All my work is to translate the given algorithm to Java and dissect it in a way, so that I can understand the solution.

Without further ado…

lattice_path_iterative

The algorithm performs nicely within a blink of a second. Even if I increase the grid size above 20.

So how does it work?

First we create a two-dimensional array. Let’s use the 2×2 grid as an example.
As of long[][] grid = new long[gridHeight + 1][gridWidth + 1] our empty two-dimensional array looks like this:

empty_two_dimensional_array

Actually all grid cells hold an initial value of 0.

Next step is to fill the grid partially:

for (int i = 0; i <= gridHeight; i++) {
    grid[i][0] = 1;
}

for (int j = 0; j <= gridWidth; j++) {
    grid[0][j] = 1;
}

two_dimensional_array_partially_filledAnd then we fill in the remaining slots:

for (int i = 1; i <= gridHeight; i++) {
    for (int j = 1; j <= gridWidth; j++) {
        grid[i][j] = grid[i – 1][j] + grid[i][j – 1];
    }
}

iteration_values

After the first iteration (i = 1 and j = 1) the grid looks like this:

iterative_solution_first_iteration

After the second iteration (i = 1 and j = 2):

iterative_solution_second_iteration

Third iteration (i = 2 and j = 1):

iterative_solution_third_iteration

And finally (i = 2 and j = 2), which is exactly Pascal’s triangle:

iterative_solution_fourth_iteration

There is one more blog post to write about this problem. It will be about a combinatorial solution.

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 )

Connecting to %s