TheAlgorithms-Python

1
"""
2
Project Euler Problem 85: https://projecteuler.net/problem=85
3

4
By counting carefully it can be seen that a rectangular grid measuring 3 by 2
5
contains eighteen rectangles.
6

7
Although there exists no rectangular grid that contains exactly two million
8
rectangles, find the area of the grid with the nearest solution.
9

10
Solution:
11

12
    For a grid with side-lengths a and b, the number of rectangles contained in the grid
13
    is [a*(a+1)/2] * [b*(b+1)/2)], which happens to be the product of the a-th and b-th
14
    triangle numbers. So to find the solution grid (a,b), we need to find the two
15
    triangle numbers whose product is closest to two million.
16

17
    Denote these two triangle numbers Ta and Tb. We want their product Ta*Tb to be
18
    as close as possible to 2m. Assuming that the best solution is fairly close to 2m,
19
    We can assume that both Ta and Tb are roughly bounded by 2m. Since Ta = a(a+1)/2,
20
    we can assume that a (and similarly b) are roughly bounded by sqrt(2 * 2m) = 2000.
21
    Since this is a rough bound, to be on the safe side we add 10%. Therefore we start
22
    by generating all the triangle numbers Ta for 1 <= a <= 2200. This can be done
23
    iteratively since the ith triangle number is the sum of 1,2, ... ,i, and so
24
    T(i) = T(i-1) + i.
25

26
    We then search this list of triangle numbers for the two that give a product
27
    closest to our target of two million. Rather than testing every combination of 2
28
    elements of the list, which would find the result in quadratic time, we can find
29
    the best pair in linear time.
30

31
    We iterate through the list of triangle numbers using enumerate() so we have a
32
    and Ta. Since we want Ta * Tb to be as close as possible to 2m, we know that Tb
33
    needs to be roughly 2m / Ta. Using the formula Tb = b*(b+1)/2 as well as the
34
    quadratic formula, we can solve for b:
35
    b is roughly (-1 + sqrt(1 + 8 * 2m / Ta)) / 2.
36

37
    Since the closest integers to this estimate will give product closest to 2m,
38
    we only need to consider the integers above and below. It's then a simple matter
39
    to get the triangle numbers corresponding to those integers, calculate the product
40
    Ta * Tb, compare that product to our target 2m, and keep track of the (a,b) pair
41
    that comes the closest.
42

43

44
Reference: https://en.wikipedia.org/wiki/Triangular_number
45
           https://en.wikipedia.org/wiki/Quadratic_formula
46
"""
47

48
from __future__ import annotations
49

50
from math import ceil, floor, sqrt
51

52

53
def solution(target: int = 2000000) -> int:
54
    """
55
    Find the area of the grid which contains as close to two million rectangles
56
    as possible.
57
    >>> solution(20)
58
    6
59
    >>> solution(2000)
60
    72
61
    >>> solution(2000000000)
62
    86595
63
    """
64
    triangle_numbers: list[int] = [0]
65
    idx: int
66

67
    for idx in range(1, ceil(sqrt(target * 2) * 1.1)):
68
        triangle_numbers.append(triangle_numbers[-1] + idx)
69

70
    # we want this to be as close as possible to target
71
    best_product: int = 0
72
    # the area corresponding to the grid that gives the product closest to target
73
    area: int = 0
74
    # an estimate of b, using the quadratic formula
75
    b_estimate: float
76
    # the largest integer less than b_estimate
77
    b_floor: int
78
    # the largest integer less than b_estimate
79
    b_ceil: int
80
    # the triangle number corresponding to b_floor
81
    triangle_b_first_guess: int
82
    # the triangle number corresponding to b_ceil
83
    triangle_b_second_guess: int
84

85
    for idx_a, triangle_a in enumerate(triangle_numbers[1:], 1):
86
        b_estimate = (-1 + sqrt(1 + 8 * target / triangle_a)) / 2
87
        b_floor = floor(b_estimate)
88
        b_ceil = ceil(b_estimate)
89
        triangle_b_first_guess = triangle_numbers[b_floor]
90
        triangle_b_second_guess = triangle_numbers[b_ceil]
91

92
        if abs(target - triangle_b_first_guess * triangle_a) < abs(
93
            target - best_product
94
        ):
95
            best_product = triangle_b_first_guess * triangle_a
96
            area = idx_a * b_floor
97

98
        if abs(target - triangle_b_second_guess * triangle_a) < abs(
99
            target - best_product
100
        ):
101
            best_product = triangle_b_second_guess * triangle_a
102
            area = idx_a * b_ceil
103

104
    return area
105

106

107
if __name__ == "__main__":
108
    print(f"{solution() = }")
109