{"id":6883,"date":"2022-04-07T06:00:29","date_gmt":"2022-04-07T04:00:29","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6883"},"modified":"2022-04-15T11:59:58","modified_gmt":"2022-04-15T09:59:58","slug":"elementos-de-una-matriz-con-algun-vecino-menor","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/elementos-de-una-matriz-con-algun-vecino-menor\/","title":{"rendered":"Elementos de una matriz con alg\u00fan vecino menor"},"content":{"rendered":"<p>Las matrices pueden representarse mediante tablas cuyos \u00edndices son pares de n\u00fameros naturales. Su tipo se define por<\/p>\n<pre lang=\"text\">\n   type Matriz = Array (Int,Int) Int\n<\/pre>\n<p>Por ejemplo, la matriz<\/p>\n<pre lang=\"text\">\n   |9 4 6 5|\n   |8 1 7 3|\n   |4 2 5 4|\n<\/pre>\n<p>se define por<\/p>\n<pre lang=\"text\">\n   ej :: Matriz\n   ej = listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,4,2,5,4]\n<\/pre>\n<p>Los vecinos de un elemento son los que est\u00e1n a un paso en la misma fila, columna o diagonal. Por ejemplo, en la matriz anterior, el 1 tiene 8 vecinos (el 9, 4, 6, 8, 7, 4, 2 y 5) pero el 9 s\u00f3lo tiene 3 vecinos (el 4, 8 y 1).<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   algunoMenor :: Matriz -> [Int]\n<\/pre>\n<p>tal que <code>(algunoMenor p)<\/code> es la lista de los elementos de <code>p<\/code> que tienen alg\u00fan vecino menor que \u00e9l. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   algunoMenor ej == [9,4,6,5,8,7,4,2,5,4]\n<\/pre>\n<p>pues s\u00f3lo el 1 y el 3 no tienen ning\u00fan vecino menor en la matriz.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array (Array, (!), bounds, indices, inRange, listArray)\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, chooseInt, quickCheck,\n                        vectorOf)\n\ntype Matriz = Array (Int,Int) Int\n\nej :: Matriz\nej = listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,4,2,5,4]\n\ntype Pos = (Int,Int)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor1 :: Matriz -> [Int]\nalgunoMenor1 a =\n  [a!p| p <- indices a,\n        any (< a!p) (vecinos1 a p)]\n\n-- (vecinos q p) es la lista de los vecinos en la matriz a de la\n-- posici\u00f3n p. Por ejemplo,\n--    vecinos1 ej (2,2)  ==  [9,4,6,8,7,4,2,5]\n--    vecinos1 ej (1,1)  ==  [4,8,1]\nvecinos1 :: Matriz -> Pos -> [Int]\nvecinos1 a p =\n  [a!p' | p' <- posicionesVecinos1 a p]\n\n-- (posicionesVecinos a p) es la lista de las posiciones de los\n-- vecino de p en la matriz a. Por ejemplo,\n--    \u03bb> posicionesVecinos1 3 3 (2,2)\n--    [(1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,3)]\n--    \u03bb> posicionesVecinos1 3 3 (1,1)\n--    [(1,2),(2,1),(2,2)]\nposicionesVecinos1 :: Matriz -> Pos -> [Pos]\nposicionesVecinos1 a (i,j) =\n  [(i+di,j+dj) | (di,dj) <- [(-1,-1),(-1,0),(-1,1),\n                             ( 0,-1),       ( 0,1),\n                             ( 1,-1),( 1,0),( 1,1)],\n                 inRange (bounds a) (i+di,j+dj)]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor2 :: Matriz -> [Int]\nalgunoMenor2 a =\n  [a!p | p <- indices a,\n         any (<a!p) (vecinos2 p)]\n  where\n    vecinos2 p =\n      [a!p' | p' <- posicionesVecinos2 p]\n    posicionesVecinos2 (i,j) =\n      [(i+di,j+dj) | (di,dj) <- [(-1,-1),(-1,0),(-1,1),\n                                 ( 0,-1),       ( 0,1),\n                                 ( 1,-1),( 1,0),( 1,1)],\n                     inRange (bounds a) (i+di,j+dj)]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor3 :: Matriz -> [Int]\nalgunoMenor3 a =\n  [a!p | p <- indices a,\n         any (<a!p) (vecinos3 p)]\n  where\n    vecinos3 p =\n      [a!p' | p' <- posicionesVecinos3 p]\n    posicionesVecinos3 (i,j) =\n      [(i',j') | i' <- [i-1..i+1],\n                 j' <- [j-1..j+1],\n                 (i',j') \/= (i,j),\n                 inRange (bounds a) (i',j')]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor4 :: Matriz -> [Int]\nalgunoMenor4 a =\n  [a!p | p <- indices a,\n         any (<a!p) (vecinos4 p)]\n  where\n    vecinos4 p =\n      [a!p' | p' <- posicionesVecinos4 p]\n    posicionesVecinos4 (i,j) =\n      [(i',j') | i' <- [max 1 (i-1)..min m (i+1)],\n                 j' <- [max 1 (j-1)..min n (j+1)],\n                 (i',j') \/= (i,j)]\n      where (_,(m,n)) = bounds a\n\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor5 :: Matriz -> [Int]\nalgunoMenor5 a =\n  [a!p | p <- indices a,\n         any (<a!p) (vecinos5 p)]\n  where\n    vecinos5 p =\n      [a!p' | p' <- posicionesVecinos5 p]\n    posicionesVecinos5 (i,j) =\n      [(i-1,j-1) | i > 1, j > 1] ++\n      [(i-1,j)   | i > 1]        ++\n      [(i-1,j+1) | i > 1, j < n] ++\n      [(i,j-1)   | j > 1]        ++\n      [(i,j+1)   | j < n]        ++\n      [(i+1,j-1) | i < m, j > 1] ++\n      [(i+1,j)   | i < m]        ++\n      [(i+1,j+1) | i < m, j < n]\n      where (_,(m,n)) = bounds a\n\n-- ---------------------------------------------------------------------\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\nnewtype Matriz2 = M Matriz\n  deriving Show\n\n-- Generador de matrices arbitrarias. Por ejemplo,\n--    \u03bb> generate matrizArbitraria\n--    M (array ((1,1),(3,4))\n--             [((1,1),18),((1,2),6), ((1,3),-23),((1,4),-13),\n--              ((2,1),-2),((2,2),22),((2,3),-25),((2,4),-5),\n--              ((3,1),2), ((3,2),16),((3,3),-15),((3,4),7)])\nmatrizArbitraria :: Gen Matriz2\nmatrizArbitraria = do\n  m  <- chooseInt (1,10)\n  n  <- chooseInt (1,10)\n  xs <- vectorOf (m*n) arbitrary\n  return (M (listArray ((1,1),(m,n)) xs))\n\n-- Matriz es una subclase de Arbitrary.\ninstance Arbitrary Matriz2 where\n  arbitrary = matrizArbitraria\n\n-- La propiedad es\nprop_algunoMenor :: Matriz2 -> Bool\nprop_algunoMenor (M p) =\n  all (== algunoMenor1 p)\n      [algunoMenor2 p,\n       algunoMenor3 p,\n       algunoMenor4 p,\n       algunoMenor5 p]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_algunoMenor\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> maximum (algunoMenor1 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (2.20 secs, 1,350,075,240 bytes)\n--    \u03bb> maximum (algunoMenor2 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (2.24 secs, 1,373,139,968 bytes)\n--    \u03bb> maximum (algunoMenor3 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (2.08 secs, 1,200,734,112 bytes)\n--    \u03bb> maximum (algunoMenor4 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (2.76 secs, 1,287,653,136 bytes)\n--    \u03bb> maximum (algunoMenor5 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (1.67 secs, 953,937,600 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Algun_vecino_menor.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/ZILfrx75FyM\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Las matrices pueden representarse mediante tablas cuyos \u00edndices son pares de n\u00fameros naturales. Su tipo se define por type Matriz = Array (Int,Int) Int Por ejemplo, la matriz |9 4 6 5| |8 1 7 3| |4 2 5 4| se define por ej :: Matriz ej = listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,4,2,5,4] Los vecinos de un&#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":[2],"tags":[41,483,43,533,8,507,82,336,72,42,83,84,181,141,11,371,146,534],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6883"}],"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=6883"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6883\/revisions"}],"predecessor-version":[{"id":6932,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6883\/revisions\/6932"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6883"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6883"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6883"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}