Project Euler Problem 39 Solution

euler-39.py

import itertools

class PythagoreanTriple(object):
    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c
    def __hash__(self):
        return hash(self._a) * hash(self._b) - hash(self._c)
    def __eq__(self, other):
        return ((self._a == other._a and self._b == other._b) \
            or (self._a == other._b and self._b == other._a)) and self._c == other._c
    def __mul__(self, scalar):
        return PythagoreanTriple(self._a * scalar, self._b * scalar, self._c *scalar)
    def sum(self):
        return self._a + self._b + self._c
    def __str__(self):
        return "({0}, {1}, {2})".format(self._a, self._b, self._c)

def primitive_pythagorean_triples():
    for m in itertools.count(1):
        for n in range(1, m):
            yield PythagoreanTriple(m ** 2 - n ** 2, 2 * m * n, m ** 2 + n ** 2)

best_p = 0
best_count = 0

for p in range(1, 1001):
    solutions = set()
    for triple in primitive_pythagorean_triples():
        for scalar in itertools.count(1):
            scaled = triple * scalar
            perimeter = scaled.sum()
            if perimeter == p:
                solutions.add(scaled)
            elif perimeter > p:
                break
        if triple.sum() > p:
            break
    if len(solutions) > best_count:
        best_count = len(solutions)
        best_p = p

print best_p