6
\$\begingroup\$

Project Euler problem 9 says:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

I am a beginner in programming, especially Python. I got the answer for the problem, but how can I optimize it?

a=0
b=a+1
exit=False

#a loop
for x in xrange(1000):
    a+=1
    b=a+1
    c=b+1
    #b loop
    for y in xrange(1000):
        b+=1            
        if(1000-b-a < 0):
            break
        c = 1000-a-b
        if(a**2 + b**2 == c**2):    
                print "The number is ", a*b*c
                x=1000
                exit = True
        else:
                print "A is ", a ,".\n B is ", b, ".\n  C is ",c,"."
        if exit:
                break
    if exit:
            break
\$\endgroup\$
  • \$\begingroup\$ Any optimizations that you could make would likely be in removing the O(n^2) complexity. \$\endgroup\$ – James Mills Dec 15 '13 at 7:01
  • 3
    \$\begingroup\$ This is Project Euler Problem 9. \$\endgroup\$ – 200_success Dec 15 '13 at 7:58
4
\$\begingroup\$

Well, you got the answer, but your code could be tidier. The main weaknesses I see are:

  • Too many variables: The problem calls for numbers a, b, and c. Introducing variables x and y needlessly complicates the code. It's always the case that a = x + 1, so x is redundant. Then, with y (but not really using y), you loop up to 1000 times with b starting from a + 1.

    Your loop structure can be distilled down to…

    for a in xrange(1, 1001):
        for b in xrange(a + 1, a + 1001):
            if a + b > 1000:
                break
            c = 1000 - a - b
            # etc.
    

    However, the if-break could still be improved upon — see below.

  • Using variables for flow control: It's cumbersome to set an exit flag, then have code elsewhere inspect the flag. There are more assertive techniques to go where you want to go immediately. You want to break out from a nested loop, so search Stack Overflow and read this advice.

As previously mentioned, there is an even better way to enumerate possibilities for a, b, and c such that their sum is always 1000. That way, you don't need the if-break in your code.

def euler9():
    # Ensure a < c
    for c in xrange(2, 1000):
        for a in xrange(1, c):
            # Ensure a + b + c == 1000.  Since a is counting up, the first
            # answer we find should have a <= b.
            b = 1000 - c - a

            # Ensure Pythagorean triple
            if a**2 + b**2 == c**2:
                print("a = %d, b = %d, c = %d.  abc = %d" % (a, b, c, a * b * c))
                return

euler9()

Alternatively:

def euler9():
    for a in xrange(1, 1000):
        for b in xrange(a + 1, 1000 - a):
            # Ensure a + b + c == 1000.  Since b is counting up, the first
            # answer we find should have b <= c.
            c = 1000 - a - b
            # etc.
\$\endgroup\$
5
\$\begingroup\$

Here are some changes I would do in your code:

  1. Since you already have two variables x and y from the loop, you don't need a and b. Get the 3 numbers as - x, y, and 1000 - x - y, and use them.

  2. You might well possibly be checking the values same pythagorean triplets twice. Once with x, y, and 1000 - x - y, and then with y, x, 1000 - y - x. For example, when x takes 2 and y takes 3, then you don't want to check this again for x = 3 and y = 2. This might happen, as your inner loop is running from the beginning every time. You can avoid this by iterating from x to 1000.

  3. No need of exit boolean variable. Put those loops inside some function, and return as soon as the result is found.

Modified Code:

def specialPythagoreanTriplet(s):

    for a in xrange(s):
        for b in xrange(a, s):
            c = s - a - b;
            if a**2 + b**2 = c**2:
                return (a, b, c)

In addition to all that, you don't really need to iterate till 1000 for values of a and b. The maximum value that a could take should be much less than 1000. Let's find out.

You have:

a + b + c = 1000, and
a < b < c

Replace b and c with a, we get:

a + a + a < 1000
3a < 1000
a < 333

Similarly, you can find out the threshold for b, I'm leaving it for you:

for a in xrange(s / 3):
    for b in xrange(a + 1, s):  # Change `s` to someother value
        # Same as previous code.
\$\endgroup\$
2
\$\begingroup\$

I used information here and it seems to solve fairly quickly:

Euclid's Formula

a = m^2 - n^2 , b = 2mn , c = m^2 + n^2 

For math related questions, using the correct formula can save quite a lot of computation.

In regard to your current code, you can probably avoid setting the a, b, c in the outer loop, and b in the inner loop if you change your 'for x in xrange' to 'for a in xrange' and your 'for y in xrange' to 'for b in xrange'. This is a pretty common way to advance those values and saves quite a bit of moving the numbers in python. Less work done is faster. :)

Using the Euler formula above is likely much faster though. You may want to consider how you would cycle through values m and n and calculate a,b,c.

\$\endgroup\$
  • \$\begingroup\$ True, but it's only faster if you disregard the time to write and debug your program. A computer can easily iterate 1000 x 1000 times in less than one second. \$\endgroup\$ – 200_success Dec 16 '13 at 9:23
2
\$\begingroup\$

I think I have the fastest solution:

print "The number is 31875000"

In all seriousness, you have several constraints you can throw in. WLOG, a <= b. We also know a,b < c. We know that a + b + c = 1000. So a < 334. If a = 100, then b < 450.

I will also say that since this is a Project Euler question you can probably find some very clever solutions on the Project Euler thread. I imagine this problem can be done pretty quickly by hand with the right maths.

\$\endgroup\$
  • \$\begingroup\$ lol, I know the answer and my code works. I just want an optimized version. Your suggestion will also be taken. Thanks \$\endgroup\$ – Dark Mirror Dec 15 '13 at 6:49

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.