Skip to content

Instantly share code, notes, and snippets.

@Fylwind
Created June 13, 2015 05:05
Show Gist options
  • Save Fylwind/0bc36ca767ddb3f1aaf3 to your computer and use it in GitHub Desktop.
Save Fylwind/0bc36ca767ddb3f1aaf3 to your computer and use it in GitHub Desktop.
Solution to Euler problem 67 in Haskell
main :: IO ()
main = do
print (maxTotal [[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]])
print . maxTotal . parseTable =<< readFile "p067_triangle.txt"
maxTotal :: [[Int]] -> Int
maxTotal tree = case triangularFold getMax tree of
[x] -> x
_ -> error "maxTotal: invalid input"
where getMax x t t' = x + max t t'
triangularFold :: (a -> a -> a -> a) -> [[a]] -> [a]
triangularFold _ [] = []
triangularFold _ [r] = r
triangularFold f (r : rs) = [f x t t' | (x, t, t') <- zip3 r ts (tail ts)]
where ts = triangularFold f rs
parseTable :: Read a => String -> [[a]]
parseTable = map ((map read) . words) . lines
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment