Lately I’ve been hooked on the website Project Euler. Today I sat down to solve 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 in a 20x20 grid?
My initial thought with this was “recursion!” So I sat down and thought about graphs and trees from previous CS classes, debated creating a node class with down and right attributes that would be check off after they were used, etc. Then I realized that it could be solved with a single recursion function, given two arguments (the x and y position). My initial code in ruby is below:
[sourcecode language=“ruby”]
#!/usr/bin/env ruby
class Problem
# Constructor
def initialize (n = 10)
@n = n.to_i
@paths = 0
end
# Solve it
def solve
node(0,0)
puts “Found [email protected]} paths“
end
# Recursively check for paths
def node(x, y)
# First, are we the end node?
if x == @n && y == @n
@paths += 1
return
end
# Lets go “right“
node(x+1,y) if x < @n
# Lets go “down“
node(x,y+1) if y < @n
end
end
if __FILE__ == $0
# Initialize the program
p = Problem.new ARGV[0] || 2
p.solve
end
[/sourcecode]
This works quite well for small values of n. The issue is that it’s basically a brute force method, and performance of this falls off rather quickly as n increases.
n ms paths
============================
2 5 6
3 5 20
4 5 70
5 6 252
6 8 924
7 17 3432
8 57 12870
9 176 48620
10 668 184756
11 2513 705432
12 9401 2704156
This forced me to take another look at the problem. If I approach it from a mathematical viewpoint I can see that there is definitely a pattern. To get from the top left to the bottom right we must always go N moves to the right, and N moves downward. If we call the left and right positions X and the up and down positions Y, and write out our path with X’s and Y’s, we’ll get XXYY for one of the positions of the 2x2 grid. Another would be XYYX. And so forth. What this is representing is the permutation of indistinguishable objects, where (x+y)!/(x!y!) gives the number of permutations.
My code for this is below:
[sourcecode language=“ruby”]
#!/usr/bin/env ruby
class Problem
# Create the object
def initialize (n = 10)
@n = n.to_i
@paths = 0
end
# Solve it
def solve
@paths = f(@n*2)/(f(@n)**2)
puts “Found [email protected]} paths“
end
# Factorial of n
def f(n)
n == 1 ? 1 : n*f(n-1)
end
end
if __FILE__ == $0
# Initialize the program
p = Problem.new ARGV[0] || 2
p.solve
end
[/sourcecode]
This is much quicker. It actually is able to calculate the number of paths for a give NxN grid in just a couple milliseconds. It takes 5ms for N up to 115. Thats what I call improvement!
The lesson learned from this problem is that even though a “coding” solution is readily apparent (and works!) it may not necessarily be the best or most efficient solution to the problem. That is why a good understanding of math will never hurt ;)