Loading...
Project Euler 147: Count the number of horizontal, vertical and diagonal rectangles in a rectangular grid
Problem Description
In a 3×2 cross-hatched 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 cross-hatched, 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.
![\frac{n[(2m-n)(4n^2-1)-3]}{6},\:where\: m\geq n](https://s0.wp.com/latex.php?latex=+%5Cfrac%7Bn%5B%282m-n%29%284n%5E2-1%29-3%5D%7D%7B6%7D%2C%5C%3Awhere%5C%3A+m%5Cgeq+n+&bg=ffffff&fg=000&s=2&c=20201002)
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.