In problem 39 we’re supposed to look at right triangles with integral sides and perimeter no bigger than 100. Specifically, among such perimeters, which has the most representing right triangles?
The given bound seemed small enough that I figure brute force was a good place to start. Loop through lengths for the legs, calculate what the hypotenuse would be, keep track of solutions you find, organized by perimeter, and see who wins. The first (correct) program I wrote ran in 5 seconds. With 5 minutes tweaking the code without much thought, I had the runtime down to half a second. 1000 really isn’t a difficult bound (fwiw though, 10000 takes nearly a minute on my computer). Here’s my code:
def solve(bound):
solns = [0 for n in range(0,bound+1)] # storage
ret = 0 # the winning perimeter
for smleg in xrange(1,bound//2 + 1):
# the larger leg will still be shorter than the hypotenuse
for lgleg in xrange(smleg+1, (bound-smleg)//2 + 1):
hyp = int((smleg**2 + lgleg**2)**.5)
peri = smleg + lgleg + hyp
if peri <= bound and smleg**2 + lgleg**2 == hyp**2:
solns[peri] += 1
if solns[peri] > solns[ret]:
ret = peri
return ret
I have a hard time letting such ugly code go, but I’m pretty sure I’m supposed to be spending my time doing other things anyway, so perhaps I should… move on to problem 40 
Nearing a level-up on Project Euler…
Tags: prob39
