Monthly Archives: April 2013

Euler 91 – Right Triangles

Blue Abstraction - Triangle

I haven’t done a Euler problem for a while. This one caught my eye, so I gave it a try in Haskell. Yeah, yeah, yeah, I know the picture is an equilateral…

My solution started out as a brute force, but then I added a few smarts along the way. First I ran a list comprehension of all possible points, then created a routine with guards to eliminate obvious impossible situations. The angle of each was calculated using the inverse cosine of two vectors:

550px-Find-the-Angle-Between-Two-Vectors-Step-6

… then its was simply a matter of checking for a 90 degree angle && the other two angles equalling 90. Oh yeah and then dividing the total by two because the list comprehension finds doubled matches because of transposed points.

I compiled this routine using GHC with flag -O2 and it runs in about 3 seconds for [0..50]. I’m still waiting for GHCi to finish …


result :: Int -> [Int]
result n = [1 | px <- r, py <- r, qx <- r, qy <- r, isRight px py qx qy ]  
	where
		r = [0..n]

isRight :: Int -> Int -> Int -> Int -> Bool
isRight px py qx qy
	| (px,py) == (0,0) = False
	| (qx,qy) == (0,0) = False
	| (px,py) == (qx,qy) = False
	| ao == 90 && (round (ap + aq)) == 90 = True
	| ap == 90 && (round (ao + aq)) == 90 = True
	| aq == 90 && (round (ao + ap)) == 90 = True
	| otherwise = False
	where
		ao = calcAngle px py qx qy
		ap = 180 + (-1 * (calcAngle px py (qx-px) (qy-py)))
		aq = 180 + (-1 * (calcAngle qx qy (px-qx) (py-qy)))

calcAngle :: Int -> Int -> Int -> Int -> Double
calcAngle px py qx qy = acos (num / denom) * 180 / pi
	where
		num = fInt (px * qx + py * qy)
		denom = (calcMag px py) * (calcMag qx qy)

calcMag :: Int -> Int ->  Double
calcMag x y = sqrt $ fInt (x*x) + fInt (y*y)

fInt = fromIntegral

main = do
	putStrLn "Enter limit:"
	limit <- getLine
	let answer = round $ 0.5 * fInt (length $ result $ read limit)
	putStrLn ("Answer = " ++ show answer)