Project Euler — problem 15

July 18, 2012

(This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers)

The 15th problem in Project Euler.

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 through a 20×20 grid?

Mmm… walk in the grid; it sounds like a problem of graph theory. I’m sure there must be some complicated solution for this. But I’m gonna solve it with the simplest way. To define “pass by one grid in either direction” as one step. Without going back, one needs to 20 steps leftwards and 20 steps downwards to travel from the top left corner to the down right corner.  The problem turns to “how many combinations of leftwards steps with downwards steps”, which is a simple combination problem in mathematics. Thus, the answer is C(20, 40) .

?View Code RSPLUS
result <- choose(40, 20)
cat("The result is:", result, "\n")

To leave a comment for the author, please follow the link and comment on his blog: Tony's bubble universe » R. 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...

Tags: , ,

Comments are closed.