Python Implementation of Problem 85
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 85
Problem:
By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:
Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.
1"""
2Project Euler Problem 85
3
4Problem:
5
6By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:
7
8.. image:: https://projecteuler.net/resources/images/0085.png
9
10Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with
11the nearest solution.
12"""
13from math import ceil, sqrt
14
15
16def num_rectangles(x: int, y: int) -> int:
17 answer = 0
18 for a in range(1, x + 1):
19 for b in range(1, y + 1):
20 answer += (x - a + 1) * (y - b + 1)
21 return answer
22
23
24def main(tolerance: int = 2) -> int:
25 for x in range(1, ceil(sqrt(2000000))):
26 for y in range(1, x):
27 if abs(num_rectangles(x, y) - 2000000) <= tolerance:
28 return x * y
29 return -1