3
\$\begingroup\$

I just finished Project Euler 39:

If p is the perimeter of a right angle triangle with integral length sides, {a, b, c} … For which value of p ≤ 1000, is the number of solutions maximised?

I'm pretty satisfied with my solution. I derive the formula for the hypotenuse as follows:

$$\begin{align} a + b + c &= p \tag{Def. perimeter}\\ b + c &= p - a \tag{2}\\ \\ a^2 + b^2 &= c^2 \tag{Pythagorean}\\ a^2 &= c^2 - b^2 \\ a^2 &= (c - b)(c + b) \\ a^2 &= (c - b)(p - a) \tag{from (2)} \\ \frac{a^2}{p - a} &= c - b \tag{7} \\ \\ (c - b) + (c + b) &= \frac{a^2}{p - a} + (p - a) \tag{from (7) and (2)}\\ 2c &= \frac{a^2}{p - a} + \frac{(p - a)^2}{p - a} \\ 2c &= \frac{a^2 + (p - a)^2}{p - a} \\ c &= \frac{a^2 + (p - a)^2}{2\ (p - a)} \end{align}$$

Any optimization would be appreciated.

from timeit import default_timer as timer

start = timer()
def find_pythagorean_triples(perimeter):
    count = 0
    for a in range(3, perimeter / 2 - 1): # triangle inequality
        c = (a**2 + (perimeter - a)**2) / (2*(perimeter - a)) # derived formula
        b = (c**2 - a**2)**0.5
        if b.is_integer() and a + b + c == perimeter:
            count += 1
    return count

def find_most_solutions_upto(limit):
    data = {"most": 0, "num": 0}
    for p in range(limit/2, limit + 1): # scale upwards
        if find_pythagorean_triples(p) > data['most']:
            data['most'] = find_pythagorean_triples(p)
            data['num'] = p
    return data['num']

ans = find_most_solutions_upto(1000)
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)
\$\endgroup\$
4
\$\begingroup\$
  • You are using a dictionary data = {"most": 0, "num": 0} where you could just as well use local variables. The locals would be more readable and faster.
  • The built-in max function is convenient when looking for a maximum. You could write find_most_solutions_upto like this:

    def find_most_solutions_upto(limit):
        return max(xrange(limit/2, limit + 1), key=find_pythagorean_triples)
    
\$\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.