Project Euler/11

Project Euler problem 11: https://projecteuler.net/problem=11

In this problem you are presented with a 20 x 20 grid, and asked to find the maximum product of 4 sequential integers (up, down, left, right, diagonal up/diagonal down).

The way that I thought about this problem was, we were applying a stencil - a moving window, that was looking at a similar sequence of 4 integers, but applied to different parts of the square. Initially, it was my intention to solve this problem using some kind of recursive backtracking - start at the end and work backwards, trying 4-number combinations as I went. However, this is a gross overcomplication. The stencil idea turns out to be a good one to focus on.

To apply a stencil, you can use a sub-array, and walk the sub-array along the main array structure. Copy operations can also be sped up (if talking about primitive data). In this case, the stencil is a 4 x 4 sub-array. We are looking at valid 4-integer products that are covered by the stencil (specifically, we are computing them, and comparing them to a running maximum to see if we have a new 4-integer sequence yielding a larger product).

The moving stencil operation can also be adapted to linked or array structures, and a great deal more optimization can be done to minimize the number of products computed and operations performed.