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.
