Project Euler: Problem 15 – Lattice paths

Problem 15:

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

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

Idea:

I recognized this as a Binomial Coefficient problem of given n things, how many ways could you choose m things? I looked briefly but didn’t find any Java classes that implemented this, so I implemented it myself.

String answer = "";

BigInteger value = nChooseM(40,20);
answer = value.toString();

System.out.println("Answer: "+answer);

Note: “nChooseM” is a Mathematical Combination function I implemented using BigInteger. 40 choose 20 because there are 40 moves (20 left, 20 down), in the 20×20 grid. In the example, it would be 4 choose 2 = 6.

Bookmark the permalink.

3 Comments

  1. may I see your “nChooseM” function?

  2. I implemented the factorial method from the Binomial Coefficient link above: n! / (m! (n-m)!)

    Basically it’s: (n & m are int parameters, nFact, mFact, and nMinusM are BigIntegers)

    //n!
    for(int i = n-1; i > 1; i--) {
    nFact = nFact.multiply(BigInteger.valueOf(i));
    }

    //m!
    for(int i = m-1; i > 1; i--) {
    mFact = mFact.multiply(BigInteger.valueOf(i));
    }

    //(n-m)!
    for(int i = (n-m)-1; i > 1; i--) {
    nMinusM = nMinusM.multiply(BigInteger.valueOf(i));
    }

    return nFact.divide(mFact.multiply(nMinusM));

  3. Pingback: Project Euler: Problem 53 – Combinatoric selections - Pursuit of Intellectual Curiosity

Leave a Reply

Your email address will not be published. Required fields are marked *