Problem 15: Lattice paths

*Difficulty: Easy

Problem:

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

How to solve:

First, what is Lattice path?

Lattice Path is a path that lead from one lattice point to the next.

two paths, from the leftmost corner to the rightmost, through a 1×1 lattice

six paths through a 2×2 lattice

Here are the Lattice paths for 4×4 grid

Here is the grid 4×4 in matrix-view

1     1     1     1     1

1     2     3    4     5

1     3     6   10    15

1     4    10  20   35

1     5    15   35   70

What we need is calculating the value at the position (3,3) in the grid, which is 70.

Do we have a formula for this? Like input the size of the grid and instantly got the number of the Lattice paths. The answer is: no, but as you will be showed next, we have a mechanism to calculate the number of the Lattice paths of a nxn size grid, and it runs incredibly fast. (With the brute force approach, this problem cant be solved in an acceptable amount of time with a grid of size just 20, or 30)  .

As you can see :

2 = 1*2, 6 = 3*2, 20 = 10*2, 70 = 35*2

What I want to point out here is from the 0th line, we can compute the value of the next line.

Like this

1     1     1     1     1

Take the second element and multiply it by 2, placing it below the second element:

1     1     1     1     1

——2

Add that to the next element in the above row (2 + 1):

1      1     1     1     1

——2     3

And keep going on going:

1     1     1     1     1

——2     3    4     5

Then work on the third row by taking the second element of the second row (3) and repeating the process, 3 * 2 = 6 hence:

1     1     1     1     1

——2     3    4     5

————6

Take 6 and add it to the next element in the second row (4):

1     1     1     1     1

——2     3    4     5

————6   10

And then take that and add it to the last element in the second row:

1     1     1     1     1

——2     3    4     5

————6   10   15

Continue

1     1     1     1     1

——2     3    4     5

————6   10   15

——————20  35

And finally

1     1     1     1     1

——2     3    4     5

————6   10   15

——————20  35

————————70

This algorithm allows you determine the number of paths from on edge to the other without actually drawing a diagram and manually counting the paths.

Implementation: Java

import java.util.Arrays;

import java.util.LinkedList;

public class Prob15 {

publicstaticvoidmain(String[] args) {

long cur = System.currentTimeMillis();

System.out.println(possibleLatticePath(20));

System.out.println(“Took “ + (System.currentTimeMillis()cur) + ” ms”);

}

privatestaticlongpossibleLatticePath(int size) {

Long[] firstLine = new Long[size+1];

Arrays.fill(firstLine, 1l);

LinkedList<Long> nextLine = new LinkedList<>();

if(firstLine.length==2) return 2;

do{

nextLine = new LinkedList<>();

nextLine.add(firstLine[1]*2);

if(firstLine.length > 2) {

for(int count = 2; count < firstLine.length; ++count) {

nextLine.add(nextLine.getLast() + firstLine[count]);

}

firstLine= new Long[nextLine.size()];

nextLine.toArray(firstLine);

}

}while(nextLine.size()>1);

return nextLine.getLast();

}

}

 

 

Advertisements