Project Euler #9 - Pythagorean triplets

Question

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

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
– clutton, Commented Aug 21, 2014 at 1:01
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
– clutton, Commented Aug 21, 2014 at 1:42
Have you looked here codereview.stackexchange.com/questions/58548/…? This can be done with a single loop instead of 3. — Stuart
– Stuart, Commented Aug 21, 2014 at 22:09
This problem can be solved using pencil and paper using Euklids formula. — miracle173
– miracle173, Commented Aug 22, 2014 at 5:48

miracle173 · Accepted Answer · 2014-08-23 06:36:58Z

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$$

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
– Jose Magana, Commented Aug 21, 2014 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
– Jose Magana, Commented Aug 21, 2014 at 4:45
Chose as answer just for that last part, reduces time to 0.115 seconds! — Jose Magana
– Jose Magana, Commented Aug 21, 2014 at 4:50

user50399 · Accepted Answer · 2014-08-21 08:11:45Z

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)

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
– Jose Magana, Commented Aug 21, 2014 at 8:17

Keith · Accepted Answer · 2014-08-21 21:50:33Z

3

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.

edited Aug 21, 2014 at 21:50

answered Aug 21, 2014 at 4:34

Keith

6834 silver badges7 bronze badges

\$\begingroup\$ Yes, I noticed that (forgot to add to original post), and it reduced the time to 0.27 seconds. \$\endgroup\$

Jose Magana
– Jose Magana

2014-08-21 04:37:45 +00:00
Commented Aug 21, 2014 at 4:37
\$\begingroup\$ @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. \$\endgroup\$

clutton
– clutton

2014-08-21 16:48:04 +00:00
Commented Aug 21, 2014 at 16:48
\$\begingroup\$ @clutton. Fair enough - I'll amend my comment. \$\endgroup\$

Keith
– Keith

2014-08-21 21:48:10 +00:00
Commented Aug 21, 2014 at 21:48

Add a comment |

Stack Exchange Network

Project Euler #9 - Pythagorean triplets

3 Answers 3

Naming and expressiveness

Optimization

You must log in to answer this question.

Linked

Hot Network Questions

Project Euler #9 - Pythagorean triplets

3 Answers 3

Naming and expressiveness

Optimization

You must log in to answer this question.

Linked

Related

Hot Network Questions