I just wanted to get an opinion on my dynamic-programming Haskell implementation of the solution to Project Euler problem 18.
The Problem:
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.
$$\begin{array}{ccc} & & & \color{red}{3} \\ & & \color{red}{7} & & 4 \\ & 2 & & \color{red}{4} & & 6 \\ 8 & & 5 & & \color{red}{9} & & 3 \\ \end{array}$$
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67 is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method!
My code:
--Find the maximum total from top to bottom of the triangle below
import Data.Array
import System.Environment (getArgs)
import Control.Applicative ((<$>))
main :: IO()
main = do
path <- head <$> getArgs
triangle <- read_triangle path
putStrLn $ show $ max_path triangle (tri_size triangle) 1
tri_size :: Array Int (Array Int Int) -> Int
tri_size triangle = case bounds triangle of
(s, f) -> (f - s) + 1
--the triangle in this case is a 2d array
--(similar to how pascal's triangle is mathematically described)
--read the tree
read_triangle :: FilePath -> IO (Array Int (Array Int Int))
read_triangle fp = (tri . reverse . lines) <$> readFile fp
where
tri lines = listArray (1, length lines) (map row lines)
row line = listArray (1, length $ nums line) (nums line)
nums = map (read :: String -> Int) . words
--OPT(r,i) = v_ri + max(OPT(r-1,i), OPT(r-1,i+1))
--OPT(N,i) = v_ri
max_path :: Array Int (Array Int Int) -> Int -> Int -> Int
max_path triangle row index = (opt!row)!index
where opt = listArray (1,row) $ (triangle!1 : map f [2..row])
f r = listArray (1,rsize r) $ map (g r) [1..(rsize r)]
g r i = triangle!r!i + max (opt!(r-1)!i) (opt!(r-1)!(i+1))
rsize r = tsize - r + 1
tsize = tri_size triangle
Where can I cut down on repetition/is there anything I could include to make this more concise/readable? Does anything I do show a general misunderstanding of stuff like monads or Haskell's laziness?
