Thinking in Code vs. Thinking in Mathematics

Lately I’ve been hooked on the web­site Project Euler. Today I sat down to solve Prob­lem #15:

Start­ing in the top left cor­ner of a 2×2 grid, there are 6 routes (with­out back­track­ing) to the bot­tom right cor­ner.
How many routes are there in a 20x20 grid?

My ini­tial thought with this was “recur­sion!” So I sat down and thought about graphs and trees from pre­vi­ous CS classes, debated cre­at­ing a node class with down and right attrib­utes that would be check off after they were used, etc. Then I real­ized that it could be solved with a sin­gle recur­sion func­tion, given two argu­ments (the x and y posi­tion). My ini­tial code in ruby is below:
[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Con­struc­tor
def ini­tial­ize (n = 10)
@n = n.to_i
@paths = 0
end

# Solve it
def solve
node(0,0)
puts “Found #{@paths} paths“
end

# Recur­sively 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 # Ini­tial­ize the pro­gram p = Problem.new ARGV[0] || 2 p.solve end [/sourcecode] This works quite well for small val­ues of n. The issue is that it’s basi­cally a brute force method, and per­for­mance 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 prob­lem. If I approach it from a math­e­mat­i­cal view­point I can see that there is def­i­nitely a pat­tern. To get from the top left to the bot­tom right we must always go N moves to the right, and N moves down­ward. If we call the left and right posi­tions X and the up and down posi­tions Y, and write out our path with X’s and Y’s, we’ll get XXYY for one of the posi­tions of the 2x2 grid. Another would be XYYX. And so forth. What this is rep­re­sent­ing is the per­mu­ta­tion of indis­tin­guish­able objects, where (x+y)!/(x!y!) gives the num­ber of permutations.

My code for this is below:
[source­code language=“ruby”]
#!/usr/bin/env ruby

class Prob­lem

# Cre­ate the object
def ini­tial­ize (n = 10)
@n = n.to_i
@paths = 0
end

# Solve it
def solve
@paths = f(@n*2)/(f(@n)**2)
puts “Found #{@paths} paths“
end

# Fac­to­r­ial of n
def f(n)
n == 1 ? 1 : n*f(n-1)
end

end

if __FILE__ == $0

# Ini­tial­ize the pro­gram
p = Problem.new ARGV[0] || 2
p.solve

end
[/sourcecode]

This is much quicker. It actu­ally is able to cal­cu­late the num­ber of paths for a give NxN grid in just a cou­ple mil­lisec­onds. It takes 5ms for N up to 115. Thats what I call improvement!

The les­son learned from this prob­lem is that even though a “cod­ing” solu­tion is read­ily appar­ent (and works!) it may not nec­es­sar­ily be the best or most effi­cient solu­tion to the prob­lem. That is why a good under­stand­ing of math will never hurt ;)

Leave a Reply