Camino de máxima suma en una matriz
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
|
1 2 3 |
( 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 2 3 4 5 6 7 8 9 10 |
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
|
1 |
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,
|
1 2 3 4 |
λ> 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 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
import Data.Matrix import Test.QuickCheck -- 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) -- Equivalencia de las definiciones -- ================================ -- El generador es instance Arbitrary a => Arbitrary (Matrix a) where arbitrary = do m <- choose (1,7) n <- choose (1,7) xs <- Test.QuickCheck.vector (n*m) return (fromList m n xs) -- Por ejemplo, -- λ> sample' (arbitrary :: Gen (Matrix Int)) -- [( 0 ) -- ( 0 ) -- ( 0 ) -- ( 0 ) -- ,( 1 2 ) -- ( -1 1 ) -- ( -1 -2 ) -- ( 1 -1 ) -- ( 1 0 ) -- ( 2 0 ) -- ( 2 -2 ) -- ,( -4 4 -2 ) -- ( -2 0 -2 ) -- ( 0 -1 -2 ) -- ( -4 -1 2 ) -- ,( -2 7 -3 1 -5 -3 5 ) -- ( 0 2 7 -1 -5 7 -6 ) -- ( 1 7 -8 1 6 -7 5 ) -- ( -4 7 -2 -7 -5 5 -8 ) -- ... -- La propiedad es prop_caminoMaxSuma :: Matrix Int -> Bool prop_caminoMaxSuma m = x1 == x2 && x2 == x3 where x1 = sum (caminoMaxSuma1 m) x2 = sum (caminoMaxSuma2 m) x3 = sum (caminoMaxSuma1 m) -- La comprobación es -- λ> quickCheck prop_caminoMaxSuma -- +++ OK, passed 100 tests. -- 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) |
Pensamiento
Caminante, no hay camino,
sino estelas en la mar.Antonio Machado
</pre lang=»haskell»>
import Data.Matrix
caminoMaxSuma :: Matrix Int -> [Int]
caminoMaxSuma m = (m ! (1,1)) : aux m (1,1)
where aux m (i,j) | j== ncols m = [ m ! (k,j) | k <- [i+1..(nrows m)]]
| i== nrows m = [ m ! (i,k) | k (m ! (i,j+1)) = (m ! (i+1,j)):aux m (i+1,j)
| otherwise = (m ! (i,j+1)):aux m (i,j+1)
–Calcula el ultimo ejemplo sin problemas
–sum (caminoMaxSuma (fromList 800 800 [1..]))
–766721999
–(0.08 secs, 57,475,224 bytes)