Euler Problem 11: Largest Product in a Grid

Euler Problem 11 Definition

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

Euler problem 11

The product of these numbers is 26 × 63 × 78 × 14 = 1,788,696. What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20 by 20 grid?

Solution

The solution applies straightforward vector arithmetic. The product of all verticals is an array of the product of rows 1 to 4, rows 2 to 5 and so on. The code uses a similar logic for the horizontals and the diagonals.

#Read and convert data
square <- readLines("Euler/p011_matrix.txt")
square <- as.numeric(unlist(lapply(square, function(x){strsplit(x, " ")})))
square <- matrix(square, ncol=20)

# Define products
prod.vert <- square[1:17, ] * square[2:18, ] * square[3:19, ] * square[4:20, ]
prod.hori <- square[,1:17] * square[,2:18] * square[,3:19] * square[,4:20]
prod.dia1 <- square[1:17, 1:17] * square[2:18, 2:18] * square[3:19, 3:19] * square[4:20, 4:20]
prod.dia2 <- square[4:20, 1:17] * square[3:19, 2:18] * square[2:18, 3:19] * square[1:17, 4:20]

answer <- max(prod.vert, prod.hori, prod.dia1, prod.dia2)

 

 

 

12 thoughts on “Euler Problem 11: Largest Product in a Grid

  1. Pingback: Euler Problem 11: Largest Product in a Grid - Use-R!Use-R!

  2. Pingback: Euler Problem 11: Largest Product in a Grid – Mubashir Qasim

  3. Pingback: Euler Problem 11: Largest Product in a Grid | A bunch of data

  4. This is an interesting little problem. Although a somewhat trivial exercise after you’ve worked out the important details, I thought it might be interesting to generalize it:

    ####
    set.seed(13)
    cols <- 20 # The number of desired columns in a square matrix
    
    # Create a random sequence of integers cols^2 in length
    # The sequence limit
    lim <- 99
    nums <- as.integer(runif(cols^2, 1, lim))
    
    # Create a square matrix from integer sequence
    square <- matrix(nums, ncol = cols)
    
    # Length of adjacent number thread.
    N <- 4
    
    # Initialize product matrix
    prod.vert <- 1
    prod.hori <- prod.vert
    prod.dia1 <- prod.vert
    prod.dia2 <- prod.vert
    
    # Calculate the iterative product of each product matrix
    for (n in 1:N) {
      prod.vert <- prod.vert * square[n:(cols - N + n), ]
      prod.hori <- prod.hori * square[, n:(cols - N + n)]
      prod.dia1 <- prod.dia1 * square[n:(cols - N + n), n:(cols - N + n)]
      prod.dia2 <- prod.dia2 * square[(N - n + 1):(cols - n + 1), n:(cols - N + n)]
    }
    
    # Find the max product across all matrices
    answer <- max(prod.vert, prod.hori, prod.dia1, prod.dia2)
    print(answer)
    

    It might be worth taking the time to see if an apply function would best replace the loop if the matrix and adjacent number thread were much larger.

  5. Your solution without for-loop:

    answer <- max(c(apply(sapply(1:N, function(n) square[n:(cols - N + n), ]), 1, prod), 
                    apply(sapply(1:N, function(n) square[, n:(cols - N + n)]), 1, prod),
                    apply(sapply(1:N, function(n) square[n:(cols - N + n), n:(cols - N + n)]), 1, prod),
                    apply(sapply(1:N, function(n) square[(N - n + 1):(cols - n + 1), n:(cols - N + n)]), 1, prod)
    ))
    
  6. You do know it’s in the rules not to publish your solutions online? Let other people have the satisfaction of solving the problems, too. Even if you disagree, it’s especially uncool to publish your solutions to Rbloggers.

    I learned so much solving problem XXX so is it okay to publish my solution elsewhere?

    It appears that you have answered your own question. There is nothing quite like that “Aha!” moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.

    • Hi Kiv,

      Thanks for your response and although I understand your concerns, I respectfully disagree.

      Your argument sounds like a magician opposing the exposure of magic trick secrets. Just because people can buy magic books or watch explanations on YouTube does not imply that they will no longer enjoy magic tricks.

      Everybody has a choice to read any of the many blogs on this topic or not to read them. Project Euler provides great challenges, but there is little opportunity to share knowledge about specific languages.

      There are not many participants that use R and I started this blog to promote the use of R and meet like-minded people.

      Some of the comments to my posts provide better and faster solutions to the problem. This shows that both readers and myself learn from these posts.

      Lastly, learning can be accelerated when discussing your thoughts with other people. I lecture marketing to MBA students and facilitate their learning by letting them discuss the issues, not be letting solve their problems by themselves.

      Peter

Leave a Reply