1
|
|
|
""" |
2
|
|
|
Project Euler Problem 9: Special Pythagorean Triplet |
3
|
|
|
==================================================== |
4
|
|
|
|
5
|
|
|
.. module:: solutions.problem9 |
6
|
|
|
:synopsis: My solution to problem #9. |
7
|
|
|
|
8
|
|
|
The source code for this problem can be |
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem9.py>`_. |
10
|
|
|
|
11
|
|
|
Problem Statement |
12
|
|
|
################# |
13
|
|
|
|
14
|
|
|
A Pythagorean triplet is a set of three natural numbers, :math:`a \\lt b \\lt c`, for which, |
15
|
|
|
:math:`a^2 + b^2 = c^2` |
16
|
|
|
|
17
|
|
|
For example, :math:`3^2 + 4^2 = 9 + 16 = 25 = 5^2`. |
18
|
|
|
|
19
|
|
|
There exists exactly one Pythagorean triplet for which :math:`a + b + c = 1000`. |
20
|
|
|
|
21
|
|
|
Find the product :math:`abc`. |
22
|
|
|
|
23
|
|
|
Solution Discussion |
24
|
|
|
################### |
25
|
|
|
|
26
|
|
|
Perform an exhaustive search over :math:`a,b,c` using a few constraints to limit the search space. |
27
|
|
|
|
28
|
|
|
.. math:: |
29
|
|
|
|
30
|
|
|
&a \\lt b \\lt c \\\\ |
31
|
|
|
&a + b + c = 1000 |
32
|
|
|
|
33
|
|
|
This is concisely achieved by iterating over the variable :math:`a` first, then determining the range of variable |
|
|
|
|
34
|
|
|
:math:`b` based on the current value of :math:`a`. Finally, the value of the variable :math:`c` can be simply computed |
|
|
|
|
35
|
|
|
as: |
36
|
|
|
:math:`c = 1000 - a - b` |
37
|
|
|
|
38
|
|
|
Solution Implementation |
39
|
|
|
####################### |
40
|
|
|
|
41
|
|
|
.. literalinclude:: ../../solutions/problem9.py |
42
|
|
|
:language: python |
43
|
|
|
:lines: 47- |
44
|
|
|
""" |
45
|
|
|
|
46
|
|
|
|
47
|
|
|
def solve(): |
48
|
|
|
""" Compute the answer to Project Euler's problem #9 """ |
49
|
|
|
triplet_sum = 1000 |
50
|
|
|
min_a, max_a = 1, triplet_sum // 3 |
|
|
|
|
51
|
|
|
for a in range(1, max_a): |
|
|
|
|
52
|
|
|
for b in range(a + 1, (triplet_sum - a) // 2): |
|
|
|
|
53
|
|
|
c = triplet_sum - a - b |
|
|
|
|
54
|
|
|
assert a < b < c, "constraint violated: {} < {} < {}".format(a, b, c) |
55
|
|
|
if a ** 2 + b ** 2 == c ** 2: |
56
|
|
|
return a * b * c # there should only be one solution ... |
57
|
|
|
|
58
|
|
|
|
59
|
|
|
expected_answer = 31875000 |
|
|
|
|
60
|
|
|
|
This check looks for lines that are too long. You can specify the maximum line length.