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.

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.

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)