Really an interesting question again on Project Euler site. Problem #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.. :)
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.
- 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.