Matriz de mínimas distancias
Definir las funciones
1 2 |
minimasDistancias :: Matrix Int -> Matrix Int sumaMinimaDistanciasIdentidad :: Int -> Int |
tales que
- (mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 |
λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]]) ( 1 0 0 ) ( 2 1 0 ) λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]]) ( 1 1 0 ) ( 0 1 1 ) λ> minimasDistancias (identity 5) ( 0 1 2 3 4 ) ( 1 0 1 2 3 ) ( 2 1 0 1 2 ) ( 3 2 1 0 1 ) ( 4 3 2 1 0 ) |
- (sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,
1 2 3 4 |
sumaMinimaDistanciasIdentidad 5 == 40 sumaMinimaDistanciasIdentidad (10^2) == 333300 sumaMinimaDistanciasIdentidad (10^4) == 333333330000 sumaMinimaDistanciasIdentidad (10^6) == 333333333333000000 |
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 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 |
import Data.Matrix import Data.Maybe import Test.QuickCheck -- 1ª definición de minimasDistancias -- ================================== minimasDistancias :: Matrix Int -> Matrix Int minimasDistancias a = matrix (nrows a) (ncols a) (\(i,j) -> minimaDistancia (i,j) a) minimaDistancia :: (Int,Int) -> Matrix Int -> Int minimaDistancia (a,b) p = minimum [distancia (a,b) (c,d) | (c,d) <- unos p] unos :: Matrix Int -> [(Int,Int)] unos p = [(i,j) | i <- [1..nrows p] , j <- [1..ncols p] , p ! (i,j) == 1] distancia :: (Int,Int) -> (Int,Int) -> Int distancia (a,b) (c,d) = abs (c - a) + abs (d - b) -- 2ª definición de minimasDistancias -- ================================== minimasDistancias2 :: Matrix Int -> Matrix Int minimasDistancias2 a = fmap fromJust (aux (matrizInicial a)) where aux b | Nothing `elem` c = aux c | otherwise = c where c = propagacion b -- (matrizInicial a) es la matriz que tiene (Just 0) en los elementos de -- a iguales a 1 y Nothing en los restantes. Por ejemplo, -- λ> matrizInicial (fromLists [[0,0,1],[1,0,0]]) -- ( Nothing Nothing Just 0 ) -- ( Just 0 Nothing Nothing ) matrizInicial :: Matrix Int -> Matrix (Maybe Int) matrizInicial a = matrix m n f where m = nrows a n = ncols a f (i,j) | a ! (i,j) == 1 = Just 0 | otherwise = Nothing -- (propagacion a) es la matriz obtenida cambiando los elementos Nothing -- de a por el siguiente del mínimo de los valores de sus vecinos. Por -- ejemplo, -- λ> propagacion (fromLists [[0,1,1],[0,0,1]]) -- ( Just 1 Just 0 Just 0 ) -- ( Nothing Just 1 Just 0 ) -- -- λ> propagacion it -- ( Just 1 Just 0 Just 0 ) -- ( Just 2 Just 1 Just 0 ) propagacion :: Matrix (Maybe Int) -> Matrix (Maybe Int) propagacion a = matrix m n f where m = nrows a n = ncols a f (i,j) | isJust x = x | otherwise = siguiente (minimo (valoresVecinos a (i,j))) where x = a ! (i,j) -- (valoresVecinos a p) es la lista de los valores de los vecinos la -- posición p en la matriz a. Por ejemplo, -- λ> a = fromList 3 4 [1..] -- λ> a -- ( 1 2 3 4 ) -- ( 5 6 7 8 ) -- ( 9 10 11 12 ) -- -- λ> valoresVecinos a (1,1) -- [5,2] -- λ> valoresVecinos a (2,3) -- [3,11,6,8] -- λ> valoresVecinos a (2,4) -- [4,12,7] valoresVecinos :: Matrix a -> (Int,Int) -> [a] valoresVecinos a (i,j) = [a ! (k,l) | (k,l) <- vecinos m n (i,j)] where m = nrows a n = ncols a -- (vecinos m n p) es la lista de las posiciones vecinas de la posición -- p en la matriz a; es decir, los que se encuentran a su izquierda, -- derecha, arriba o abajo. por ejemplo, -- vecinos 3 4 (1,1) == [(2,1),(1,2)] -- vecinos 3 4 (2,3) == [(1,3),(3,3),(2,2),(2,4)] -- vecinos 3 4 (2,4) == [(1,4),(3,4),(2,3)] vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)] vecinos m n (i,j) = [(i - 1,j) | i > 1] ++ [(i + 1,j) | i < m] ++ [(i, j - 1) | j > 1] ++ [(i, j + 1) | j < n] -- (minimo xs) es el mínimo de la lista de valores opcionales xs -- (considerando Nothing como el mayor elemento). Por ejemplo, -- minimo [Just 3, Nothing, Just 2] == Just 2 minimo :: [Maybe Int] -> Maybe Int minimo = foldr1 minimo2 -- (minimo2 x y) es el mínimo de los valores opcionales x e y -- (considerando Nothing como el mayor elemento). Por ejemplo, -- minimo2 (Just 3) (Just 2) == Just 2 -- minimo2 (Just 1) (Just 2) == Just 1 -- minimo2 (Just 1) Nothing == Just 1 -- minimo2 Nothing (Just 2) == Just 2 -- minimo2 Nothing Nothing == Nothing minimo2 :: Maybe Int -> Maybe Int -> Maybe Int minimo2 (Just x) (Just y) = Just (min x y) minimo2 Nothing (Just y) = Just y minimo2 (Just x) Nothing = Just x minimo2 Nothing Nothing = Nothing -- (siguiente x) es el siguiente elemento del opcional x (considerando -- Nothing como el infinito). Por ejemplo, -- siguiente (Just 3) == Just 4 -- siguiente Nothing == Nothing siguiente :: Maybe Int -> Maybe Int siguiente (Just x) = Just (1 + x) siguiente Nothing = Nothing -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> maximum (minimasDistancias (identity 40)) -- 39 -- (3.85 secs, 654,473,496 bytes) -- λ> maximum (minimasDistancias2 (identity 40)) -- 39 -- (0.50 secs, 75,079,912 bytes) -- 1ª definición de sumaMinimaDistanciasIdentidad -- ============================================== sumaMinimaDistanciasIdentidad :: Int -> Int sumaMinimaDistanciasIdentidad n = sum (minimasDistancias (identity n)) -- 2ª definición de sumaMinimaDistanciasIdentidad -- ============================================== sumaMinimaDistanciasIdentidad2 :: Int -> Int sumaMinimaDistanciasIdentidad2 n = n*(n^2-1) `div` 3 -- Equivalencia de las definiciones de sumaMinimaDistanciasIdentidad -- ================================================================= -- La propiedad es prop_MinimaDistanciasIdentidad :: Positive Int -> Bool prop_MinimaDistanciasIdentidad (Positive n) = sumaMinimaDistanciasIdentidad n == sumaMinimaDistanciasIdentidad2 n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=50}) prop_MinimaDistanciasIdentidad -- +++ OK, passed 100 tests. -- Comparación de eficiencia de sumaMinimaDistanciasIdentidad -- ========================================================== -- La comparación es -- λ> sumaMinimaDistanciasIdentidad 50 -- 41650 -- (0.24 secs, 149,395,744 bytes) -- λ> sumaMinimaDistanciasIdentidad 100 -- 333300 -- (1.98 secs, 1,294,676,272 bytes) -- λ> sumaMinimaDistanciasIdentidad 200 -- 2666600 -- (17.96 secs, 11,094,515,016 bytes) -- -- λ> sumaMinimaDistanciasIdentidad2 50 -- 41650 -- (0.00 secs, 126,944 bytes) -- λ> sumaMinimaDistanciasIdentidad2 100 -- 333300 -- (0.00 secs, 126,872 bytes) -- λ> sumaMinimaDistanciasIdentidad2 200 -- 2666600 -- (0.00 secs, 131,240 bytes) -- -- Resumidamente, el tiempo es -- -- +-----+---------+--------+ -- | n | 1ª def. | 2ª def | -- +-----+---------+--------+ -- | 50 | 0.24 | 0.00 | -- | 100 | 1.98 | 0.00 | -- | 200 | 17.96 | 0.00 | -- +-----+---------+--------+ |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
3 Comentarios