www.migniot.com

Haskell strikes again

Sept. 29, 2014, 7:31 a.m.

My first non-trivial code for solving efficiently project euler problem #67

  • Please note that half of the code is only IO boilerplate

  • The solution is only the maxsum function, applied to the triangle, bottom to top

    maxsum (r1:r2:rows) = maxsum ((zipWith (max) (zipWith (+) r2 r1) (zipWith (+) r2 $ tail r1)):rows)
    

Here is the full code

-- Main function
main = do
       text <- readFile "p067_triangle.txt"
       putStrLn ("Solution is "++(show $ maxsum $ reverse $ triangle text))

-- Parse a triangle to integers
triangle :: String -> [[Integer]]
triangle text = map splitints $ lines text
splitints line = map read $ words line

-- Solution
maxsum :: [[Integer]] -> Integer
maxsum [[n]] = n
maxsum (r1:r2:rows) = maxsum ((
                     zipWith (max)
                    (zipWith (+) r2 r1)
                    (zipWith (+) r2 $ tail r1)
                     ):rows)