Posts Tagged ‘prob39’

Problem 39 – Perimeters of Right Triangles

February 17, 2010

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…