Dynamic programming with Project Euler #18

Question

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 23

NOTE: 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?

Answer 1

Your code is correct, fast, and I'd like to emphasize that you thoroughly include types for your functions, which greatly helps readability.

While arrays offer fast performance, I'd say that in this case operations with indexes and bounds of the arrays cloud the main idea considerably. Therefore I'd offer to use lists and functions native to lists that avoid indexing (the same could be also achieved with arrays, by writing similar functions for them).

The main idea, computing the maximum path lengths for one row, can be then nicely described by zipping:

-- OPT(r,i) = v_ri + max(OPT(r+1,i), OPT(r+1,i+1))
opt :: [Int] -- ^ the current row
 -> [Int] -- ^ the maximum paths from the previous row
 -> [Int]
opt row mxs = zipWith (+) row $ zipWith max mxs (tail mxs)

Then, computing the maximum path can be expressed as folding opt over a list of lists that represents a triangle:

-- Given a triangle (the first row containing `n` elements, the last row 1
-- element), compute the maximum path.
max_path :: [[Int]] -> Int
max_path = head . foldr opt (repeat 0)

where we start with an infinite list of zeros. This is safe, as we always only access a finite number of elements of this starting list.

While the algorithm remains the same, avoiding explicit indexing makes it more readable.

---

Minor notes:

• it's customary to write f . g $ x instead of f $ g $ x to emphasize function composition
• putStrLn . show can be replaced by just print

(I suggest you to try out hlint, which gives many interesting hints how to improve a Haskell program, including the two above.)