{"id":4856,"date":"2019-03-22T06:00:58","date_gmt":"2019-03-22T04:00:58","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4856"},"modified":"2021-04-25T16:21:52","modified_gmt":"2021-04-25T14:21:52","slug":"matriz-de-minimas-distancias-2019","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/matriz-de-minimas-distancias-2019\/","title":{"rendered":"Matriz de m\u00ednimas distancias"},"content":{"rendered":"<p>Definir las funciones<\/p>\n<pre lang=\"text\"> \n   minimasDistancias             :: Matrix Int -> Matrix Int\n   sumaMinimaDistanciasIdentidad :: Int -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(mininasDistancias a) es la matriz de las m\u00ednimas 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, <\/li>\n<\/ul>\n<pre lang=\"text\">   \n     \u03bb> minimasDistancias (fromLists [[0,1,1],[0,0,1]])\n     ( 1 0 0 )\n     ( 2 1 0 )\n     \u03bb> minimasDistancias (fromLists [[0,0,1],[1,0,0]])\n     ( 1 1 0 )\n     ( 0 1 1 )\n     \u03bb> minimasDistancias (identity 5)\n     ( 0 1 2 3 4 )\n     ( 1 0 1 2 3 )\n     ( 2 1 0 1 2 )\n     ( 3 2 1 0 1 )\n     ( 4 3 2 1 0 )\n<\/pre>\n<ul>\n<li>(sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las m\u00ednimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">   \n     sumaMinimaDistanciasIdentidad 5       ==  40\n     sumaMinimaDistanciasIdentidad (10^2)  ==  333300\n     sumaMinimaDistanciasIdentidad (10^4)  ==  333333330000\n     sumaMinimaDistanciasIdentidad (10^6)  ==  333333333333000000\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Matrix\nimport Data.Maybe (isJust, fromJust)\nimport Test.QuickCheck\n\n-- Definici\u00f3n de minimasDistancias\n-- ===============================\n\nminimasDistancias :: Matrix Int -> Matrix Int\nminimasDistancias a = fmap fromJust (aux (matrizInicial a))\n  where aux b | Nothing `elem` c = aux c\n              | otherwise        = c\n          where c = propagacion b\n\n-- (matrizInicial a) es la matriz que tiene (Just 0) en los elementos de\n-- a iguales a 1 y Nothing en los restantes. Por ejemplo,\n--    \u03bb> matrizInicial (fromLists [[0,0,1],[1,0,0]])\n--    ( Nothing Nothing  Just 0 )\n--    (  Just 0 Nothing Nothing )\nmatrizInicial :: Matrix Int -> Matrix (Maybe Int)\nmatrizInicial a = matrix m n f\n  where m = nrows a\n        n = ncols a\n        f (i,j) | a ! (i,j) == 1 = Just 0\n                | otherwise      = Nothing\n\n-- (propagacion a) es la matriz obtenida cambiando los elementos Nothing\n-- de a por el sigiente del m\u00ednomo de los valores de sus vecinos. Por\n-- ejemplo,\n--    \u03bb> propagacion (fromLists [[0,1,1],[0,0,1]])\n--    (  Just 1  Just 0  Just 0 )\n--    ( Nothing  Just 1  Just 0 )\n--    \n--    \u03bb> propagacion it\n--    ( Just 1 Just 0 Just 0 )\n--    ( Just 2 Just 1 Just 0 )\npropagacion :: Matrix (Maybe Int) -> Matrix (Maybe Int)\npropagacion a = matrix m n f\n  where\n    m = nrows a\n    n = ncols a\n    f (i,j) | isJust x  = x\n            | otherwise = siguiente (minimo (valoresVecinos a (i,j)))\n      where x = a ! (i,j)\n\n-- (valoresVecinos a p) es la lista de los valores de los vecinos la\n-- posici\u00f3n p en la matriz a. Por ejemplo,             \n--    \u03bb> a = fromList 3 4 [1..]\n--    \u03bb> a\n--    (  1  2  3  4 )\n--    (  5  6  7  8 )\n--    (  9 10 11 12 )\n--    \n--    \u03bb> valoresVecinos a (1,1)\n--    [5,2]\n--    \u03bb> valoresVecinos a (2,3)\n--    [3,11,6,8]\n--    \u03bb> valoresVecinos a (2,4)\n--    [4,12,7]\nvaloresVecinos :: Matrix a -> (Int,Int) -> [a]\nvaloresVecinos a (i,j) = [a ! (k,l) | (k,l) <- vecinos m n (i,j)]\n  where m = nrows a\n        n = ncols a\n\n-- (vecinos m n p) es la lista de las posiciones vecinas de la posici\u00f3n\n-- p en la matriz a; es decir, los que se encuentran a su izquierda,\n-- derecha, arriba o abajo. por ejemplo,\n--    vecinos 3 4 (1,1)  ==  [(2,1),(1,2)]\n--    vecinos 3 4 (2,3)  ==  [(1,3),(3,3),(2,2),(2,4)]\n--    vecinos 3 4 (2,4)  ==  [(1,4),(3,4),(2,3)]\nvecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]\nvecinos m n (i,j) = [(i - 1,j)     | i > 1] ++\n                    [(i + 1,j)     | i < m] ++\n                    [(i,    j - 1) | j > 1] ++\n                    [(i,    j + 1) | j < n]\n\n-- (minimo xs) es el m\u00ednimo de la lista de valores opcionales xs\n-- (considerando Nothing como el mayor elemento). Por ejemplo,\n--    minimo [Just 3, Nothing, Just 2]  ==  Just 2\nminimo :: [Maybe Int] -> Maybe Int\nminimo = foldr1 minimo2\n\n-- (minimo2 x y) es el m\u00ednimo de los valores opcionales x e y\n-- (considerando Nothing como el mayor elemento). Por ejemplo,\n--    minimo2 (Just 3) (Just 2)  ==  Just 2\n--    minimo2 (Just 1) (Just 2)  ==  Just 1\n--    minimo2 (Just 1) Nothing   ==  Just 1\n--    minimo2 Nothing (Just 2)   ==  Just 2\n--    minimo2 Nothing Nothing    ==  Nothing\nminimo2 :: Maybe Int -> Maybe Int -> Maybe Int\nminimo2 (Just x) (Just y) = Just (min x y)\nminimo2 Nothing  (Just y) = Just y\nminimo2 (Just x) Nothing  = Just x\nminimo2 Nothing  Nothing  = Nothing\n\n-- (siguiente x) es el siguiente elemento del opcional x (considerando\n-- Nothing como el infinito). Por ejemplo, \n--    siguiente (Just 3)  ==  Just 4\n--    siguiente Nothing  ==  Nothing\nsiguiente :: Maybe Int -> Maybe Int\nsiguiente (Just x) = Just (1 + x)\nsiguiente Nothing  = Nothing\n\n-- 1\u00aa definici\u00f3n de sumaMinimaDistanciasIdentidad\n-- ==============================================\n\nsumaMinimaDistanciasIdentidad :: Int -> Int\nsumaMinimaDistanciasIdentidad n =\n  sum (minimasDistancias (identity n))\n\n-- 2\u00aa definici\u00f3n de sumaMinimaDistanciasIdentidad\n-- ==============================================\n\nsumaMinimaDistanciasIdentidad2 :: Int -> Int\nsumaMinimaDistanciasIdentidad2 n =\n  n*(n^2-1) `div` 3\n\n-- Equivalencia de las definiciones de sumaMinimaDistanciasIdentidad\n-- =================================================================\n\n-- La propiedad es\nprop_MinimaDistanciasIdentidad :: Positive Int -> Bool\nprop_MinimaDistanciasIdentidad (Positive n) =\n  sumaMinimaDistanciasIdentidad n == sumaMinimaDistanciasIdentidad2 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=50}) prop_MinimaDistanciasIdentidad\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sumaMinimaDistanciasIdentidad 50\n--    41650\n--    (0.24 secs, 149,395,744 bytes)\n--    \u03bb> sumaMinimaDistanciasIdentidad 100\n--    333300\n--    (1.98 secs, 1,294,676,272 bytes)\n--    \u03bb> sumaMinimaDistanciasIdentidad 200\n--    2666600\n--    (17.96 secs, 11,094,515,016 bytes)\n--    \n--    \u03bb> sumaMinimaDistanciasIdentidad2 50\n--    41650\n--    (0.00 secs, 126,944 bytes)\n--    \u03bb> sumaMinimaDistanciasIdentidad2 100\n--    333300\n--    (0.00 secs, 126,872 bytes)\n--    \u03bb> sumaMinimaDistanciasIdentidad2 200\n--    2666600\n--    (0.00 secs, 131,240 bytes)\n--\n-- Resumidamente, el tiempo es\n--\n--    +-----+---------+--------+\n--    |   n | 1\u00aa def. | 2\u00aa def |\n--    +-----+---------+--------+\n--    |  50 |  0.24   | 0.00   |\n--    | 100 |  1.98   | 0.00   |\n--    | 200 | 17.96   | 0.00   | \n--    +-----+---------+--------+\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\nLa primavera ha venido.<br \/>\nNadie sabe como ha sido.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Definir las funciones minimasDistancias :: Matrix Int -> Matrix Int sumaMinimaDistanciasIdentidad :: Int -> Int tales que (mininasDistancias a) es la matriz de las m\u00ednimas 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, \u03bb> minimasDistancias (fromLists [[0,1,1],[0,0,1]]) (&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[7],"tags":[130,8,286,469,468,243,419,42,97,84,340,99,98,11],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4856"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=4856"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4856\/revisions"}],"predecessor-version":[{"id":4892,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4856\/revisions\/4892"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4856"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4856"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4856"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}