3
\$\begingroup\$

I'm using Python 3 and have written this code to find the right triangle sides when given the perimeter:

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 l

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?

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 l
\$\endgroup\$
  • 3
    \$\begingroup\$ Are you working on Project Euler problem 39? \$\endgroup\$ – Gareth Rees Jan 25 '17 at 7:57
  • \$\begingroup\$ I was and I feel dirty for having looked at this thread, but I did learn from @Peilonrayz's solution, especially making it a list comprehension (probably one of the ugliest I've ever seen!). \$\endgroup\$ – horcle_buzz Dec 14 '17 at 16:32
4
\$\begingroup\$

This feels like the sort of thing where you can find a clever algorithm to make it super-efficient. That's not my strength, so I'm just going to point out some simple things you can do to make things faster.

First, I'm going to rewrite it without a list-comprehension to make it easier to think about:

def intRightTri(p):
    triples = []
    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):
                    triples.append((a, b, c))           
    return triples

And that inner comparison happens p^3 times.

You have some constraints in your check that you can get rid of by setting things up a little more carefully.

def intRightTri(p):
    triples = []
    for a in range(1, p):
        for b in range(a, p):          #ensure b >= a
            for c in range(b+1, p):    #ensure c > b
                if (a**2 + b**2 == c**2) and (a + b + c == p):
                    triples.append((a, b, c))           
    return triples

This is a little better. But then after we have our a and b, there is only one possible value for c to satisfy a + b + c == p, so you don't even need that last nested loop.

def intRightTri(p):
    triples = []
    for a in range(1, p):
        for b in range(a, p-a):     
            c = p - (a + b)
            if a**2 + b**2 == c**2:
                 triples.append((a, b, c)) 
            elif a**2 + b**2 > c**2:
                # As we continue our innermost loop, the left side 
                # gets bigger, right gets smaller, so we're done here
                break    

    return triples
\$\endgroup\$
  • \$\begingroup\$ You could save a2 = a**2 to avoid computing it every time. \$\endgroup\$ – Graipher Jan 25 '17 at 7:41
  • 1
    \$\begingroup\$ a==b will not yield a pythogorean triple. Because square root of two is not a rational number. - Ie. you can have b in range(a+1,p-a). Also because c>b>a you can have b in range(a+1,p-2*a) - although this last improvement will not matter because you will hit the break instruction before you hit the end of either loop. In fact the code might be faster by doing b in range (a+1,p) - because you avoid calculating p-a \$\endgroup\$ – Taemyr Jan 25 '17 at 9:05
5
\$\begingroup\$

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:

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)}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.