matrix.hs

import System.IO
import Data.List.Split
-- import Data.MemoCombinators
-- import Debug.Trace(trace)
import Data.Array

main :: IO()
main = do
	contents <- readFile "matrix_big.txt"
	let matrix = map (map readInt . splitOn ",") . lines $ contents
	let height = length matrix - 1
	let width = minimum (map length matrix) - 1
	print $ shortestPath matrix width height

-- shortestPath :: [[Int]] -> Int -> Int -> Int
-- shortestPath matrix width height = shortestPath' width height
-- 	where
-- 	matrix' = listArray (0, height) $ map (listArray (0, width)) matrix
-- 	shortestPath' = memo2 integral integral shortestPath''
-- 	shortestPath'' 0 0 = matrix' ! 0 ! 0
-- 	shortestPath'' 0 y = matrix' ! 0 ! y + shortestPath' 0 (y-1)
-- 	shortestPath'' x 0 = matrix' ! x ! 0 + shortestPath' (x-1) 0
-- 	shortestPath'' x y = matrix' ! x ! y + min (shortestPath' (x-1) y) (shortestPath' x (y-1))

shortestPath :: [[Int]] -> Int -> Int -> Int
shortestPath matrix width height = shortestPath' width height
	where
	-- matrix' = listArray ((1, 1), (height, width)) [matrix !! x
	matrix' = listArray (0, height) $ map (listArray (0, width)) matrix
	shortestPath' 0 0 = matrix' ! 0 ! 0
	shortestPath' 0 y = matrix' ! 0 ! y + paths ! (0, y-1)
	shortestPath' x 0 = matrix' ! x ! 0 + paths ! (x-1, 0)
	shortestPath' x y = matrix' ! x ! y + min (paths ! (x-1, y)) (paths ! (x, y-1))
	paths = listArray my_bounds [shortestPath' x y | (x, y) <- range my_bounds]
	my_bounds = ((0, 0), (width, height))

readInt :: String -> Int
readInt = read