Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

This code works, and I'm trying to figure out if there's a better way to optimize it. As you can see, I've cut down drastically on time just by using numbers that work for a < b < c. Is there any outstanding thing that can reduce the time? It currently takes ~7 seconds.

Problem:

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

$$a^2 + b^2 = c^2$$

For example, \$3^2 + 4^2 = 9 + 16 = 25 = 5^2\$.

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

My code:

import time

start = time.time()

def pythag(a, b, c):
    if a ** 2 + b ** 2 == c ** 2:
        return True
    return False

a = [x for x in range(1, 1000)]

for num in a:
    for dig in range(num, 1000 - num):
        for i in range(dig, 1000 - dig):
            if num + dig + i == 1000:
                if pythag(num, dig, i):
                    print(num, dig, i)
                    print("Product: {}".format(num * dig * i))
                    elapsed = time.time() - start
                    print("Time: {:.5f} seconds".format(elapsed))
                    exit(1)

# 200 375 425
# Product: 31875000
# Time: 7.63648 seconds
share|improve this question
1  
You should take a look at Euclid's Formula, it will be very fast, you can find an explanation at en.wikipedia.org/wiki/Pythagorean_triple –  clutton Aug 21 at 1:01
    
@clutton Just read through that. Thank you very much! –  Jose Magana Aug 21 at 1:26
    
With many of those Euler problems it is just finding the right way to go about it and sometimes the right formula will exist. You should get well under a second, good luck. :) –  clutton Aug 21 at 1:42
    
    
@Jamal Oh good to know. Will remove the best result so far section. Or you already did haha :) –  Jose Magana Aug 21 at 5:35

3 Answers 3

up vote 2 down vote accepted

Without changing your time too much I got these results:

Original run:

>>> 
200 375 425
Product: 31875000
Time: 8.19322 seconds
>>>

New code:

>>> 
200 375 425
Product: 31875000
Time: 0.28517 seconds
>>> 

What I changed:

  • I moved the timing to completely surround the code, instead of when it hit the triplet.
  • I inlined the check for the triplet, as functions are slow in Python
  • Instead of generating a list for num, I used a range object straight up to generate them as needed
  • I eliminated the i loop and condition by using the fact that i will need to be 1000 - num - dig.

Resulting code:

import time

start = time.time()

for num in range(1, 1000):
    for dig in range(num, 1000 - num):
        i = 1000 - num - dig
        if num * num + dig * dig == i * i
            print(num, dig, i)
            print("Product: {}".format(num * dig * i))

elapsed = time.time() - start               
print("Time: {:.5f} seconds".format(elapsed))

Fun fact: the check for a triplet in this case can be reduced to:

num * dig + 1000 * i == 500000

Where did I get these magic numbers you ask? Math. Check it out:

$$(\text{num}+ \text{dig}+ i)^2 = 1000^2$$ Expand: $$\text{num}^2 + \text{dig}^2 + i^2 + 2 \; \text{num} \; \text{dig}+ 2 \; \text{num} \; i + 2 \; \text{dig} \; i = 1000000$$ Use triplet equality: $$2 i^2 + 2 \; \text{num} \; \text{dig}+ 2 \; \text{num} \; i + 2 \; \text{dig} \; i = 1000000$$

Factor:

$$i(\text{num}+ \text{dig}+ i) + \text{num} \; \text{dig}= 500000$$

Use fact that \$\text{num}+ \text{dig}+ i = 1000\$ in our case:

$$\text{num} \; \text{dig}+ 1000 i = 500000$$

share|improve this answer
    
I like the inline version of triplet check. And yes, changing the i to limit it to the only possible value given num and dig greatly reduces the time (as seen in my latest edit). Thanks! –  Jose Magana Aug 21 at 4:43
    
Oops, forgot to show that I also did the same thing with removing the list. This is basically super close to the solution I came up with. –  Jose Magana Aug 21 at 4:45
    
Chose as answer just for that last part, reduces time to 0.115 seconds! –  Jose Magana Aug 21 at 4:50
    
Nice! That is really quick! –  mleyfman Aug 21 at 4:51

Naming and expressiveness

I found your code hard to read, due to issues with naming and general clumsiness in expression.

For example, your pythag() function should be

def is_pythagorean_triplet(a, b, c):
    return a ** 2 + b ** 2 == c ** 2

Next, looking at if num + dig + i == 1000, I have to wonder, how did the a, b, and c in the original problem turn into weird variable names num, dig, and i?

for a in range(1, 1000):
    for b in range(a, 1000 - a):
        for c in range(b, 1000 - b):
            if a + b + c == 1000:
                if is_pythagorean_triple(a, b, c):
                    print(a, b, c)
                    print("Product: {}".format(a * b * c))
                    exit(0)

Now we have an inefficient brute-force solution, but at least it has the virtue of being a very literal translation of the problem into Python.

Note that exit(1) was not appropriate. By convention, a non-zero exit indicates an error.

Optimization

Without drastically changing the strategy, we can still make a major improvement. There is no point in iterating to find c such that a + b + c == 1000, when you can determine it by simple arithmetic.

for a in range(1, 1000):
    for b in range(a, 1000 - a):
        c = 1000 - a - b
        if c < b:
            break
        if is_pythagorean_triple(a, b, c):
            print(a, b, c)
            print("Product: {}".format(a * b * c))
            exit(0)
share|improve this answer
    
Yes, the optimization you have mentioned has already been discussed and yields the same result. Nevertheless, I really appreciate a lot of the things you mentioned in the naming and expressiveness section because I am new to the language and all I've been using is a flake 8 lint for ST2. I should've added the beginner tag that I just learned is on this site (there isn't one on SO). Thank you! –  Jose Magana Aug 21 at 8:17

Whilst for triples, it is easy to find the nice formula, in many problems that will not be so easy.

So, as it demonstrates a basic principle, you should have fewer loops and solve for terms where possible.

In this case, remove the loop over i and simply set i = 1000 - num - dig.

So in fact the extra constraint here is so useful, you may do not require the Euclid, but @clutton's comment suggests that you can use to it go much faster. Note that whilst I can't recall if I used the formula for this problem myself, I'm pretty sure I did find it essential for some other Euler problems.

share|improve this answer
    
Yes, I noticed that (forgot to add to original post), and it reduced the time to 0.27 seconds. –  Jose Magana Aug 21 at 4:37
    
@Keith - I actually used Euclid's formula for the problem when I did it long ago and it solves in about 1ms which I thought was pretty fast compared to other methods I've seen. I wouldn't say that it is not a helpful formula for this particular problem. –  clutton Aug 21 at 16:48
    
@clutton. Fair enough - I'll amend my comment. –  Keith Aug 21 at 21:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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