Problem 15(Lattice paths)

Problem 15(Lattice paths)

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?

In Python:

#PE14 Longest Collatz sequence
import time
start_time = time.time()
lenChain = []
for num in range(2, pow(10, 6)):
    i = 0
    while num > 1:
        i += 1
        if num % 2 == 0:
            num /= 2
        else:
            num = 3 * num + 1
    lenChain.append(i)
print(lenChain.index(max(lenChain))+2)
print(time.time() - start_time, "seconds")

Run Time: 0.00011491775512695312 seconds

In Java:

//Euler15 Lattice paths

package project_euler;

public class Euler15 {

public static double factorial(int n) {

if (n == 1) {

return 1;

}

else {

return n * factorial(n-1);

}

}

public static void main(String[] args) {

long startTime = System.currentTimeMillis();

double result = 0;

result = factorial(40) / (factorial(20) * factorial(20));

System.out.println((long)result);

long endTime = System.currentTimeMillis();

System.out.println((double)(endTime - startTime) / (double)1000 + "seconds");

}

}

Run time: 0.001seconds

Solution: 137846528820

[from Project Euler: https://projecteuler.net/problem=15]