Problem 15 : Lattice Paths

Lattice paths

Problem 15

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?

                                                                                                       (https://projecteuler.net/problem=15)

After solving Problem 14, you will be glad that Problem 15 is really easy problem.

..... if you know the mathematical formula to solve it.

Let's look at the picture above. We see four squares connected to each other.

We will change our understanding of the picture: not four squares, but 12 line segments.

 __ __
|__|__|
|__|__|

or

     __        __

|            |            |
     __        __

|            |            |
     __        __

Yes, like this.

We can only go right or down. Which means that we can only make 4 moves total: 2 right and 2 down.

We have 2 r and 2 d, and we will get the total number of different types of combinations possible.

The equation will be totalNumber = 4! / (2! x 2!)

{The number of possible combinations of N terms is always N!.

However, among those N terms, if there are D number of terms which are identical (like 2 r's), then we divide it by D! --> N! / D!}

And the total combination will be 4! / (2! x 2!) = 6, as the problem states.

Aha! Now we can probably finish our solution within 5 lines of code. Or maybe 6.

And as I told you before, using BigInteger becomes really handy this time, as the number gets extremely large when there is combination of 20 + 20 grid lines.

Our ultimate goal is to calculate 40! / (20! x 20!), and here is how to do that using BigInteger:

BigInteger num = BigInteger.ONE;
  
for (int i = 21; i <= 40; i++)
 num = num.multiply(BigInteger.valueOf(i));

for (int i = 2; i <= 20; i++)
 num = num.divide(BigInteger.valueOf(i));

System.out.println(num);

Answer is 137846528820

Execution time is 3.516281 ms

Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem015.java