{"id":6816,"date":"2022-03-25T06:00:59","date_gmt":"2022-03-25T04:00:59","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6816"},"modified":"2022-04-01T17:23:56","modified_gmt":"2022-04-01T15:23:56","slug":"numero-de-pares-de-elementos-adyacentes-iguales-en-una-matriz","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numero-de-pares-de-elementos-adyacentes-iguales-en-una-matriz\/","title":{"rendered":"N\u00famero de pares de elementos adyacentes iguales en una matriz"},"content":{"rendered":"

Una matriz se puede representar mediante una lista de listas. Por ejemplo, la matriz<\/p>\n

\n   |2 1 5|\n   |4 3 7|\n<\/pre>\n
se puede representar mediante la lista<\/p>\n
\n   [[2,1,5],[4,3,7]]\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   numeroParesAdyacentesIguales :: Eq a => [[a]] -> Int\n<\/pre>\n
tal que (numeroParesAdyacentesIguales xss)<\/code> es el n\u00famero de pares de elementos consecutivos (en la misma fila o columna) iguales de la matriz xss<\/code>. Por ejemplo,<\/p>\n
\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
Soluciones<\/h4>\n
\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
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n