project euler – Problem 15

[This article was first published on YGC » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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 their blog: YGC » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)