nekedome / project-euler

solutions/problem39.py

"""
Project Euler Problem 39: Integer Right Triangles
=================================================

.. module:: solutions.problem39
   :synopsis: My solution to problem #39.

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

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

If :math:`p` is the perimeter of a right angle triangle with integral length sides, :math:`{a,b,c}`, there are exactly

This line is too long as per the coding-style (118/100).

three solutions for :math:`p = 120`.

.. math::

    \\lbrace 20,48,52 \\rbrace, \\lbrace 24,45,51 \\rbrace, \\lbrace 30,40,50 \\rbrace

For which value of :math:`p \\le 1000`, is the number of solutions maximised?

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

We are searching for integer solutions :math:`a,b,c` s.t. :math:`a + b + c = p \\le 1000`.

The obvious approach to this problem is to search explicitly through values of :math:`p`, counting the number of integer

This line is too long as per the coding-style (120/100).

solutions :math:`(a,b,c)`. However, this involves many redundant calculations; there are better options.

This line is too long as per the coding-style (104/100).

Let :math:`a,b,c` be the sides of a right-angled triangle
:raw-html:`<br />`
Let :math:`c` be the hypotenuse
:raw-html:`<br />`
Given :math:`a` and :math:`b`, we can solve for :math:`c` using
`Pythagoras' theorem <https://en.wikipedia.org/wiki/Pythagorean_theorem>`_
:raw-html:`<br />`
Now, if :math:`c \\le 1000` and :math:`c \\in \\mathbb{Z}` then we have identified a solution for :math:`p = a + b + c`

This line is too long as per the coding-style (119/100).

We need only search over all :math:`a` and :math:`b`, solving for :math:`c` and filtering out appropriate solutions.

This line is too long as per the coding-style (116/100).

Finally, by ensuring that :math:`b \\ge a`, we avoid double counting the simple transposition
:math:`(a,b,c) \\rightarrow (b,a,c)`.

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

.. literalinclude:: ../../solutions/problem39.py
   :language: python
   :lines: 52-
"""

from math import sqrt

from lib.numbertheory import is_square


def solve():
    """ Compute the answer to Project Euler's problem #39 """
    upper_limit = 1000
    answers = [0] * (upper_limit + 1)
    for a in range(1, upper_limit + 1):

The name a does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        for b in range(a, upper_limit + 1):

The name b does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

            c2 = a * a + b * b

The name c2 does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

            if c2 <= (upper_limit - a - b) * (upper_limit - a - b) and is_square(c2):
                # a + b + c <= upper_limit
                # c <= upper_limit - a - b
                # c^2 <= (upper_limit - a - b)^2
                c = int(sqrt(c2))

The name c does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

                p = a + b + c

The name p does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

                if p <= upper_limit:
                    answers[p] += 1
    answer = max(range(len(answers)), key=lambda _p: answers[_p])  # find arg-max(answers)
    return answer


expected_answer = 840

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).