Project Euler – Largest product in a grid

Another Project Euler problem. This time about adjacent numbers in a grid.

screenshot_35.png

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.screenshot_36.png

My idea was to iterate over the grid and create horizontal…

screenshot_37.png

…vertical…

screenshot_38.png…and diagonal groups…

screenshot_39.png

…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.

screenshot_54.png

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.

Simple but…

screenshot_56.png

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.

screenshot_57.png

That’s my solution:

screenshot_74.png

screenshot_75.png

screenshot_76.png

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s