patternpythonMinor
Finding integer lengths for a right triangle with a given perimeter
Viewed 0 times
withperimetergiventriangleforlengthsfindingintegerright
Problem
I'm using Python 3 and have written this code to find the right triangle sides when given the perimeter:
When I run my tests, they work, but the last one seems to be taking a really long time. What would be a good way to improve my code so it executes quicker?
Update
New quicker method combining both answers.
def intRightTri(p):
l = [(a,b,c) for a in range (1, p)
for b in range (1, p)
for c in range (1, p)
if (a**2 + b**2 == c**2) and (a + b + c == p) and (a<=b) and (b<c)]
return lWhen I run my tests, they work, but the last one seems to be taking a really long time. What would be a good way to improve my code so it executes quicker?
import unittest
tc = unittest.TestCase()
tc.assertEqual(intRightTri(100), [])
tc.assertEqual(intRightTri(180), [(18, 80, 82), (30, 72, 78), (45, 60, 75)])
tc.assertEqual(intRightTri(840),
[(40, 399, 401),
(56, 390, 394),
(105, 360, 375),
(120, 350, 370),
(140, 336, 364),
(168, 315, 357),
(210, 280, 350),
(240, 252, 348)])Update
New quicker method combining both answers.
def integer_right_triangles(p):
l = [(a,b,p-a-b) for a in range (1, p)
for b in range (a, p-a)
if (a**2 + b**2 == (p - (a+b))**2 )]
return lSolution
You can improve the performance with a bit of math. Rather than doing this in \$O(p^3)\$ you can do it in in \$O(p)\$.
First remove \$c\$ from the equation:
$$
a + b + c = p\\
c = p - a - b\\
a^2 + b^2 = c^2\\
a^2 + b^2 = (a + b - p)^2$$
After this you can expand the right hand side and simplify.
$$
a^2 + b^2 = (a + b - p)(a + b - p)\\
a^2 + b^2 = a^2 + b^2 + 2ab - 2ap - 2bp + p^2\\
2ab - 2ap - 2bp + p^2 = 0\\
a = \frac{2bp - p^2}{2b - 2p}\\
$$
Which in Python can be:
First remove \$c\$ from the equation:
$$
a + b + c = p\\
c = p - a - b\\
a^2 + b^2 = c^2\\
a^2 + b^2 = (a + b - p)^2$$
After this you can expand the right hand side and simplify.
$$
a^2 + b^2 = (a + b - p)(a + b - p)\\
a^2 + b^2 = a^2 + b^2 + 2ab - 2ap - 2bp + p^2\\
2ab - 2ap - 2bp + p^2 = 0\\
a = \frac{2bp - p^2}{2b - 2p}\\
$$
Which in Python can be:
def _right_a(p):
for b in range(1, p // 2):
a = (2*b*p - p**2) / (2 * (b - p))
if a % 1:
continue
a = int(a)
yield a, b, p - a - b
def int_right_tri(p):
return {tuple(sorted(i)) for i in _right_a(p)}Code Snippets
def _right_a(p):
for b in range(1, p // 2):
a = (2*b*p - p**2) / (2 * (b - p))
if a % 1:
continue
a = int(a)
yield a, b, p - a - b
def int_right_tri(p):
return {tuple(sorted(i)) for i in _right_a(p)}Context
StackExchange Code Review Q#153542, answer score: 5
Revisions (0)
No revisions yet.