nekedome / project-euler

solutions/problem9.py

"""
Project Euler Problem 9: Special Pythagorean Triplet
====================================================

.. module:: solutions.problem9
   :synopsis: My solution to problem #9.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem9.py>`_.

Problem Statement
#################

A Pythagorean triplet is a set of three natural numbers, :math:`a \\lt b \\lt c`, for which,
    :math:`a^2 + b^2 = c^2`

For example, :math:`3^2 + 4^2 = 9 + 16 = 25 = 5^2`.

There exists exactly one Pythagorean triplet for which :math:`a + b + c = 1000`.

Find the product :math:`abc`.

Solution Discussion
###################

Perform an exhaustive search over :math:`a,b,c` using a few constraints to limit the search space.

.. math::

    &a \\lt b \\lt c \\\\
    &a + b + c = 1000

This is concisely achieved by iterating over the variable :math:`a` first, then determining the range of variable
:math:`b` based on the current value of :math:`a`. Finally, the value of the variable :math:`c` can be simply computed
as:
    :math:`c = 1000 - a - b`

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem9.py
   :language: python
   :lines: 47-
"""


def solve():
    """ Compute the answer to Project Euler's problem #9 """
    triplet_sum = 1000
    min_a, max_a = 1, triplet_sum // 3

The variable min_a seems to be unused.

    for a in range(1, max_a):
        for b in range(a + 1, (triplet_sum - a) // 2):
            c = triplet_sum - a - b
            assert a < b < c, "constraint violated: {} < {} < {}".format(a, b, c)
            if a ** 2 + b ** 2 == c ** 2:
                return a * b * c  # there should only be one solution ...


expected_answer = 31875000