Project Euler-Problem 15

Description

From Project Euler:

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

How many routes are there through a 20x20 grid?

Solution

In order find the number of paths that can be taken, we must first observe that we are going to move right 20 times and down 20 times in any valid solution. So our initial answer might be that we simply have to find how many ways we can rearrange 20 rights and 20 downs. Well, the number of possible orderings of 40 elements is 40!. So we might write something like:

class Problem015
  class ::Integer
    def fact
      (1..self).reduce(1, :*)
    end
  end
end

40.fact

There is a problem with this solution, however. What happens if we swap a move down with a move down? We get the exact same ordering of moves. Now, since there are 20 moves down, there are 20! possible ways you can swap a down move with another down move. Similarly there are 20! ways we can swap a right move with another right move. So we need to remove these possibilities from the total number of orderings. So we get:

40.fact / (20.fact * 20.fact)

Now we can generalize this a little bit for any grid mxn.

class Problem015
  def paths_for_grid(m,n)
    (m+n).fact / (m.fact * n.fact)
  end
end

Problem015.new.paths_for_grid(20,20)

The full source and specifications can be seen on github. Next time, what is the sum of the digits of the number 2¹⁰⁰⁰?