Project Euler 91 (via HackerRank): Right triangles with integer coordinates

Question

This is my code to solve HackerRank's version of Project Euler Problem 91: on an N × N grid, find the number of possible right triangles where one vertex is (0, 0) and the other two vertices are integer grid points.

I know its an open challenge, but it is not for any job related coding, and I have also partially solved the problem and just need more optimized code.

#checks if the input 2 points, along with 3rd point as Origin, forms a right angle triangle
def righttri(a,b):
    temp=[]
    temp.append(((a[0]**2)+(a[1]**2))**(1/2))
    temp.append(((b[0]**2)+(b[1]**2))**(1/2))
    temp.append((((a[0]-b[0])**2)+((a[1]-b[1])**2))**(1/2))
    temp=sorted(temp)
    if temp.count(0)>0:
        return False
    elif round((temp[0]**2 )+ (temp[1]**2)) == round(temp[2]**2):
        done.append(sorted([a,b]))
        return True
    else:
        return False

n=int(input())+1
count=0
#coor stores all the 1-increment possible combination of points.
#ex:- for n=2, coor stores [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
#
#done stores the 2points data for all those val which forms right angle with origin
coor,done=[],[]
a,b=0,0
while a<n:
    while b<n:
        coor.append([a,b])
        b+=1
    b=0
    a+=1
for x in coor:
    for y in coor:
        if sorted([x,y]) not in done:
            if righttri(x,y)==True:
                count+=1

print(count)

Now, this code is tested on 9 different test cases, out of which 3 are showing OK. The rest 6 timeout. It means either my algorithm is faulty or I can just implement this algorithm efficiently. I would like to know how this code can be made fast.

Answer 1

• righttri violates the single responsibility principle: it tests the triangle, and (possibly) appends it in the done list. Appending doesn't belong here.

• righttri is surely working too hard: it calculates square roots just to compare them being squared back. Besides losing performance with unnecessary math, it also losing precision. With problems like this it is much better to stay within the integer domain.

• Algorithm inspects every pair of dots on the grid, that is a time complexity is \$O(N^4)\$. That explains the timeouts. There are just too many pairs which do not form the right triangle.

  A better algorithm would enumerate only right triangles via the Euclid's formula.