Euler Problem 11 – Largest Product in a grid.

Largest product in a grid

Problem 11

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

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

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

This by far has been the most challenging problem. Took lot of time to solve and really had to think hard to get to the solution.

It was clear from the problem that we need to use rollapply like we used in the problem 8 . We need to use it once for rows and once for columns. The other option remaining was diagonal. In R, we could extract diagonal of matrices using a function called diag().

     [,1] [,2] [,3]

[1,]    1    4    7

[2,]    2    5    8

[3,]    3    6    9

So for above matrix when you do diag(mat) it returns 1, 5 , 9. So I can use rollapply on this diagonal elements as well.

My plan was to get 3 max values :

1) a – max for row-wise products

2) b – max for column-wise products

3) c- max for diagonal-wise products

and then max of these 3 values would be the answer.

However, it turns out the answer which I got wasn’t the right answer. I cross checked the commands which I was running on a smaller matrix and it did give the right answer.

Upon closely looking at the question again, I realised the example which was given with values 26, 63, 78 and 14 aren’t the elements of primary diagonals. So we had to check the product for every diagonal in the matrix. So for the same matrix as above

     [,1] [,2] [,3]

[1,]    1    4    7

[2,]    2    5    8

[3,]    3    6    9

Along with 1, 5 and 9 we also need to check the product for 2, 6 and 4, 8. Getting the primary diagonal was easy with diag in R but how can I get all the diagonals? While trying to search for it I came across an excellent answer on Stackoverflow which returns a list of all the diagonals.

j = row(temp) – col(temp)

This assigned same number to all the diagonal element which we can then pass to our split function which splits the matrix into diagonals.

So with this I get a list of all diagonals elements, we remove those lists elements with length less than 4 (as we need four consecutive elements) and then use rollapply on each list and get the max value from that list which would be our c now.  Surprisingly, even the answer which I got from this wasn’t the right answer. This was strange as I had checked my output on a smaller matrix and it worked.  I had covered all the cases (at least I thought so, but definitely I was missing something). There was no calculation error as well.

After lots and lots of thinking about which case I was missing. I finally found out.

     [,1] [,2] [,3]
[1,]    1    4    7

[2,]    2    5    8

[3,]    3    6    9

This was my matrix. For window = 2

a = rowwise maximum product (1*4, 4*7, 5*8, 6*9 etc…)

b = columnwise maximum product (1*2, 2*3, 4*5, 8*9 etc…)

c = diagonal wise maximum product (1 * 5, 5*9, 2*6, 4*8 )

and the case which i was missing was

d = anti-diagonal (or whatever it is called) wise product (7*5, 5*3, 4*2, 8*6)

Sigh!! That was tricky and interesting. The tricky part was only to figure out this anti diagonal thing. Once I fugured that out there was nothing challenging as such.

Those anti diagonal patterns could be formed easily by using

j = row(temp) + col(temp)

and then split the matrix accordingly. Got an output and tada…that was the correct answer!

Here’s the code

library(zoo)
getMaxProduct = function(mat, windowSize) {
#check for column
a = max(rollapply(mat, windowSize, prod))
#check for row
b = max(rollapply(t(mat), windowSize, prod))
#check for diagonal
# create an indicator for all diagonals in the matrix
d = row(mat) - col(mat)
k = row(mat) + col(mat)
# use split to group on these values
diags1 = split(mat, d)
diags2 = split(mat, k)
prodList1 = unlist(lapply(diags1[lapply(diags1, length) > (windowSize - 1)], function(x) rollapply(x, windowSize, prod)), use.names = FALSE)
prodList2 = unlist(lapply(diags2[lapply(diags2, length) > (windowSize - 1)], function(x) rollapply(x, windowSize, prod)), use.names = FALSE)
c = max(prodList1)
d = max(prodList2)
max(a, b, c, d)
}

getMaxProduct(mat, 4)
[1] 70600674

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s