project euler problem 174 https projecteuler netproblem174 we shall define a square lamina to be a square outline with a square hole so that the shape possesses vertical and horizontal symmetry given eight tiles it is possible to form a lamina in only one way 3x3 square with a 1x1 hole in the middle however using thirtytwo tiles it is possible to form two distinct laminae if t represents the number of tiles used we shall say that t 8 is type l1 and t 32 is type l2 let nn be the number of t 1000000 such that t is type ln for example n15 832 what is nn for 1 n 10 return the sum of nn for 1 n nlimit solution1000 5 249 solution10000 10 2383 return the sum of n n for 1 n n_limit solution 1000 5 249 solution 10000 10 2383
from collections import defaultdict
from math import ceil, sqrt


def solution(t_limit: int = 1000000, n_limit: int = 10) -> int:
    
    count: defaultdict = defaultdict(int)

    for outer_width in range(3, (t_limit // 4) + 2):
        if outer_width * outer_width > t_limit:
            hole_width_lower_bound = max(
                ceil(sqrt(outer_width * outer_width - t_limit)), 1
            )
        else:
            hole_width_lower_bound = 1

        hole_width_lower_bound += (outer_width - hole_width_lower_bound) % 2

        for hole_width in range(hole_width_lower_bound, outer_width - 1, 2):
            count[outer_width * outer_width - hole_width * hole_width] += 1

    return sum(1 for n in count.values() if 1 <= n <= 10)


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