{"id":7696,"date":"2022-04-02T11:38:35","date_gmt":"2022-04-02T09:38:35","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7696"},"modified":"2022-04-02T11:38:35","modified_gmt":"2022-04-02T09:38:35","slug":"la-semana-en-exercitium-del-28-de-marzo-al-1-de-abril","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/la-semana-en-exercitium-del-28-de-marzo-al-1-de-abril\/","title":{"rendered":"La semana en Exercitium (del 28 de marzo al 1 de abril)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Emparejamiento binario<\/a><\/li>\n<li><a href=\"#ej2\">2. Ampliaci\u00f3n de matrices por columnas<\/a><\/li>\n<li><a href=\"#ej3\">3. Regiones determinadas por n rectas del plano<\/a><\/li>\n<li><a href=\"#ej4\">4. Elemento m\u00e1s repetido de manera consecutiva<\/a><\/li>\n<li><a href=\"#ej5\">5. N\u00famero de pares de elementos adyacentes iguales en una matriz<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Emparejamiento binario<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   zipBinario :: [a -> b -> c] -> [a] -> [b] -> [c]\n<\/pre>\n<p>tal que (zipBinario fs xs ys) es la lista obtenida aplicando cada una de las operaciones binarias de fs a los correspondientes elementos de xs e ys. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   zipBinario [(+), (*), (*)] [2,2,2] [4,4,4]    == [6,8,8]\n   zipBinario [(+)] [2,2,2] [4,4,4]              == [6]\n   zipBinario [(<), (==), (==)] \"coloca\" \"lobo\"  == [True,True,False]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\nimport Test.QuickCheck.HigherOrder\nimport Test.Hspec\n\n-- 1\u00aa soluci\u00f3n\nzipBinario1 :: [a -> b -> c] -> [a] -> [b] -> [c]\nzipBinario1 (f:fs) (x:xs) (y:ys) = f x y : zipBinario1 fs xs ys\nzipBinario1 _ _ _                = []\n\n-- 2\u00aa soluci\u00f3n\nzipBinario2 :: [a -> b -> c] -> [a] -> [b] -> [c]\nzipBinario2 fs xs ys = [f x y | (f,(x,y)) <- zip fs (zip xs ys)]\n\n-- 3\u00aa soluci\u00f3n\nzipBinario3 :: [a -> b -> c] -> [a] -> [b] -> [c]\nzipBinario3 fs xs ys = [f x y | (f,x,y) <- zip3 fs xs ys]\n\n-- 4\u00aa soluci\u00f3n\nzipBinario4 :: [a -> b -> c] -> [a] -> [b] -> [c]\nzipBinario4 = zipWith3 id\n\n-- Verificaci\u00f3n\n-- ============\n\nespecificacion :: ([Int -> Int -> Int] -> [Int] -> [Int] -> [Int]) -> Spec\nespecificacion zipBinario = do\n  it \"e1\" $ zipBinario [(+), (*), (*)] [2,2,2] [4,4,4]    `shouldBe` [6,8,8]\n  it \"e2\" $ zipBinario [(+)] [2,2,2] [4,4,4]              `shouldBe` [6]\n\nverifica :: IO ()\nverifica = hspec $ do\n  describe \"zipBinario1\" $ especificacion zipBinario1\n  describe \"zipBinario2\" $ especificacion zipBinario2\n  describe \"zipBinario3\" $ especificacion zipBinario3\n  describe \"zipBinario4\" $ especificacion zipBinario4\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    zipBinario1\n--      e1\n--      e2\n--    zipBinario2\n--      e1\n--      e2\n--    zipBinario3\n--      e1\n--      e2\n--    zipBinario4\n--      e1\n--      e2\n--\n--    Finished in 0.0016 seconds\n--    8 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n\n-- La propiedad es\nprop_zipBinario :: [Bool -> Bool -> Bool] -> [Bool] -> [Bool] -> Bool\nprop_zipBinario fs xs ys =\n  all (== zipBinario1 fs xs ys)\n      [g fs xs ys | g <- [zipBinario2,\n                          zipBinario3,\n                          zipBinario4]]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck' prop_zipBinario\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> maximum (zipBinario1 (cycle [(+), (*)]) [1..] [1..2*10^6])\n--    4000000000000\n--    (2.13 secs, 965,392,072 bytes)\n--    \u03bb> maximum (zipBinario2 (cycle [(+), (*)]) [1..] [1..2*10^6])\n--    4000000000000\n--    (1.86 secs, 1,109,392,176 bytes)\n--    \u03bb> maximum (zipBinario3 (cycle [(+), (*)]) [1..] [1..2*10^6])\n--    4000000000000\n--    (1.93 secs, 981,392,128 bytes)\n--    \u03bb> maximum (zipBinario4 (cycle [(+), (*)]) [1..] [1..2*10^6])\n--    4000000000000\n--    (1.07 secs, 773,392,040 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Emparejamiento_binario.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\/oQBOs1uPIms\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Ampliaci\u00f3n de matrices por columnas<\/h3>\n<p>Las matrices enteras se pueden representar mediante tablas con \u00edndices enteros:<\/p>\n<pre lang=\"text\">\n   type Matriz = Array (Int,Int) Int\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ampliaColumnas :: Matriz -> Matriz -> Matriz\n<\/pre>\n<p>tal que (ampliaColumnas p q) es la matriz construida a\u00f1adiendo las columnas de la matriz q a continuaci\u00f3n de las de p (se supone que tienen el mismo n\u00famero de filas). Por ejemplo, si p y q representa las dos primeras matrices, entonces (ampliaColumnas p q) es la tercera<\/p>\n<pre lang=\"text\">\n   |0 1|    |4 5 6|    |0 1 4 5 6|\n   |2 3|    |7 8 9|    |2 3 7 8 9|\n<\/pre>\n<p>En Haskell, se definen las dos primeras matrices se definen por<\/p>\n<pre lang=\"text\">\n   ej1 = listArray ((1,1),(2,2)) [0..3]\n   ej2 = listArray ((1,1),(2,3)) [4..9]\n<\/pre>\n<p>y el c\u00e1lculo de la tercera es<\/p>\n<pre lang=\"text\">\n   \u03bb> ampliaColumnas ej1 ej2\n   array ((1,1),(2,5)) [((1,1),0),((1,2),1),((1,3),4),((1,4),5),((1,5),6),\n                        ((2,1),2),((2,2),3),((2,3),7),((2,4),8),((2,5),9)]\n   \u03bb> elems (ampliaColumnas ej1 ej2)\n   [0,1,4,5,6,2,3,7,8,9]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array (Array, (!), array, bounds, elems, listArray)\nimport Data.Matrix (Matrix, (<|>), fromList, ncols, nrows, toList)\nimport Test.QuickCheck\n\ntype Matriz = Array (Int,Int) Int\n\nej1, ej2 :: Matriz\nej1 = listArray ((1,1),(2,2)) [0..3]\nej2 = listArray ((1,1),(2,3)) [4..9]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nampliaColumnas1 :: Matriz -> Matriz -> Matriz\nampliaColumnas1 p1 p2 =\n  array ((1,1),(m,n1+n2)) [((i,j), f i j) | i <- [1..m], j <- [1..n1+n2]]\n    where ((_,_),(m,n1)) = bounds p1\n          ((_,_),(_,n2)) = bounds p2\n          f i j | j <= n1   = p1!(i,j)\n                | otherwise = p2!(i,j-n1)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nampliaColumnas2 :: Matriz -> Matriz -> Matriz\nampliaColumnas2 p1 p2 =\n  matriz (matrix p1 <|> matrix p2)\n\n-- (matrix p) es la matriz p en el formatao de Data.Matrix. Por ejemplo,\n--    \u03bb> ej1\n--    array ((1,1),(2,2)) [((1,1),0),((1,2),1),((2,1),2),((2,2),3)]\n--    \u03bb> matrix ej1\n--    \u250c     \u2510\n--    \u2502 0 1 \u2502\n--    \u2502 2 3 \u2502\n--    \u2514     \u2518\n--    \u03bb> matrix (ampliaColumnas1 ej1 ej2)\n--    \u250c           \u2510\n--    \u2502 0 1 4 5 6 \u2502\n--    \u2502 2 3 7 8 9 \u2502\n--    \u2514           \u2518\nmatrix :: Matriz -> Matrix Int\nmatrix p = fromList m n (elems p)\n  where (_,(m,n)) = bounds p\n\n-- (matriz p) es la matriz p en el formato de Data.Array. Por ejemplo,\n--    \u03bb> matriz (fromList 2 3 [1..])\n--    array ((1,1),(2,3)) [((1,1),1),((1,2),2),((1,3),3),((2,1),4),((2,2),5),((2,3),6)]\nmatriz :: Matrix Int -> Matriz\nmatriz p = listArray ((1,1),(nrows p,ncols p)) (toList p)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\ndata ParMatrices = P Matriz Matriz\n  deriving Show\n\n-- parMatricesArbitrario es un generador de pares de matrices con el\n-- mismo n\u00famero de filas.\nparMatricesArbitrario :: Gen ParMatrices\nparMatricesArbitrario = do\n  m  <- arbitrary `suchThat` (> 0)\n  n1 <- arbitrary `suchThat` (> 0)\n  n2 <- arbitrary `suchThat` (> 0)\n  xs <- vector (m * n1)\n  ys <- vector (m * n2)\n  return (P (listArray ((1,1),(m,n1)) xs)\n            (listArray ((1,1),(m,n2)) ys))\n\n-- ParMatrices es una subclase de Arbitrary\ninstance Arbitrary ParMatrices where\n  arbitrary = parMatricesArbitrario\n\n-- La propiedad es\nprop_ampliaColumna :: ParMatrices -> Bool\nprop_ampliaColumna (P p q) =\n  ampliaColumnas1 p q == ampliaColumnas2 p q\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ampliaColumna\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> let p = listArray ((1,1),(10^3,10^3)) [1..] in maximum (ampliaColumnas1 p p)\n--    1000000\n--    (2.04 secs, 1,562,652,704 bytes)\n--    \u03bb> let p = listArray ((1,1),(10^3,10^3)) [1..] in maximum (ampliaColumnas2 p p)\n--    1000000\n--    (0.69 secs, 738,508,624 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Amplia_columnas.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\/Jrz5kxuhD9Y\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Regiones determinadas por n rectas del plano<\/h3>\n<p>En los siguientes dibujos se observa que el n\u00famero m\u00e1ximo de regiones en el plano generadas con 1, 2 \u00f3 3 l\u00edneas son 2, 4 \u00f3 7, respectivamente.<\/p>\n<pre lang=\"text\">\n\n                      \\  |\n                       \\5|\n                        \\|\n                         \\\n                         |\\\n                         | \\\n               |         |  \\\n    1        1 | 3     1 | 3 \\  6\n   ------   ---|---   ---|----\\---\n    2        2 | 4     2 | 4   \\ 7\n               |         |      \\\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   regiones :: Integer -> Integer\n<\/pre>\n<p>tal que <code>(regiones n)<\/code> es el n\u00famero m\u00e1ximo de regiones en el plano generadas con <code>n<\/code> l\u00edneas. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   regiones 1     ==  2\n   regiones 2     ==  4\n   regiones 3     ==  7\n   regiones 100   ==  5051\n   regiones 1000  ==  500501\n   regiones 10000 ==  50005001\n   length (show (regiones (10^(10^5)))) ==  200000\n   length (show (regiones (10^(10^6)))) ==  2000000\n   length (show (regiones (10^(10^6)))) ==  2000000\n   length (show (regiones (10^(10^7)))) ==  20000000\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericIndex)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nregiones1 :: Integer -> Integer\nregiones1 0 = 1\nregiones1 n = regiones1 (n-1) + n\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nregiones2 :: Integer -> Integer\nregiones2 n = 1 + sum [0..n]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nregiones3 :: Integer -> Integer\nregiones3 n = 1 + sumas `genericIndex` n\n\n-- (sumas n) es la suma 0 + 1 + 2 +...+ n. Por ejemplo,\n--    take 10 sumas  ==  [0,1,3,6,10,15,21,28,36,45]\nsumas :: [Integer]\nsumas = scanl1 (+) [0..]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nregiones4 :: Integer -> Integer\nregiones4 n = 1 + n*(n+1) `div` 2\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_regiones :: Positive Integer -> Bool\nprop_regiones (Positive n) =\n  all (== regiones1 n)\n      [regiones2 n,\n       regiones3 n,\n       regiones4 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_regiones\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> regiones1 (4*10^6)\n--    8000002000001\n--    (2.20 secs, 938,105,888 bytes)\n--    \u03bb> regiones2 (4*10^6)\n--    8000002000001\n--    (0.77 secs, 645,391,624 bytes)\n--    \u03bb> regiones3 (4*10^6)\n--    8000002000001\n--    (1.22 secs, 1,381,375,296 bytes)\n--    \u03bb> regiones4 (4*10^6)\n--    8000002000001\n--    (0.01 secs, 484,552 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Regiones.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\/lLl-jQ1tW-I\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Elemento m\u00e1s repetido de manera consecutiva<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   masRepetido :: Ord a => [a] -> (a,Int)\n<\/pre>\n<p>tal que <code>(masRepetido xs)<\/code> es el elemento de <code>xs<\/code> que aparece m\u00e1s veces de manera consecutiva en la lista junto con el n\u00famero de sus apariciones consecutivas; en caso de empate, se devuelve el mayor de dichos elementos. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   masRepetido [1,1,4,4,1]  ==  (4,2)\n   masRepetido [4,4,1,1,5]  ==  (4,2)\n   masRepetido \"aadda\"      ==  ('d',2)\n   masRepetido \"ddaab\"      ==  ('d',2)\n   masRepetido (show (product [1..5*10^4]))  ==  ('0',12499)\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (group)\nimport Data.Tuple (swap)\nimport Control.Arrow ((&&&))\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmasRepetido1 :: Ord a => [a] -> (a,Int)\nmasRepetido1 [x] = (x,1)\nmasRepetido1 (x:y:zs) | m > n      = (x,m)\n                      | m == n     = (max x u,m)\n                      | otherwise  = (u,n)\n  where (u,n)  = masRepetido1 (y:zs)\n        m      = length (takeWhile (==x) (x:y:zs))\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmasRepetido2 :: Ord a => [a] -> (a,Int)\nmasRepetido2 (x:xs)\n  | null xs'   = (x,length (x:xs))\n  | m > n      = (x,m)\n  | m == n     = (max x u,m)\n  | otherwise  = (u,n)\n  where xs'    = dropWhile (== x) xs\n        m      = length (takeWhile (==x) (x:xs))\n        (u,n)  = masRepetido2 xs'\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmasRepetido3 :: Ord a => [a] -> (a,Int)\nmasRepetido3 xs = (n,z)\n  where (z,n) = maximum [(1 + length ys,y) | (y:ys) <- group xs]\n\n-- 4\u00aa soluci\u00f3n\n-- ============\n\nmasRepetido4 :: Ord a => [a] -> (a,Int)\nmasRepetido4 xs =\n  swap (maximum [(1 + length ys,y) | (y:ys) <- group xs])\n\n-- 5\u00aa soluci\u00f3n\n-- ============\n\nmasRepetido5 :: Ord a => [a] -> (a,Int)\nmasRepetido5 xs =\n  swap (maximum (map (\\ys -> (length ys, head ys)) (group xs)))\n\n-- 6\u00aa soluci\u00f3n\n-- ============\n\nmasRepetido6 :: Ord a => [a] -> (a,Int)\nmasRepetido6 =\n  swap . maximum . map ((,) <$> length <*> head) . group\n\n-- 7\u00aa soluci\u00f3n\n-- ============\n\nmasRepetido7 :: Ord a => [a] -> (a,Int)\nmasRepetido7 =\n  swap . maximum . map (length &&& head) . group\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_masRepetido :: NonEmptyList Int -> Bool\nprop_masRepetido (NonEmpty xs) =\n  all (== masRepetido1 xs)\n      [masRepetido2 xs,\n       masRepetido3 xs,\n       masRepetido4 xs,\n       masRepetido5 xs,\n       masRepetido6 xs,\n       masRepetido7 xs]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_masRepetido\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> masRepetido1 (show (product [1..3*10^4]))\n--    ('0',7498)\n--    (3.72 secs, 2,589,930,952 bytes)\n--    \u03bb> masRepetido2 (show (product [1..3*10^4]))\n--    ('0',7498)\n--    (1.27 secs, 991,406,232 bytes)\n--    \u03bb> masRepetido3 (show (product [1..3*10^4]))\n--    ('0',7498)\n--    (0.85 secs, 945,399,976 bytes)\n--    \u03bb> masRepetido4 (show (product [1..3*10^4]))\n--    ('0',7498)\n--    (0.86 secs, 945,399,888 bytes)\n--    \u03bb> masRepetido5 (show (product [1..3*10^4]))\n--    ('0',7498)\n--    (0.80 secs, 943,760,760 bytes)\n--    \u03bb> masRepetido6 (show (product [1..3*10^4]))\n--    ('0',7498)\n--    (0.78 secs, 945,400,400 bytes)\n--    \u03bb> masRepetido7 (show (product [1..3*10^4]))\n--    ('0',7498)\n--    (0.78 secs, 942,122,088 bytes)\n--\n--    \u03bb> masRepetido2 (show (product [1..5*10^4]))\n--    ('0',12499)\n--    (3.27 secs, 2,798,156,008 bytes)\n--    \u03bb> masRepetido3 (show (product [1..5*10^4]))\n--    ('0',12499)\n--    (2.20 secs, 2,716,952,408 bytes)\n--    \u03bb> masRepetido4 (show (product [1..5*10^4]))\n--    ('0',12499)\n--    (2.22 secs, 2,716,952,320 bytes)\n--    \u03bb> masRepetido5 (show (product [1..5*10^4]))\n--    ('0',12499)\n--    (2.18 secs, 2,714,062,328 bytes)\n--    \u03bb> masRepetido6 (show (product [1..5*10^4]))\n--    ('0',12499)\n--    (2.17 secs, 2,716,952,832 bytes)\n--    \u03bb> masRepetido7 (show (product [1..5*10^4]))\n--    ('0',12499)\n--    (2.17 secs, 2,711,172,792 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Mas_repetido.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\/bz-NO5s2XVQ\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. N\u00famero de pares de elementos adyacentes iguales en una matriz<\/h3>\n<p>Una matriz se puede representar mediante una lista de listas. Por ejemplo, la matriz<\/p>\n<pre lang=\"text\">\n   |2 1 5|\n   |4 3 7|\n<\/pre>\n<p>se puede representar mediante la lista<\/p>\n<pre lang=\"text\">\n   [[2,1,5],[4,3,7]]\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   numeroParesAdyacentesIguales :: Eq a => [[a]] -> Int\n<\/pre>\n<p>tal que <code>(numeroParesAdyacentesIguales xss)<\/code> es el n\u00famero de pares de elementos consecutivos (en la misma fila o columna) iguales de la matriz <code>xss<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   numeroParesAdyacentesIguales [[0,1],[0,2]]              ==  1\n   numeroParesAdyacentesIguales [[0,0],[1,2]]              ==  1\n   numeroParesAdyacentesIguales [[0,1],[0,0]]              ==  2\n   numeroParesAdyacentesIguales [[1,2],[1,4],[4,4]]        ==  3\n   numeroParesAdyacentesIguales [\"ab\",\"aa\"]                ==  2\n   numeroParesAdyacentesIguales [[0,0,0],[0,0,0],[0,0,0]]  ==  12\n   numeroParesAdyacentesIguales [[0,0,0],[0,1,0],[0,0,0]]  ==  8\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (group,transpose)\nimport Data.Array ((!), listArray)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParesAdyacentesIguales1 :: Eq a => [[a]] -> Int\nnumeroParesAdyacentesIguales1 xss =\n  length [(i,j) | i <- [1..m-1], j <- [1..n], p!(i,j) == p!(i+1,j)] +\n  length [(i,j) | i <- [1..m], j <- [1..n-1], p!(i,j) == p!(i,j+1)]\n  where m = length xss\n        n = length (head xss)\n        p = listArray ((1,1),(m,n)) (concat xss)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParesAdyacentesIguales2 :: Eq a => [[a]] -> Int\nnumeroParesAdyacentesIguales2 xss =\n  numeroParesAdyacentesIgualesFilas xss +\n  numeroParesAdyacentesIgualesFilas (transpose xss)\n\n-- (numeroParesAdyacentesIgualesFilas xss) es el n\u00famero de pares de\n-- elementos consecutivos (en la misma fila) iguales de la matriz\n-- xss. Por ejemplo,\n--    \u03bb> numeroParesAdyacentesIgualesFilas [[0,0,1,0],[0,1,1,0],[0,1,0,1]]\n--    2\n--    \u03bb> numeroParesAdyacentesIgualesFilas [\"0010\",\"0110\",\"0101\"]\n--    2\nnumeroParesAdyacentesIgualesFilas :: Eq a => [[a]] -> Int\nnumeroParesAdyacentesIgualesFilas xss =\n  sum [numeroParesAdyacentesIgualesFila xs | xs <- xss]\n\n-- La funci\u00f3n anterior se puede definir con map\nnumeroParesAdyacentesIgualesFilas2 :: Eq a => [[a]] -> Int\nnumeroParesAdyacentesIgualesFilas2 xss =\n  sum (map numeroParesAdyacentesIgualesFila xss)\n\n-- y tambi\u00e9n se puede definir sin argumentos:\nnumeroParesAdyacentesIgualesFilas3 :: Eq a => [[a]] -> Int\nnumeroParesAdyacentesIgualesFilas3 =\n  sum . map numeroParesAdyacentesIgualesFila\n\n-- (numeroParesAdyacentesIgualesFila xs) es el n\u00famero de pares de\n-- elementos consecutivos de la lista xs. Por ejemplo,\n--    numeroParesAdyacentesIgualesFila [5,5,5,2,5] ==  2\nnumeroParesAdyacentesIgualesFila :: Eq a => [a] -> Int\nnumeroParesAdyacentesIgualesFila xs =\n  length [(x,y) | (x,y) <- zip xs (tail xs), x == y]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParesAdyacentesIguales3 :: Eq a => [[a]] -> Int\nnumeroParesAdyacentesIguales3 xss =\n  length (concatMap tail (concatMap group (xss ++ transpose xss)))\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nnumeroParesAdyacentesIguales4 :: Eq a => [[a]] -> Int\nnumeroParesAdyacentesIguales4 =\n  length . (tail =<<) . (group =<<) . ((++) =<< transpose)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\nnewtype Matriz = M [[Int]]\n  deriving Show\n\n-- Generador de matrices arbitrarias. Por ejemplo,\n--    \u03bb> generate matrizArbitraria\n--    M [[-3,0],[8,-6],[-13,-13],[10,8],[14,29]]\n--    \u03bb> generate matrizArbitraria\n--    M [[11,9,4,-25,-29,30,-18],[13,8,-2,-22,29,-3,-13]]\nmatrizArbitraria :: Gen Matriz\nmatrizArbitraria = do\n  m <- chooseInt (1,10)\n  n <- chooseInt (1,10)\n  xss <- vectorOf m (vectorOf n arbitrary)\n  return (M xss)\n\n-- Matriz es una subclase de Arbitrary.\ninstance Arbitrary Matriz where\n  arbitrary = matrizArbitraria\n\n-- La propiedad es\nprop_numeroParesAdyacentesIguales :: Matriz -> Bool\nprop_numeroParesAdyacentesIguales (M xss) =\n  all (== numeroParesAdyacentesIguales1 xss)\n      [numeroParesAdyacentesIguales2 xss,\n       numeroParesAdyacentesIguales3 xss,\n       numeroParesAdyacentesIguales4 xss]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_numeroParesAdyacentesIguales\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> numeroParesAdyacentesIguales1 (replicate (3*10^3) (replicate (10^3) 0))\n--    5996000\n--    (5.51 secs, 4,751,249,472 bytes)\n--    \u03bb> numeroParesAdyacentesIguales2 (replicate (3*10^3) (replicate (10^3) 0))\n--    5996000\n--    (2.62 secs, 1,681,379,960 bytes)\n--    \u03bb> numeroParesAdyacentesIguales3 (replicate (3*10^3) (replicate (10^3) 0))\n--    5996000\n--    (0.48 secs, 1,393,672,616 bytes)\n--    \u03bb> numeroParesAdyacentesIguales4 (replicate (3*10^3) (replicate (10^3) 0))\n--    5996000\n--    (0.38 secs, 1,393,560,848 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Pares_adyacentes_iguales.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\/yt_aRjlA4kQ\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Emparejamiento binario 2. Ampliaci\u00f3n de matrices por columnas 3. Regiones determinadas por n rectas del plano 4. Elemento m\u00e1s repetido de manera consecutiva 5. N\u00famero de pares de elementos adyacentes iguales en una matriz A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7696"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7696"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7696\/revisions"}],"predecessor-version":[{"id":7698,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7696\/revisions\/7698"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}