{"id":7679,"date":"2022-03-12T07:33:49","date_gmt":"2022-03-12T06:33:49","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7679"},"modified":"2022-03-12T07:33:49","modified_gmt":"2022-03-12T06:33:49","slug":"la-semana-en-exercitium-del-7-al-11-de-marzo","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/la-semana-en-exercitium-del-7-al-11-de-marzo\/","title":{"rendered":"La semana en Exercitium (del 7 al 11 de marzo)"},"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. La bandera tricolor<\/a><\/li>\n<li><a href=\"#ej2\">2. Anagramas<\/a><\/li>\n<li><a href=\"#ej3\">3. Primos equidistantes<\/a><\/li>\n<li><a href=\"#ej4\">4. Suma si todos los valores son justos<\/a><\/li>\n<li><a href=\"#ej5\">5. Posiciones de las diagonales principales<\/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. La bandera tricolor<\/h3>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- El problema de la bandera tricolor consiste en lo siguiente: Dada un\n-- lista de objetos xs que pueden ser rojos, amarillos o morados, se pide\n-- devolver una lista ys que contiene los elementos de xs, primero los\n-- rojos, luego los amarillos y por \u00faltimo los morados.\n--\n-- Definir el tipo de dato Color para representar los colores con los\n-- constructores R, A y M correspondientes al rojo, azul y morado y la\n-- funci\u00f3n\n--    banderaTricolor :: [Color] -> [Color]\n-- tal que (banderaTricolor xs) es la bandera tricolor formada con los\n-- elementos de xs. Por ejemplo,\n--    bandera [M,R,A,A,R,R,A,M,M]  ==  [R,R,R,A,A,A,M,M,M]\n--    bandera [M,R,A,R,R,A]        ==  [R,R,R,A,A,M]\n-- ---------------------------------------------------------------------\n\nmodule Bandera_tricolor where\n\nimport Data.List (sort)\nimport Test.QuickCheck (Arbitrary(arbitrary), elements, quickCheck)\n\ndata Color = R | A | M\n  deriving (Show, Eq, Ord, Enum)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nbanderaTricolor1 :: [Color] -> [Color]\nbanderaTricolor1 xs =\n  [x | x <- xs, x == R] ++\n  [x | x <- xs, x == A] ++\n  [x | x <- xs, x == M]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nbanderaTricolor2 :: [Color] -> [Color]\nbanderaTricolor2 xs =\n  colores R ++ colores A ++ colores M\n  where colores c = filter (== c) xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nbanderaTricolor3 :: [Color] -> [Color]\nbanderaTricolor3 xs =\n  concat [[x | x <- xs, x == c] | c <- [R,A,M]]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nbanderaTricolor4 :: [Color] -> [Color]\nbanderaTricolor4 xs = aux xs ([],[],[])\n  where aux []     (rs,as,ms) = rs ++ as ++ ms\n        aux (R:ys) (rs,as,ms) = aux ys (R:rs,   as,   ms)\n        aux (A:ys) (rs,as,ms) = aux ys (  rs, A:as,   ms)\n        aux (M:ys) (rs,as,ms) = aux ys (  rs,   as, M:ms)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nbanderaTricolor5 :: [Color] -> [Color]\nbanderaTricolor5 = sort\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\ninstance Arbitrary Color where\n  arbitrary = elements [A,R,M]\n\n-- La propiedad es\nprop_banderaTricolor :: [Color] -> Bool\nprop_banderaTricolor xs =\n  all (== banderaTricolor1 xs)\n      [banderaTricolor2 xs,\n       banderaTricolor3 xs,\n       banderaTricolor4 xs,\n       banderaTricolor5 xs]\n\nverifica_banderaTricolor :: IO ()\nverifica_banderaTricolor =\n  quickCheck prop_banderaTricolor\n\n-- La comprobaci\u00f3n es\n--    \u03bb> verifica_banderaTricolor\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> bandera n = concat [replicate n c | c <- [M,R,A]]\n--    \u03bb> length (banderaTricolor1 (bandera (10^6)))\n--    3000000\n--    (1.51 secs, 1,024,454,768 bytes)\n--    \u03bb> length (banderaTricolor1 (bandera (2*10^6)))\n--    6000000\n--    (2.94 secs, 2,048,454,832 bytes)\n--    \u03bb> length (banderaTricolor2 (bandera (2*10^6)))\n--    6000000\n--    (2.35 secs, 1,232,454,920 bytes)\n--    \u03bb> length (banderaTricolor3 (bandera (2*10^6)))\n--    6000000\n--    (4.28 secs, 2,304,455,360 bytes)\n--    \u03bb> length (banderaTricolor4 (bandera (2*10^6)))\n--    6000000\n--    (3.01 secs, 1,904,454,672 bytes)\n--    \u03bb> length (banderaTricolor5 (bandera (2*10^6)))\n--    6000000\n--    (2.47 secs, 1,248,454,744 bytes)\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Anagramas<\/h3>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Una palabra es una anagrama de otra si se puede obtener permutando\n-- sus letras. Por ejemplo, \"mora\" y \"roma\" son anagramas de \"amor\".\n--\n-- Definir la funci\u00f3n\n--    anagramas :: String -> [String] -> [String]\n-- tal que (anagramas x ys) es la lista de los elementos de ys que son\n-- anagramas de x. Por ejemplo,\n--    \u03bb> anagramas \"amor\" [\"Roma\",\"mola\",\"loma\",\"moRa\", \"rama\"]\n--    [\"Roma\",\"moRa\"]\n--    \u03bb> anagramas \"rama\" [\"aMar\",\"amaRa\",\"roMa\",\"marr\",\"aRma\"]\n--    [\"aMar\",\"aRma\"]\n-- ---------------------------------------------------------------------\n\nmodule Anagramas where\n\nimport Data.List (delete, sort)\nimport Data.Char (toLower)\nimport Data.Function (on)\n\n-- 1\u00aa soluci\u00f3n\n-- =============\n\nanagramas :: String -> [String] -> [String]\nanagramas _ [] = []\nanagramas x (y:ys)\n  | sonAnagramas x y = y : anagramas x ys\n  | otherwise        = anagramas x ys\n\n-- (sonAnagramas xs ys) se verifica si xs e ys son anagramas. Por\n-- ejemplo,\n--    sonAnagramas \"amor\" \"Roma\"  ==  True\n--    sonAnagramas \"amor\" \"mola\"  ==  False\nsonAnagramas :: String -> String -> Bool\nsonAnagramas xs ys =\n  sort (map toLower xs) == sort (map toLower ys)\n\n-- 2\u00aa soluci\u00f3n\n-- =============\n\nanagramas2 :: String -> [String] -> [String]\nanagramas2 _ [] = []\nanagramas2 x (y:ys)\n  | sonAnagramas2 x y = y : anagramas2 x ys\n  | otherwise         = anagramas2 x ys\n\nsonAnagramas2 :: String -> String -> Bool\nsonAnagramas2 xs ys =\n  (sort . map toLower) xs == (sort . map toLower) ys\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nanagramas3 :: String -> [String] -> [String]\nanagramas3 _ [] = []\nanagramas3 x (y:ys)\n  | sonAnagramas3 x y = y : anagramas3 x ys\n  | otherwise         = anagramas3 x ys\n\nsonAnagramas3 :: String -> String -> Bool\nsonAnagramas3 = (==) `on` (sort . map toLower)\n\n-- Nota. En la soluci\u00f3n anterior se usa la funci\u00f3n on ya que\n--    (f `on` g) x y\n-- es equivalente a\n--    f (g x) (g y)\n-- Por ejemplo,\n--    \u03bb> ((*) `on` (+2)) 3 4\n--    30\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nanagramas4 :: String -> [String] -> [String]\nanagramas4 x ys = [y | y <- ys, sonAnagramas x y]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nanagramas5 :: String -> [String] -> [String]\nanagramas5 x = filter (`sonAnagramas` x)\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nanagramas6 :: String -> [String] -> [String]\nanagramas6 x = filter (((==) `on` (sort . map toLower)) x)\n\n-- 7\u00aa soluci\u00f3n\n-- ===========\n\nanagramas7 :: String -> [String] -> [String]\nanagramas7 _ [] = []\nanagramas7 x (y:ys)\n  | sonAnagramas7 x y = y : anagramas7 x ys\n  | otherwise         = anagramas7 x ys\n\nsonAnagramas7 :: String -> String -> Bool\nsonAnagramas7 xs ys = aux (map toLower xs) (map toLower ys)\n  where\n    aux [] [] = True\n    aux [] _  = False\n    aux (u:us) vs | u `notElem` vs = False\n                  | otherwise      = aux us (delete u vs)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> ej = take (10^6) (permutations \"1234567890\")\n--    \u03bb> length (anagramas \"1234567890\" ej)\n--    1000000\n--    (2.27 secs, 5,627,236,104 bytes)\n--    \u03bb> length (anagramas2 \"1234567890\" ej)\n--    1000000\n--    (2.80 secs, 5,513,260,584 bytes)\n--    \u03bb> length (anagramas3 \"1234567890\" ej)\n--    1000000\n--    (1.86 secs, 5,097,260,856 bytes)\n--    \u03bb> length (anagramas4 \"1234567890\" ej)\n--    1000000\n--    (2.25 secs, 5,073,260,632 bytes)\n--    \u03bb> length (anagramas5 \"1234567890\" ej)\n--    1000000\n--    (2.14 secs, 5,009,260,616 bytes)\n--    \u03bb> length (anagramas6 \"1234567890\" ej)\n--    1000000\n--    (1.58 secs, 4,977,260,976 bytes)\n--    \u03bb> length (anagramas7 \"1234567890\" ej)\n--    1000000\n--    (6.63 secs, 6,904,821,648 bytes)\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Primos equidistantes<\/h3>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Definir la funci\u00f3n\n--    primosEquidistantes :: Integer -> [(Integer,Integer)]\n-- tal que (primosEquidistantes k) es la lista de los pares de primos\n-- cuya diferencia es k. Por ejemplo,\n--    take 3 (primosEquidistantes 2)  ==  [(3,5),(5,7),(11,13)]\n--    take 3 (primosEquidistantes 4)  ==  [(7,11),(13,17),(19,23)]\n--    take 3 (primosEquidistantes 6)  ==  [(23,29),(31,37),(47,53)]\n--    take 3 (primosEquidistantes 8)  ==  [(89,97),(359,367),(389,397)]\n--    primosEquidistantes 4 !! (10^5) ==  (18467047,18467051)\n-- ---------------------------------------------------------------------\n\n{-# OPTIONS_GHC -fno-warn-incomplete-patterns #-}\n\nmodule Primos_equidistantes where\n\nimport Data.Numbers.Primes (primes)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosEquidistantes1 :: Integer -> [(Integer,Integer)]\nprimosEquidistantes1 k = aux primos\n  where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)\n                     | otherwise  = aux (y:ps)\n\n-- (primo x) se verifica si x es primo. Por ejemplo,\n--    primo 7  ==  True\n--    primo 8  ==  False\nprimo :: Integer -> Bool\nprimo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]\n\n-- primos es la lista de los n\u00fameros primos. Por ejemplo,\n--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]\nprimos :: [Integer]\nprimos = 2 : [x | x <- [3,5..], primo x]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nprimosEquidistantes2 :: Integer -> [(Integer,Integer)]\nprimosEquidistantes2 k = aux primos2\n  where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)\n                     | otherwise  = aux (y:ps)\n\nprimos2 :: [Integer]\nprimos2 = criba [2..]\n  where criba (p:ps) = p : criba [n | n <- ps, mod n p \/= 0]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nprimosEquidistantes3 :: Integer -> [(Integer,Integer)]\nprimosEquidistantes3 k = aux primos3\n  where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)\n                     | otherwise  = aux (y:ps)\n\nprimos3 :: [Integer]\nprimos3 = 2 : 3 : criba3 0 (tail primos3) 3\n  where criba3 k (p:ps) x = [n | n <- [x+2,x+4..p*p-2],\n                                 and [n `rem` q \/= 0 | q <- take k (tail primos3)]]\n                            ++ criba3 (k+1) ps (p*p)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nprimosEquidistantes4 :: Integer -> [(Integer,Integer)]\nprimosEquidistantes4 k = aux primes\n  where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)\n                     | otherwise  = aux (y:ps)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nprimosEquidistantes5 :: Integer -> [(Integer,Integer)]\nprimosEquidistantes5 k =\n  [(x,y) | (x,y) <- zip primes (tail primes)\n         , y - x == k]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> primosEquidistantes1 4 !! 200\n--    (9829,9833)\n--    (2.60 secs, 1,126,458,272 bytes)\n--    \u03bb> primosEquidistantes2 4 !! 200\n--    (9829,9833)\n--    (0.44 secs, 249,622,048 bytes)\n--    \u03bb> primosEquidistantes3 4 !! 200\n--    (9829,9833)\n--    (0.06 secs, 13,352,208 bytes)\n--    \u03bb> primosEquidistantes4 4 !! 200\n--    (9829,9833)\n--    (0.02 secs, 4,012,848 bytes)\n--    \u03bb> primosEquidistantes5 4 !! 200\n--    (9829,9833)\n--    (0.01 secs, 7,085,072 bytes)\n--\n--    \u03bb> primosEquidistantes2 4 !! 600\n--    (41617,41621)\n--    (5.67 secs, 3,340,313,480 bytes)\n--    \u03bb> primosEquidistantes3 4 !! 600\n--    (41617,41621)\n--    (0.14 secs, 76,600,968 bytes)\n--    \u03bb> primosEquidistantes4 4 !! 600\n--    (41617,41621)\n--    (0.03 secs, 15,465,824 bytes)\n--    \u03bb> primosEquidistantes5 4 !! 600\n--    (41617,41621)\n--    (0.04 secs, 28,858,232 bytes)\n--\n--    \u03bb> primosEquidistantes3 4 !! 5000\n--    (556819,556823)\n--    (3.58 secs, 2,040,940,144 bytes)\n--    \u03bb> primosEquidistantes4 4 !! 5000\n--    (556819,556823)\n--    (0.12 secs, 220,705,192 bytes)\n--    \u03bb> primosEquidistantes5 4 !! 5000\n--    (556819,556823)\n--    (0.16 secs, 424,501,800 bytes)\n--\n--    \u03bb> primosEquidistantes4 4 !! (10^5)\n--    (18467047,18467051)\n--    (3.99 secs, 9,565,715,488 bytes)\n--    \u03bb> primosEquidistantes5 4 !! (10^5)\n--    (18467047,18467051)\n--    (7.95 secs, 18,712,469,144 bytes)\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Suma si todos los valores son justos<\/h3>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Definir la funci\u00f3n\n--    sumaSiTodosJustos :: (Num a, Eq a) => [Maybe a] -> Maybe a\n-- tal que (sumaSiTodosJustos xs) es justo la suma de todos los\n-- elementos de xs si todos son justos (es decir, si Nothing no\n-- pertenece a xs) y Nothing en caso contrario. Por ejemplo,\n--    sumaSiTodosJustos [Just 2, Just 5]           == Just 7\n--    sumaSiTodosJustos [Just 2, Just 5, Nothing]  == Nothing\n-- ---------------------------------------------------------------------\n\nmodule Suma_si_todos_justos where\n\nimport Data.Maybe (catMaybes, isJust, fromJust)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumaSiTodosJustos1 :: (Num a, Eq a) => [Maybe a] -> Maybe a\nsumaSiTodosJustos1 xs\n  | todosJustos xs = Just (sum [x | (Just x) <- xs])\n  | otherwise      = Nothing\n\n-- (todosJustos xs) se verifica si todos los elementos de xs son justos\n-- (es decir, si Nothing no pertenece a xs) y Nothing en caso\n-- contrario. Por ejemplo,\n--    todosJustos [Just 2, Just 5]           == True\n--    todosJustos [Just 2, Just 5, Nothing]  == False\n\n-- 1\u00aa definici\u00f3n de todosJustos:\ntodosJustos1 :: Eq a => [Maybe a] -> Bool\ntodosJustos1 = notElem Nothing\n\n-- 2\u00aa definici\u00f3n de todosJustos:\ntodosJustos :: Eq a => [Maybe a] -> Bool\ntodosJustos = all isJust\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumaSiTodosJustos2 :: (Num a, Eq a) => [Maybe a] -> Maybe a\nsumaSiTodosJustos2 xs\n  | todosJustos xs = Just (sum [fromJust x | x <- xs])\n  | otherwise      = Nothing\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsumaSiTodosJustos3 :: (Num a, Eq a) => [Maybe a] -> Maybe a\nsumaSiTodosJustos3 xs\n  | todosJustos xs = Just (sum (map fromJust xs))\n  | otherwise      = Nothing\n\n-- 4\u00aa soluci\u00f3n\n\nsumaSiTodosJustos4 :: (Num a, Eq a) => [Maybe a] -> Maybe a\nsumaSiTodosJustos4 xs\n  | todosJustos xs = Just (sum (catMaybes xs))\n  | otherwise      = Nothing\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nsumaSiTodosJustos5 :: (Num a, Eq a) => [Maybe a] -> Maybe a\nsumaSiTodosJustos5 xs = suma (sequence xs)\n  where suma Nothing   = Nothing\n        suma (Just ys) = Just (sum ys)\n\n-- Nota. En la soluci\u00f3n anterior se usa la funci\u00f3n\n--    sequence :: Monad m => [m a] -> m [a]\n-- tal que (sequence xs) es la m\u00f3nada obtenida evaluando cada una de las\n-- de xs de izquierda a derecha. Por ejemplo,\n--    sequence [Just 2, Just 5]   ==  Just [2,5]\n--    sequence [Just 2, Nothing]  ==  Nothing\n--    sequence [[2,4],[5,7]]      ==  [[2,5],[2,7],[4,5],[4,7]]\n--    sequence [[2,4],[5,7],[6]]  ==  [[2,5,6],[2,7,6],[4,5,6],[4,7,6]]\n--    sequence [[2,4],[5,7],[]]   ==  []\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nsumaSiTodosJustos6 :: (Num a, Eq a) => [Maybe a] -> Maybe a\nsumaSiTodosJustos6 xs = fmap sum (sequence xs)\n\n-- 7\u00aa soluci\u00f3n\n-- ===========\n\nsumaSiTodosJustos7 :: (Num a, Eq a) => [Maybe a] -> Maybe a\nsumaSiTodosJustos7 = fmap sum . sequence\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_sumaSiTodosJustos :: [Maybe Integer] -> Bool\nprop_sumaSiTodosJustos xs =\n  all (== sumaSiTodosJustos1 xs)\n      [sumaSiTodosJustos2 xs,\n       sumaSiTodosJustos3 xs,\n       sumaSiTodosJustos4 xs,\n       sumaSiTodosJustos5 xs,\n       sumaSiTodosJustos6 xs,\n       sumaSiTodosJustos7 xs]\n\nverifica_sumaSiTodosJustos :: IO ()\nverifica_sumaSiTodosJustos =\n  quickCheck prop_sumaSiTodosJustos\n\n-- La comprobaci\u00f3n es\n--    \u03bb> verifica_sumaSiTodosJustos\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Posiciones de las diagonales principales<\/h3>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Las posiciones de una matriz con 3 filas y 4 columnas son\n--    (1,1) (1,2) (1,3) (1,4)\n--    (2,1) (2,2) (2,3) (2,4)\n--    (3,1) (3,2) (3,3) (3,4)\n-- La posiciones de sus 6 diagonales principales son\n--   [(3,1)]\n--   [(2,1),(3,2)]\n--   [(1,1),(2,2),(3,3)]\n--   [(1,2),(2,3),(3,4)]\n--   [(1,3),(2,4)]\n--   [(1,4)]\n--\n-- Definir la funci\u00f3n\n--    posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]]\n-- tal que (posicionesdiagonalesprincipales m n) es la lista de las\n-- posiciones de las diagonales principales de una matriz con m filas y\n-- n columnas. Por ejemplo,\n--   \u03bb> mapM_ print (posicionesDiagonalesPrincipales 3 4)\n--   [(3,1)]\n--   [(2,1),(3,2)]\n--   [(1,1),(2,2),(3,3)]\n--   [(1,2),(2,3),(3,4)]\n--   [(1,3),(2,4)]\n--   [(1,4)]\n--   \u03bb> mapM_ print (posicionesDiagonalesPrincipales 4 4)\n--   [(4,1)]\n--   [(3,1),(4,2)]\n--   [(2,1),(3,2),(4,3)]\n--   [(1,1),(2,2),(3,3),(4,4)]\n--   [(1,2),(2,3),(3,4)]\n--   [(1,3),(2,4)]\n--   [(1,4)]\n--   \u03bb> mapM_ print (posicionesDiagonalesPrincipales 4 3)\n--   [(4,1)]\n--   [(3,1),(4,2)]\n--   [(2,1),(3,2),(4,3)]\n--   [(1,1),(2,2),(3,3)]\n--   [(1,2),(2,3)]\n--   [(1,3)]\n-- ---------------------------------------------------------------------\n\nmodule Posiciones_diagonales_principales where\n\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nposicionesDiagonalesPrincipales1 :: Int -> Int -> [[(Int, Int)]]\nposicionesDiagonalesPrincipales1 m n =\n  [extension ij | ij <- iniciales]\n  where iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]]\n        extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nposicionesDiagonalesPrincipales2 :: Int -> Int -> [[(Int, Int)]]\nposicionesDiagonalesPrincipales2 m n =\n  [zip [i..m] [1..n] | i <- [m,m-1..1]] ++\n  [zip [1..m] [j..n] | j <- [2..n]]\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_posicionesDiagonalesPrincipales :: Positive Int -> Positive Int -> Bool\nprop_posicionesDiagonalesPrincipales (Positive m) (Positive n) =\n  posicionesDiagonalesPrincipales1 m n ==\n  posicionesDiagonalesPrincipales2 m n\n\n-- La comprobaci\u00f3n es\n--   \u03bb> quickCheck prop_posicionesDiagonalesPrincipales\n--   +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--   \u03bb> length (posicionesDiagonalesPrincipales1 (10^7) (10^6))\n--   10999999\n--   (6.14 secs, 3,984,469,440 bytes)\n--   \u03bb> length (posicionesDiagonalesPrincipales2 (10^7) (10^6))\n--   10999999\n--   (3.07 secs, 2,840,469,440 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. La bandera tricolor 2. Anagramas 3. Primos equidistantes 4. Suma si todos los valores son justos 5. Posiciones de las diagonales principales 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\/7679"}],"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=7679"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7679\/revisions"}],"predecessor-version":[{"id":7680,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7679\/revisions\/7680"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7679"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7679"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7679"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}