Project Euler — problem 11

July 2, 2012
By

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

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 20×20 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)

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

Tags: , ,

Comments are closed.