import Data.Matrix
-- 1ª definición
-- =============
maximaSuma1 :: Matrix Int -> Int
maximaSuma1 =
maximum . map sum . caminos1
caminos1 :: Matrix Int -> [[Int]]
caminos1 m =
map reverse (caminos1Aux m (nf,nc))
where nf = nrows m
nc = ncols m
-- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p
-- desde la posición (1,1) hasta la posición x. Por ejemplo,
caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]
caminos1Aux m (1,1) = [[m!(1,1)]]
caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]
caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]
caminos1Aux m (i,j) = [m!(i,j) : xs
| xs <- caminos1Aux m (i,j-1) ++
caminos1Aux m (i-1,j)]
-- 2ª definición
-- =============
maximaSuma2 :: Matrix Int -> Int
maximaSuma2 =
maximum . map sum . caminos2
caminos2 :: Matrix Int -> [[Int]]
caminos2 m =
map reverse (matrizCaminos m ! (nrows m, ncols m))
matrizCaminos :: Matrix Int -> Matrix [[Int]]
matrizCaminos m = q
where
q = matrix (nrows m) (ncols m) f
f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]
f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]
f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]
-- 3ª definicion (por recursión, sin calcular el camino)
-- =====================================================
maximaSuma3 :: Matrix Int -> Int
maximaSuma3 m = maximaSuma3Aux m (nf,nc)
where nf = nrows m
nc = ncols m
-- (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la
-- posición p. Por ejemplo,
-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)
-- 41
-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)
-- 32
-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)
-- 31
maximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int
maximaSuma3Aux m (1,1) = m ! (1,1)
maximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j)
maximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1)
maximaSuma3Aux m (i,j) =
max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j)
-- 4ª solución (mediante programación dinámica)
-- ============================================
maximaSuma4 :: Matrix Int -> Int
maximaSuma4 m = q ! (nf,nc)
where nf = nrows m
nc = ncols m
q = matrizMaximaSuma m
-- (matrizMaximaSuma m) es la matriz donde en cada posición p se
-- encuentra el máxima de las sumas de los caminos desde (1,1) a p en la
-- matriz m. Por ejemplo,
-- λ> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
-- ( 1 7 18 20 )
-- ( 8 20 23 31 )
-- ( 11 28 32 41 )
matrizMaximaSuma :: Matrix Int -> Matrix Int
matrizMaximaSuma m = q
where nf = nrows m
nc = ncols m
q = matrix nf nc f
where f (1,1) = m ! (1,1)
f (1,j) = q ! (1,j-1) + m ! (1,j)
f (i,1) = q ! (i-1,1) + m ! (i,1)
f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j)
-- Comparación de eficiencia
-- =========================
-- λ> maximaSuma1 (fromList 8 8 [1..])
-- 659
-- (0.11 secs, 31,853,136 bytes)
-- λ> maximaSuma1a (fromList 8 8 [1..])
-- 659
-- (0.09 secs, 19,952,640 bytes)
--
-- λ> maximaSuma1 (fromList 10 10 [1..])
-- 1324
-- (2.25 secs, 349,722,744 bytes)
-- λ> maximaSuma2 (fromList 10 10 [1..])
-- 1324
-- (0.76 secs, 151,019,296 bytes)
--
-- λ> maximaSuma2 (fromList 11 11 [1..])
-- 1781
-- (3.02 secs, 545,659,632 bytes)
-- λ> maximaSuma3 (fromList 11 11 [1..])
-- 1781
-- (1.57 secs, 210,124,912 bytes)
--
-- λ> maximaSuma3 (fromList 12 12 [1..])
-- 2333
-- (5.60 secs, 810,739,032 bytes)
-- λ> maximaSuma4 (fromList 12 12 [1..])
-- 2333
-- (0.01 secs, 23,154,776 bytes)