# Project Euler — problem 11

**Tony's bubble universe » 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.

It’s been a while since I solved one Euler problem last time. Has been busy. Now I’m back and continue to solve the next problem, which is to find the maximum. Let’s take a look at the 11th problem:

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?

Well, the idea is simple — the exhaustive search: to calculate all products in either direction, then find the maximum. However, to calculate vertical or horizontal products is kinda easy, while to calculate diagonal products seems not. In my first attempt, I write a helper function to find out the maximum 4-number products in one given numeric vector; then use the `apply()`

function to get the maximum products in each line and each column. But for the diagonal products, it’s a little tricky, because I can’t use `apply()`

here. Thus, I use the `diag()`

to generate the diagonal numeric vectors. At last, I get the maximum products of diagonals and therefore the final maximum product.

^{?}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 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
mat <- as.matrix(read.table("clipboard", sep = " ")) prod.max <- function(x) { # helper funtion to find out the max product n <- length(x) products <- x[1:(n - 3)] * x[2:(n - 2)] * x[3:(n - 1)] * x[4:n] prod.max <- max(products) return(prod.max) } mat.diag <- function(mat, limit) { # helper function to get a list of diag vectors m <- dim(mat)[1] n <- dim(mat)[2] mat.diag <- list() mat.diag[[1]] <- diag(mat) len <- length(mat.diag) for (i in 1:(m - limit)) { mat.diag[[len + i]] <- diag(mat[(1 + i):m, ]) } len <- length(mat.diag) for (j in 1:(n - limit)) { mat.diag[[len + j]] <- diag(mat[, (1 + j):n]) } return(mat.diag) } diag1 <- mat.diag(mat, 4) mat.rev <- mat[, dim(mat)[2]:1] diag2 <- mat.diag(mat.rev, 4) prod.max.diag1 <- sapply(diag1, prod.max) prod.max.diag2 <- sapply(diag2, prod.max) prod.max.vertical <- apply(mat, 2, prod.max) prod.max.horizontal <- apply(mat, 1, prod.max) result <- max(prod.max.diag1, prod.max.diag2, prod.max.vertical, prod.max.horizontal) cat("The result is :", result, "\n") |

For this particular problem, another solution is faster, which utilize the power of R vectorized calculation. I directly calculate the products using matrix mathematics. Code is provided here.

^{?}View Code RSPLUS

1 2 3 4 5 6 |
prod.vertical <- mat[1:17, ] * mat[2:18, ] * mat[3:19, ] * mat[4:20, ] prod.horizontal <- mat[, 1:17] * mat[, 2:18] * mat[, 3:19] * mat[, 4:20] prod.diag1 <- mat[1:17, 1:17] * mat[2:18, 2:18] * mat[3:19, 3:19] * mat[4:20, 4:20] prod.diag2 <- mat[4:20, 1:17] * mat[3:19, 2:18] * mat[2:18, 3:19] * mat[1:17, 4:20] result <- max(prod.vertical, prod.horizontal, prod.diag1, prod.diag2) cat("The result is :", result, "\n") |

I realize that for this kind of problem, some products could be excluded, for instance those with 0′s, 1′s … Even 10′s is not necessarily included, as long as there are bigger adjacent numbers. There should be faster practical ways to calculate the maximum product. And one more thing, what if the problem is “to calculate the maximum product of four adjacent-but-unnecessarily-in-a-row numbers”? It should be fun. (To be continued)

**leave a comment**for the author, please follow the link and comment on their blog:

**Tony's bubble universe » 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.