Project Euler/11

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

Solution: https://git.charlesreid1.com/cs/euler/src/master/011

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 data structure

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.

The procedure

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.

The more general principle

The solution to this problem is one that applies to any number of other problems involving finding combinations of local values - if you build a stencil structure, and shift the structure as you move through all of your data, you can implement the calculations once and keep the task simple.

Note that the way that I implemented it was inefficient - I was re-computing many of the combinations of local values that I had computed before. With greater care and more time this could be improved, but the algorithm is quite cheap for the given problem so speed was not an issue.