Another Project Euler problem. This time about adjacent numbers in a grid.
Failed attempt…too complicated
The 20 x 20 grid did look intimidating at first. Therefore I started experimenting with a smaller 5 x 5 grid and three three adjacent numbers.
My idea was to iterate over the grid and create horizontal…
…and diagonal groups…
…calculate the product for each group to find the largest one.
That’s what my first attempt to find the largest product in a row looked like.
I quickly came up with algorithms to create horizontal and vertical groups but struggled with the diagonal ones.
Also I realized that diagonal does not necessarily mean top left to bottom right only. Diagonal can actually go in four directions.
That’s when I scrapped my first attempt, and started looking for another solution.
Again I iterate over the grid. For each number I can go in eight different directions…
- (1) Up: Column number fix, row number – 1
- (2) Diagonal right up: Column number + 1, row number – 1
- (3) Right: Row number fix, column number + 1
- (4) Diagonal right down: Column number + 1, row number + 1
- (5) Down: Column number fix, row number + 1
- (6) Diagonal left down: Column number – 1, row number + 1
- (7) Left: Row number fix, column number – 1
- (8): Diagonal up left: Row number – 1, column number – 1
I only had to be careful not to leave the boundaries of the 20 x 20 grid.
That’s my solution: