blob: 7e27424f5d4d7a2144b7d17316c8aeeff2b5c627 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
-- 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)
|
