## Wednesday, 27 July 2011

### Find the maximum product in an array (in all directions)

Question

Really an interesting question again on Project Euler site. Problem #11.

http://projecteuler.net/index.php?section=problems&id=11

Its a 20x20 matrix in which you need to find the maximum product of 4 numbers in all the possible directions you can traverse the array. :) But thank god, the traversal is in straight line. Not zig-zag or random.. :)

Brain storm

I started solving the problem. Initially thought it in very complex way possible as i always do. But its really simple. It’s no optimization problem, sorting problem, anything of that sort. :)

You need to find the adjacent elements of size 4 in up, down, left, right, diagonal directions in an array which when multiplied gives you a max. Even though the question looks complex, it will look like solvable.

Just do the brute force way. You need to first check horizontal 4-by-4 elements. vertical same 4-by-4 elements and then the diagonal.

I got the horizontal and vertical somehow as we take 4 elements on hand and multiply and still move the loop from 0->20.

But for diagonal what is the pattern ?

simple.. diagonal is 2 ways

• from left top to bottom right, move a line
• from right top to bottom left, move a line

But even when you move diagonal, you need to consider 4 elements?.. How, simple..

the pattern is,

(i,j) (i+1, j+1) (i+2, j+2) (i+3,j+3)

for all i,j. Note that we end by 17 itself. :)

the above one is for right top to bottom left

for, left top to bottom right, since we need to ignore elements, we start after 3.

Code

`using namespace std;`
` `
`void main()`
`{`
`    char line[10];`
`    double arr[20][20];`
`    ifstream myfile ("C:\\Works\\cppassignments\\algorithms\\algorithms\\euler-input.txt");`
` `
`    for(int i =0 ; i<20; i++) {`
`        for(int j=0; j<20; j++) {`
`            myfile.getline(line, 10, ' ');`
`            arr[i][j] = atof(line);`
`            cout<<arr[i][j]<<" ";`
`        }`
`        cout<<endl;`
`    }`
` `
`    double max=1;`
`    double prod;`
` `
`    // rows`
`    for(int i=0;i<20; i++) {`
`        for(int j=0; j<17; j++) {`
`            prod = arr[i][j] * arr[i][j+1] * arr[i][j+2] * arr[i][j+3];`
`            if(max < prod) {`
`                max = prod;`
`            }`
`        }`
`    }`
` `
`    // column`
`    for(int j =0; j<20;j++) {`
`        for(int i=0;i<17; i++) {`
`            prod = arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j];`
`            if(max < prod) {`
`                max = prod;`
`            }`
`        }`
`    }`
` `
`    // diagonal right top to bottom left`
`    // exclude 3 from 20 as it never can make it to 4 elements`
`    for(int i=0; i< 17;i++) {`
`        for(int j=0; j<17;j++) {`
`            prod = arr[i][j]*arr[i+1][j+1]*arr[i+2][j+2]*arr[i+3][j+3];`
`            if(max < prod)`
`                max = prod;`
`        }`
`    }`
` `
`    // diagonal left top to right bottom`
`    for(int i=3; i< 20;i++) {`
`        for(int j=0; j<17;j++) {`
`            prod = arr[i][j]*arr[i-1][j+1]*arr[i-2][j+2]*arr[i-3][j+3];`
`            if(max < prod)`
`                max = prod;`
`        }`
`    }`
`}`
• You cannot end by 20. :) be careful even some runtime won’t warn about array overrun, calculation will happen with garbage, your basic type will overflow and you will wrong value. Even for horizontal & vertical we do +3, so must run loop perfectly from 0 to 16
• For math contests like this, always try to use the maximum sized type as possible. :) But do that only if memory of the program is not the winning criteria.. :P
• Thanks to http://duncan99.wordpress.com/2008/10/29/project-euler-problem-11/ for enlightening me about the diagonal flow.