TheAlgorithms-Python

1
"""
2
Problem 39: https://projecteuler.net/problem=39
3

4
If p is the perimeter of a right angle triangle with integral length sides,
5
{a,b,c}, there are exactly three solutions for p = 120.
6
{20,48,52}, {24,45,51}, {30,40,50}
7

8
For which value of p ≤ 1000, is the number of solutions maximised?
9
"""
10

11
from __future__ import annotations
12

13
import typing
14
from collections import Counter
15

16

17
def pythagorean_triple(max_perimeter: int) -> typing.Counter[int]:
18
    """
19
    Returns a dictionary with keys as the perimeter of a right angled triangle
20
    and value as the number of corresponding triplets.
21
    >>> pythagorean_triple(15)
22
    Counter({12: 1})
23
    >>> pythagorean_triple(40)
24
    Counter({12: 1, 30: 1, 24: 1, 40: 1, 36: 1})
25
    >>> pythagorean_triple(50)
26
    Counter({12: 1, 30: 1, 24: 1, 40: 1, 36: 1, 48: 1})
27
    """
28
    triplets: typing.Counter[int] = Counter()
29
    for base in range(1, max_perimeter + 1):
30
        for perpendicular in range(base, max_perimeter + 1):
31
            hypotenuse = (base * base + perpendicular * perpendicular) ** 0.5
32
            if hypotenuse == int(hypotenuse):
33
                perimeter = int(base + perpendicular + hypotenuse)
34
                if perimeter > max_perimeter:
35
                    continue
36
                triplets[perimeter] += 1
37
    return triplets
38

39

40
def solution(n: int = 1000) -> int:
41
    """
42
    Returns perimeter with maximum solutions.
43
    >>> solution(100)
44
    90
45
    >>> solution(200)
46
    180
47
    >>> solution(1000)
48
    840
49
    """
50
    triplets = pythagorean_triple(n)
51
    return triplets.most_common(1)[0][0]
52

53

54
if __name__ == "__main__":
55
    print(f"Perimeter {solution()} has maximum solutions")
56