## Monday, November 9, 2009

### Project Euler problem 66 in Haskell

I just got finished programming up Project Euler problem 66 in Haskell. I must say, the solution is extremely elegant. One thing is certain - I never felt this good about programming in any imperative language. Something about framing a solution in as simple and powerful terms as possible just gets the dopamine flowing. Anyway, here is my solution:
`continuedFraction :: Integral a => a -> a -> a -> [a]continuedFraction root num denom = whole : (continuedFraction root newdenom outdenom) where whole = floor (((sqrt \$ fromIntegral root) + (fromIntegral num)) / (fromIntegral denom)) newdenom = (denom * whole) - num outdenom = (root - newdenom*newdenom) `div` denomevaluateConvergent :: Integral a => [a] -> (a, a)evaluateConvergent terms = foldr (\ term (x, y) -> (y + term * x, x)) (1, 0) termsgetConvergents :: Integral a => a -> [(a, a)]getConvergents root = [evaluateConvergent \$ take x \$ continuedFraction root 0 1 | x <- [1..]]getX :: Integral a => a -> agetX d = fst \$ head \$ filter (\ (x, y) -> x*x - d*y*y == 1) \$ getConvergents disPerfectSquare :: Integral a => a -> BoolisPerfectSquare val = val == squareroot * squareroot where squareroot = floor \$ sqrt \$ fromIntegral valargmax :: Ord b => (a -> b) -> [a] -> aargmax func list = fst \$ foldl1 (\ (x1, y1) (x2, y2) -> if y1 > y2 then (x1, y1) else (x2, y2)) \$ zip list (map func list)main = print \$ argmax getX (filter (not . isPerfectSquare) [2..1000])`
And there you have it. Solution runs in about 0.4 seconds on my laptop.