-- Maximum path sum II
--
-- Problem 67
-- By starting at the top of the triangle below and moving to adjacent
-- numbers on the row below, the maximum total from top to bottom is 23.
--
-- 3
-- 7 4
-- 2 4 6
-- 8 5 9 3
--
-- That is, 3 + 7 + 4 + 9 = 23.
--
-- Find the maximum total from top to bottom in triangle.txt
-- (right click and 'Save Link/Target As...'), a 15K text file containing a triangle
-- with one-hundred rows.
--
-- NOTE: This is a much more difficult version of Problem 18. It is not possible to
-- try every route to solve this problem, as there are 299 altogether! If
-- you could check one trillion (1012) routes every second it would take over
-- twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)


main = do
    content <- readFile "../data/067_triangle.txt"
    print (head $ maxPath $ parseTriangle content)

-- recursion is beautiful (always)
maxPath :: [[Int]] -> [Int]
maxPath [r] = r
maxPath (top : bottom) = zipWith (+) top (maxRow $ maxPath bottom)

maxRow :: [Int] -> [Int]
maxRow [x] = []
maxRow r = max (head r) (r !! 1) : maxRow (tail r)

parseTriangle :: String -> [[Int]]
parseTriangle str = map (\l -> map (\n -> read n :: Int) (words l)) (lines str)