TheAlgorithms-Python

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

4
We shall define a square lamina to be a square outline with a square "hole" so that
5
the shape possesses vertical and horizontal symmetry. For example, using exactly
6
thirty-two square tiles we can form two different square laminae:
7

8
With one-hundred tiles, and not necessarily using all of the tiles at one time, it is
9
possible to form forty-one different square laminae.
10

11
Using up to one million tiles how many different square laminae can be formed?
12
"""
13

14
from math import ceil, sqrt
15

16

17
def solution(limit: int = 1000000) -> int:
18
    """
19
    Return the number of different square laminae that can be formed using up to
20
    one million tiles.
21
    >>> solution(100)
22
    41
23
    """
24
    answer = 0
25

26
    for outer_width in range(3, (limit // 4) + 2):
27
        if outer_width**2 > limit:
28
            hole_width_lower_bound = max(ceil(sqrt(outer_width**2 - limit)), 1)
29
        else:
30
            hole_width_lower_bound = 1
31
        if (outer_width - hole_width_lower_bound) % 2:
32
            hole_width_lower_bound += 1
33

34
        answer += (outer_width - hole_width_lower_bound - 2) // 2 + 1
35

36
    return answer
37

38

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