project euler - Problem 15

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?

Using recursive algorithm can solved this problem well. For optimized the running time, I use a matrix to cache previously called functions, as I did in Problem 164.

?View Code RSPLUS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
find.routes.internal <- function(x,y) {
    cnt <- cacheMat[x+1,y+1]
    if (cnt != 0)
        return(cnt)
 
    if (y >0)
        cnt <- cnt+find.routes.internal(x,y-1)
    if (x >0)
        cnt <- cnt+find.routes.internal(x-1,y)
    if (x ==0 && y ==0)
        cnt <- cnt+1
 
    cacheMat[x+1,y+1] <<- cnt
 
    return(cnt)
}
 
find.routes <- function(x,y) {
    cacheMat <- matrix(0, nrow=x+1, ncol=y+1)
    cnt <- find.routes.internal(x,y)
    return(cnt)
}
zv7qrnb

Related Posts

  1. This is a basic problem of combinatorics. The number of routes through a X by Y rectangle is given by C(X+Y,X), where C represents combinations. (http://en.wikipedia.org/wiki/Binomial_coefficient). In R:
    choose(20+20,20)

    When an elegant closed form solution to a problem is presented, use it!

    Reply

  2. project euler-Problem1-50 | YGC United States Unknow Browser Unknow Os - pingback on November 9, 2011 at 3:47 pm
  3. tricky things in R | YGC United States Unknow Browser Unknow Os - pingback on July 10, 2012 at 3:39 pm

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>