# Monthly Archives: April 2013

# Euler 91 – Right Triangles

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:

… 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)
```