project euler – Problem 15

November 8, 2011
By

(This article was first published on YGC » R, and kindly contributed to R-bloggers)

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)
}

Related Posts

To leave a comment for the author, please follow the link and comment on his blog: YGC » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.