Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
( 1 6 11 2 )
( 7 12 3 8 )
( 3 8 4 9 ) |
( 1 6 11 2 )
( 7 12 3 8 )
( 3 8 4 9 )
moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:
1, 7, 3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9 |
1, 7, 3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9
Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El camino de máxima suma es el segundo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
caminoMaxSuma :: Matrix Int -> [Int] |
caminoMaxSuma :: Matrix Int -> [Int]
tal que (caminoMaxSuma m) es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,
λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[1,7,12,8,4,9]
λ> sum (caminoMaxSuma (fromList 800 800 [1..]))
766721999 |
λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[1,7,12,8,4,9]
λ> sum (caminoMaxSuma (fromList 800 800 [1..]))
766721999
Nota: Se recomienda usar programación dinámica.
Soluciones
import Data.Matrix
-- 1ª definición
-- =============
caminoMaxSuma1 :: Matrix Int -> [Int]
caminoMaxSuma1 m =
head [c | c <- cs, sum c == k]
where cs = caminos1 m
k = maximum (map sum cs)
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
-- =============
caminoMaxSuma2 :: Matrix Int -> [Int]
caminoMaxSuma2 m =
head [c | c <- cs, sum c == k]
where cs = caminos2 m
k = maximum (map sum cs)
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ª definición (con programación dinámica)
-- =========================================
caminoMaxSuma3 :: Matrix Int -> [Int]
caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))
where nf = nrows m
nc = ncols m
q = caminoMaxSumaAux m
caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])
caminoMaxSumaAux m = q
where
nf = nrows m
nc = ncols m
q = matrix nf nc f
where
f (1,1) = (m!(1,1),[m!(1,1)])
f (1,j) = (k + m!(1,j), m!(1,j):xs)
where (k,xs) = q!(1,j-1)
f (i,1) = (k + m!(i,1), m!(i,1):xs)
where (k,xs) = q!(i-1,1)
f (i,j) | k1 > k2 = (k1 + m!(i,j), m!(i,j):xs)
| otherwise = (k2 + m!(i,j), m!(i,j):ys)
where (k1,xs) = q!(i,j-1)
(k2,ys) = q!(i-1,j)
-- Comparación de eficiencia
-- -------------------------
-- λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))
-- 21
-- (10.00 secs, 1,510,120,328 bytes)
-- λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))
-- 21
-- (3.84 secs, 745,918,544 bytes)
-- λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))
-- 21
-- (0.01 secs, 0 bytes) |
import Data.Matrix
-- 1ª definición
-- =============
caminoMaxSuma1 :: Matrix Int -> [Int]
caminoMaxSuma1 m =
head [c | c <- cs, sum c == k]
where cs = caminos1 m
k = maximum (map sum cs)
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
-- =============
caminoMaxSuma2 :: Matrix Int -> [Int]
caminoMaxSuma2 m =
head [c | c <- cs, sum c == k]
where cs = caminos2 m
k = maximum (map sum cs)
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ª definición (con programación dinámica)
-- =========================================
caminoMaxSuma3 :: Matrix Int -> [Int]
caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))
where nf = nrows m
nc = ncols m
q = caminoMaxSumaAux m
caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])
caminoMaxSumaAux m = q
where
nf = nrows m
nc = ncols m
q = matrix nf nc f
where
f (1,1) = (m!(1,1),[m!(1,1)])
f (1,j) = (k + m!(1,j), m!(1,j):xs)
where (k,xs) = q!(1,j-1)
f (i,1) = (k + m!(i,1), m!(i,1):xs)
where (k,xs) = q!(i-1,1)
f (i,j) | k1 > k2 = (k1 + m!(i,j), m!(i,j):xs)
| otherwise = (k2 + m!(i,j), m!(i,j):ys)
where (k1,xs) = q!(i,j-1)
(k2,ys) = q!(i-1,j)
-- Comparación de eficiencia
-- -------------------------
-- λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))
-- 21
-- (10.00 secs, 1,510,120,328 bytes)
-- λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))
-- 21
-- (3.84 secs, 745,918,544 bytes)
-- λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))
-- 21
-- (0.01 secs, 0 bytes)