Alternative solution to Project Euler Problem 15

Contributors
1

Rearranging the problem

My solution uses a little bit of combinatorics.

First of all, the problem says that your starting position is at the top left corner of a square grid of dimension N and you want to reach the bottom right corner.
In order to do so, you are allowed to move a step at a time only down or right.

That’s been said, notice that every route is has 2N steps (N right and N down).
You can rearrange this problem into another one:

  • You have 2N elements to order
  • The 2N elements are divided in two sets of N elements each
  • Elements of the same sets are interchangeble

In mathematical terms, the number of possibilities that you have to order this 2N elements is

Possibilities = (2N)! / (N!)^2

Hope you’ll find it helpful.

Code

Summary 
function factorial(n){
  var factorial = 1;

  for (var i = 1; i <= n; i++){
    factorial *= i;
  }
  return factorial;
}

function latticePaths(gridSize) {

  var nroutes = (factorial(2*gridSize))/( (factorial(gridSize))**2 )

  return nroutes;
}

Challenge: Problem 15: Lattice paths

Link to the challenge:

2

You should use let instead of var since var is a legacy feature. Otherwise, I think we can add this solution to the guide.

4

Hi Jeremy, thanks for the feedback.
I’m new to coding so I’m glad you pointed out what I could improve in my code.
Also, I am new to freecodecamp too and I don’t know how to edit my post because it doesn’t seem to me there’s any edit button: could you tell me how to proceed, please?

5

You don’t need to do anything else for me to post this solution to the guide.

I mention the possible improvements so you can use that information in the future.