How to optimize this Python script? -

How to optimize this Python script? -

there numerous solutions (a, b, c) integer right triangle perimeter p, , these solutions a+b+c == p , pythagorean theorem applies. writing python script calculate maximum number of solutions possible triangle perimeter <= 1000.

my script correct, takes forever run. i'm sure take more 30 minutes i7 processor, need optimize it. can help me? (this problem on project euler, in case wondering)

def solutions(p): result = [] in range(1, p + 1): b in range(1, p - + 1): c in range(1, p - - b + 1): if + b + c == p , < b , b < c: d = ** 2 e = b ** 2 f = c ** 2 if (d + e == f) or (e + f == d) or (f + d == e): result.append((a, b, c)) homecoming len(result) max_p = 0 max_solutions = 0 p in range(3, 1001): print("processing %d" % p) s = solutions(p) if s > max_solutions: max_solutions = s max_p = p print("%d has %d solutions" % (max_p, max_solutions))

here rewrite of program.

first, precompute squared values. not avoid multiplication, means python won't creating , garbage-collecting objects square values.

next, got rid of loop 3rd side of triangle. 1 time have chosen values a , b there 1 possible value fits criteria a + b + c == 1000 tests one. turns problem approximately o(n^3) approximately o(n^2), vast improvement.

then tried running it. on four-year-old computer finished in 46 seconds, stopped there , here go.

i did google search , found give-and-take of problem; if give-and-take saw correct, programme prints right answer.

upper_bound = 1000 sqr = [i**2 in range(upper_bound+1)] def solutions(p): result = [] in range(1, p - 1): b in range(1, p - a): c = p - (a + b) if < b < c: d = sqr[a] e = sqr[b] f = sqr[c] if (d + e == f) or (e + f == d) or (f + d == e): result.append((a, b, c)) homecoming len(result) max_p = 0 max_solutions = 0 p in range(3, upper_bound+1): print("processing %d" % p) s = solutions(p) if s > max_solutions: max_solutions = s max_p = p print("%d has %d solutions" % (max_p, max_solutions))

edit: here's faster version playing around with. incorporates suggestion @gnibbler in comments.

upper_bound = 1000 sqr = [i**2 in range(upper_bound+1)] def solution(p): count = 0 in range(1, p - 1): b in range(a, p - a): c = p - (a + b) d = sqr[a] e = sqr[b] f = sqr[c] if (d + e == f): count += 1 homecoming count c, p = max((solution(p), p) p in range(3, upper_bound+1)) print("%d has %d solutions" % (p, c))

on computer version takes 31 seconds instead of 46.

the tricky business using max() doesn't create noticeably faster. tried without pre-computing squares , much slower, slow didn't want wait exact time.

python