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**2)+(a**2))**(1/2)) temp.append(((b**2)+(b**2))**(1/2)) temp.append((((a-b)**2)+((a-b)**2))**(1/2)) temp=sorted(temp) if temp.count(0)>0: return False elif round((temp**2 )+ (temp**2)) == round(temp**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.