project euler problem 85 https projecteuler netproblem85 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 solution for a grid with sidelengths a and b the number of rectangles contained in the grid is aa12 bb12 which happens to be the product of the ath and bth triangle numbers so to find the solution grid a b we need to find the two triangle numbers whose product is closest to two million denote these two triangle numbers ta and tb we want their product tatb to be as close as possible to 2m assuming that the best solution is fairly close to 2m we can assume that both ta and tb are roughly bounded by 2m since ta aa12 we can assume that a and similarly b are roughly bounded by sqrt2 2m 2000 since this is a rough bound to be on the safe side we add 10 therefore we start by generating all the triangle numbers ta for 1 a 2200 this can be done iteratively since the ith triangle number is the sum of 1 2 i and so ti ti1 i we then search this list of triangle numbers for the two that give a product closest to our target of two million rather than testing every combination of 2 elements of the list which would find the result in quadratic time we can find the best pair in linear time we iterate through the list of triangle numbers using enumerate so we have a and ta since we want ta tb to be as close as possible to 2m we know that tb needs to be roughly 2m ta using the formula tb bb12 as well as the quadratic formula we can solve for b b is roughly 1 sqrt1 8 2m ta 2 since the closest integers to this estimate will give product closest to 2m we only need to consider the integers above and below it s then a simple matter to get the triangle numbers corresponding to those integers calculate the product ta tb compare that product to our target 2m and keep track of the a b pair that comes the closest reference https en wikipedia orgwikitriangularnumber https en wikipedia orgwikiquadraticformula find the area of the grid which contains as close to two million rectangles as possible solution20 6 solution2000 72 solution2000000000 86595 we want this to be as close as possible to target the area corresponding to the grid that gives the product closest to target an estimate of b using the quadratic formula the largest integer less than bestimate the largest integer less than bestimate the triangle number corresponding to bfloor the triangle number corresponding to bceil find the area of the grid which contains as close to two million rectangles as possible solution 20 6 solution 2000 72 solution 2000000000 86595 we want this to be as close as possible to target the area corresponding to the grid that gives the product closest to target an estimate of b using the quadratic formula the largest integer less than b_estimate the largest integer less than b_estimate the triangle number corresponding to b_floor the triangle number corresponding to b_ceil
from __future__ import annotations

from math import ceil, floor, sqrt


def solution(target: int = 2000000) -> int:
    
    triangle_numbers: list[int] = [0]
    idx: int

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

    
    best_product: int = 0
    
    area: int = 0
    
    b_estimate: float
    
    b_floor: int
    
    b_ceil: int
    
    triangle_b_first_guess: int
    
    triangle_b_second_guess: int

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

        if abs(target - triangle_b_first_guess * triangle_a) < abs(
            target - best_product
        ):
            best_product = triangle_b_first_guess * triangle_a
            area = idx_a * b_floor

        if abs(target - triangle_b_second_guess * triangle_a) < abs(
            target - best_product
        ):
            best_product = triangle_b_second_guess * triangle_a
            area = idx_a * b_ceil

    return area


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