Project Euler 147: Count the number of horizontal, vertical and diagonal rectangles in a rectangular grid
Problem Description
In a 3×2 crosshatched grid, a total of 37 different rectangles could be situated within that grid as indicated in the sketch.
There are 5 grids smaller than 3×2, vertical and horizontal dimensions being important, i.e. 1×1, 2×1, 3×1, 1×2 and 2×2. If each of them is crosshatched, the following number of different rectangles could be situated within those smaller grids:
1×1: 1
2×1: 4
3×1: 8
1×2: 4
2×2: 18
Adding those to the 37 of the 3×2 grid, a total of 72 different rectangles could be situated within 3×2 and smaller grids.
How many different rectangles could be situated within 47×43 and smaller grids?
Analysis
1. Count the number of horizontal and vertical rectangles in the grid.
2. Count the number of diagonal rectangles in the grid. Since m ≥ n, you can safely exchange m and n if this isn’t already the case.
3. Add the two together for a total for each iteration of m and n. The sum of this series is the answer.
Example: for a 2×3 grid you have 18 horizontal and vertical rectangles and 19 diagonal rectangles for a total of 37.
Project Euler 147 Solution
Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 147 Solution Python 2.7 source.
Afterthoughts

No afterthoughts yet.
Discussion
No comments yet.