Euler Solution 91

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 91

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is, 0 ≤ x1, y1, x2, y2 ≤ 2.

Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?

Python by Althalus

Runtime: 18ms

Oh gods. I have drawn so many grids and triangles in the past day trying to find these patterns that I never want to see another triangle again.

Methinks you are slowly turning into Maximillian Cohen from Pi... - tom (16/4/2010).

from time import time
start = time()

from fractions import gcd # How nice. Python 2.6 provides a GCD implementation for me!


# right angle in bottom left or bottom right, and the first inverted.
# (0,0), (0,y), (x,0)  (0,0),(x,0),(x,y)  (0,0),(0,y),(x,y)
count = max*max*3

# triangles where long side flush with vertical/horizontal, and triangles that can be formed therein.
for i in range(1,max):
    for j in range(1,i+1):
        if i+j > max: break
        c2 += 2
count += c2

c2 = 0
# triangles not flush with a vertical/horizontal
for i in range(1,max+1,1):
    for j in range(i+1,max+1): # We can take advantage of the fact that x.y is equivelant to y.x to halve the number of loops
        if i == j: continue # covered above.
        c3 = 0
        d = gcd(i,j)
        i1 = i/d
        j1 = j/d
        x,y = i+j1, j-i1
        while x <= max and y >= 0:
            c3 += 2
            x += j1
            y -= i1
        x,y = i-j1, j+i1
        while x >= 0 and y <= max:
            c3 += 2 # See comment above.
            x -= j1
            y += i1
        c2 += c3
count += c2
print count
print time()-start
Personal tools