{"id":8171,"date":"2024-04-02T14:19:48","date_gmt":"2024-04-02T12:19:48","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=8171"},"modified":"2024-04-02T14:20:03","modified_gmt":"2024-04-02T12:20:03","slug":"02-abr-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/02-abr-24\/","title":{"rendered":"El mes de marzo en Exercitium (Ejercicios con Haskell y Python)"},"content":{"rendered":"<p>Durante el mes de marzo 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. Reiteraci\u00f3n de suma de consecutivos<\/a><\/li>\n<li><a href=\"#ej2\">2. Producto de los elementos de la diagonal principal<\/a><\/li>\n<li><a href=\"#ej3\">3. Reconocimiento de potencias de 4<\/a><\/li>\n<li><a href=\"#ej4\">4. Exponente en la factorizaci\u00f3n<\/a><\/li>\n<li><a href=\"#ej5\">5. Mayor \u00f3rbita de la sucesi\u00f3n de Collatz<\/a><\/li>\n<li><a href=\"#ej6\">6. M\u00e1ximos locales<\/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. Reiteraci\u00f3n de suma de consecutivos<\/h3>\n<p>La reiteraci\u00f3n de la suma de los elementos consecutivos de la lista [1,5,3] es 14 como se explica en el siguiente diagrama<\/p>\n<pre>\n   1 + 5 = 6\n             \\\n              ==> 14\n             \/\n   5 + 3 = 8\n<\/pre>\n<p>y la de la lista [1,5,3,4] es 29 como se explica en el siguiente diagrama<\/p>\n<pre>\n   1 + 5 = 6\n             \\\n              ==> 14\n             \/       \\\n   5 + 3 = 8          ==> 29\n             \\       \/\n              ==> 15\n             \/\n   3 + 4 = 7\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   sumaReiterada :: Num a => [a] -> a\n<\/pre>\n<p>tal que (sumaReiterada xs) es la suma reiterada de los elementos consecutivos de la lista no vac\u00eda xs. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   sumaReiterada [1,5,3]    ==  14\n   sumaReiterada [1,5,3,4]  ==  29\n<\/pre>\n<p><a name=\"haskell\"><\/a><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Reiteracion_de_suma_de_consecutivos where\n\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada1 :: Num a => [a] -> a\nsumaReiterada1 [x] = x\nsumaReiterada1 xs  = sumaReiterada1 [x+y | (x,y) <- consecutivos xs]\n\n-- (consecutivos xs) es la lista de pares de elementos consecutivos de\n-- xs. Por ejemplo,\n--    consecutivos [1,5,3,4]  ==  [(1,5),(5,3),(3,4)]\nconsecutivos :: [a] -> [(a,a)]\nconsecutivos xs = zip xs (tail xs)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada2 :: Num a => [a] -> a\nsumaReiterada2 [x] = x\nsumaReiterada2 xs  = sumaReiterada2 (sumaConsecutivos xs)\n\n-- (sumaConsecutivos xs) es la suma de los de pares de elementos\n-- consecutivos de xs. Por ejemplo,\n--    sumaConsecutivos [1,5,3,4]   ==  [6,8,7]\nsumaConsecutivos :: Num a => [a] -> [a]\nsumaConsecutivos xs = zipWith (+) xs (tail xs)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada3 :: Num a => [a] -> a\nsumaReiterada3 [x] = x\nsumaReiterada3 xs  = sumaReiterada3 (zipWith (+) xs (tail xs))\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada4 :: Num a => [a] -> a\nsumaReiterada4 [x]    = x\nsumaReiterada4 (x:xs) = sumaReiterada4 (zipWith (+) (x:xs) xs)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada5 :: Num a => [a] -> a\nsumaReiterada5 [x]       = x\nsumaReiterada5 xs@(_:ys) = sumaReiterada5 (zipWith (+) xs ys)\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada6 :: Num a => [a] -> a\nsumaReiterada6 xs =\n  head (head (dropWhile noEsUnitaria (iterate sumaConsecutivos xs)))\n\n-- (noEsUnitaria xs) se verifica si la lista xs no tiene s\u00f3lo un\n-- elemento. Por ejemplo,\n--    noEsUnitaria []     ==  True\n--    noEsUnitaria [7,5]  ==  True\n--    noEsUnitaria [7]    ==  False\nnoEsUnitaria :: [a] -> Bool\nnoEsUnitaria [_] = False\nnoEsUnitaria _   = True\n\n-- 7\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada7 :: Num a => [a] -> a\nsumaReiterada7 =\n  head . head . dropWhile (not . null . tail) . iterate sumaConsecutivos\n\n-- 8\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada8 :: Num a => [a] -> a\nsumaReiterada8 =\n  head . head . dropWhile (not . null . tail) . iterate (zipWith (+) =<< tail)\n\n-- 9\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada9 :: Num a => [a] -> a\nsumaReiterada9 = head . until ((==1) . length) (zipWith (+) <*> tail)\n\n-- 10\u00aa soluci\u00f3n\n-- ===========\n\nsumaReiterada10 :: Num a => [a] -> a\nsumaReiterada10 xs =\n  sum (zipWith (*) xs (map fromIntegral (pascal !! (length xs - 1))))\n\n-- pascal es la lista de las filas del tri\u00e1ngulo de Pascal. Por ejemplo,\n--    \u03bb> take 7 pascal\n--    [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1]]\npascal :: [[Integer]]\npascal = [1] : map f pascal\n  where f xs = zipWith (+) (0:xs) (xs++[0])\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: ([Integer] -> Integer) -> Spec\nspecG sumaReiterada = do\n  it \"e1\" $\n    sumaReiterada [1,5,3] `shouldBe` 14\n  it \"e2\" $\n    sumaReiterada [1,5,3,4] `shouldBe` 29\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG sumaReiterada1\n  describe \"def. 2\" $ specG sumaReiterada2\n  describe \"def. 3\" $ specG sumaReiterada3\n  describe \"def. 4\" $ specG sumaReiterada4\n  describe \"def. 5\" $ specG sumaReiterada5\n  describe \"def. 6\" $ specG sumaReiterada6\n  describe \"def. 7\" $ specG sumaReiterada7\n  describe \"def. 8\" $ specG sumaReiterada8\n  describe \"def. 9\" $ specG sumaReiterada9\n  describe \"def. 10\" $ specG sumaReiterada10\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    20 examples, 0 failures\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_sumaReiterada :: [Integer] -> Property\nprop_sumaReiterada xs =\n  not (null xs) ==>\n  all (== (sumaReiterada1 xs))\n      [f xs | f <- [sumaReiterada2,\n                    sumaReiterada3,\n                    sumaReiterada4,\n                    sumaReiterada5,\n                    sumaReiterada6,\n                    sumaReiterada7,\n                    sumaReiterada8,\n                    sumaReiterada9,\n                    sumaReiterada10 ]]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_sumaReiterada\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (sumaReiterada1 [1..4000]))\n--    1208\n--    (4.84 secs, 4,444,754,000 bytes)\n--    \u03bb> length (show (sumaReiterada2 [1..4000]))\n--    1208\n--    (3.07 secs, 3,332,858,616 bytes)\n--    \u03bb> length (show (sumaReiterada3 [1..4000]))\n--    1208\n--    (3.04 secs, 3,270,112,112 bytes)\n--    \u03bb> length (show (sumaReiterada4 [1..4000]))\n--    1208\n--    (3.05 secs, 3,332,857,768 bytes)\n--    \u03bb> length (show (sumaReiterada5 [1..4000]))\n--    1208\n--    (3.08 secs, 3,332,570,672 bytes)\n--    \u03bb> length (show (sumaReiterada6 [1..4000]))\n--    1208\n--    (3.03 secs, 3,270,469,704 bytes)\n--    \u03bb> length (show (sumaReiterada7 [1..4000]))\n--    1208\n--    (3.03 secs, 3,270,598,416 bytes)\n--    \u03bb> length (show (sumaReiterada8 [1..4000]))\n--    1208\n--    (3.14 secs, 3,202,183,352 bytes)\n--    \u03bb> length (show (sumaReiterada9 [1..4000]))\n--    1208\n--    (3.71 secs, 2,869,137,232 bytes)\n--    \u03bb> length (show (sumaReiterada10 [1..4000]))\n--    1208\n--    (6.48 secs, 4,621,303,752 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><\/p>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# consecutivos(xs) es la lista de pares de elementos consecutivos de\n# xs. Por ejemplo,\n#    consecutivos([1,5,3,4])  ==  [(1,5),(5,3),(3,4)]\ndef consecutivos(xs: list[A]) -> list[tuple[A, A]]:\n    return list(zip(xs, xs[1:]))\n\ndef sumaReiterada1(xs: list[int]) -> int:\n    if len(xs) == 1:\n        return xs[0]\n    return sumaReiterada1([x + y for (x, y) in consecutivos(xs)])\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# sumaConsecutivos(xs) es la suma de los de pares de elementos\n# consecutivos de xs. Por ejemplo,\n#    sumaConsecutivos([1,5,3,4])   ==  [6,8,7]\ndef sumaConsecutivos(xs : list[int]) -> list[int]:\n    return [x + y for (x, y) in list(zip(xs, xs[1:]))]\n\ndef sumaReiterada2(xs: list[int]) -> int:\n    if len(xs) == 1:\n        return xs[0]\n    return sumaReiterada2(sumaConsecutivos(xs))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef sumaReiterada3(xs: list[int]) -> int:\n    if len(xs) == 1:\n        return xs[0]\n    return sumaReiterada3([x + y for (x, y) in list(zip(xs, xs[1:]))])\n\n# Verificaci\u00f3n\n# ============\n\ndef test_sumaReiterada() -> None:\n    for sumaReiterada in [sumaReiterada1, sumaReiterada2,\n                          sumaReiterada3]:\n        assert sumaReiterada([1,5,3]) == 14\n        assert sumaReiterada([1,5,3,4]) == 29\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_sumaReiterada()\n#    Verificado\n\n# Equivalencia de las definiciones\n# ================================\n\n# La propiedad es\n@given(st.lists(st.integers(), min_size=1))\ndef test_sumaReiterada_equiv(xs: list[int]) -> None:\n    r = sumaReiterada1(xs)\n    assert sumaReiterada2(xs) == r\n    assert sumaReiterada3(xs) == r\n\n# La comprobaci\u00f3n es\n#    >>> test_sumaReiterada_equiv()\n#    >>>\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('sumaReiterada1(range(4000))')\n#    2.18 segundos\n#    >>> tiempo('sumaReiterada2(range(4000))')\n#    1.90 segundos\n#    >>> tiempo('sumaReiterada3(range(4000))')\n#    1.97 segundos\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Producto de los elementos de la diagonal principal<\/h3>\n<p>Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   productoDiagonalPrincipal :: Num a => [[a]] -> a\n<\/pre>\n<p>tal que (productoDiagonalPrincipal xss) es el producto de los elementos de la diagonal principal de la matriz cuadrada xss. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   productoDiagonal [[3,5,2],[4,7,1],[6,9,8]]  ==  168\n   productoDiagonal (replicate 5 [1..5])       ==  120\n   length (show (productoDiagonal (replicate 30000 [1..30000])))  ==  121288\n<\/pre>\n<p><a name=\"haskell\"><\/a><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Producto_de_los_elementos_de_la_diagonal_principal where\n\nimport Data.List (genericReplicate)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nproductoDiagonal1 :: Num a => [[a]] -> a\nproductoDiagonal1 xss = product (diagonal1 xss)\n\n-- (diagonal1 xss) es la diagonal de la matriz xss. Por ejemplo,\n--    diagonal1 [[3,5,2],[4,7,1],[6,9,0]]  ==  [3,7,0]\n--    diagonal1 [[3,5],[4,7],[6,9]]        ==  [3,7]\n--    diagonal1 [[3,5,2],[4,7,1]]          ==  [3,7]\ndiagonal1 :: [[a]] -> [a]\ndiagonal1 ((x:_):xss) = x : diagonal1 (map tail xss)\ndiagonal1 _           = []\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nproductoDiagonal2 :: Num a => [[a]] -> a\nproductoDiagonal2 = product . diagonal1\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nproductoDiagonal3 :: Num a => [[a]] -> a\nproductoDiagonal3 = product . diagonal3\n\ndiagonal3 :: [[a]] -> [a]\ndiagonal3 xss = [xs !! k | (xs,k) <- zip xss [0..n]]\n  where n = length (head xss) - 1\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nproductoDiagonal4 :: Num a => [[a]] -> a\nproductoDiagonal4 []          = 1\nproductoDiagonal4 [[]]        = 1\nproductoDiagonal4 ((x:_):xss) = x * productoDiagonal4 (map tail xss)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nproductoDiagonal5 :: Num a => [[a]] -> a\nproductoDiagonal5 xss = product (zipWith (!!) xss [0..k])\n  where m = length xss\n        n = length (head xss)\n        k = min m n - 1\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: ([[Integer]] -> Integer) -> Spec\nspecG productoDiagonal = do\n  it \"e1\" $\n    productoDiagonal [[3,5,2],[4,7,1],[6,9,8]]  `shouldBe`  168\n  it \"e2\" $\n    productoDiagonal (replicate 5 [1..5])       `shouldBe`  120\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG productoDiagonal1\n  describe \"def. 2\" $ specG productoDiagonal2\n  describe \"def. 3\" $ specG productoDiagonal3\n  describe \"def. 4\" $ specG productoDiagonal4\n  describe \"def. 5\" $ specG productoDiagonal5\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    10 examples, 0 failures\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\nejemplo :: Integer -> [[Integer]]\nejemplo n = genericReplicate n [1..n]\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (productoDiagonal1 (ejemplo 7000)))\n--    23878\n--    (1.23 secs, 3,396,129,424 bytes)\n--    \u03bb> length (show (productoDiagonal2 (ejemplo 7000)))\n--    23878\n--    (0.94 secs, 3,396,127,680 bytes)\n--    \u03bb> length (show (productoDiagonal3 (ejemplo 7000)))\n--    23878\n--    (0.09 secs, 44,841,864 bytes)\n--    \u03bb> length (show (productoDiagonal4 (ejemplo 7000)))\n--    23878\n--    (0.96 secs, 3,614,137,840 bytes)\n--    \u03bb> length (show (productoDiagonal5 (ejemplo 7000)))\n--    23878\n--    (0.07 secs, 44,168,984 bytes)\n--\n--    \u03bb> length (show (productoDiagonal3 (ejemplo 70000)))\n--    308760\n--    (8.26 secs, 5,359,752,408 bytes)\n--    \u03bb> length (show (productoDiagonal5 (ejemplo 70000)))\n--    308760\n--    (9.34 secs, 5,353,035,656 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><\/p>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom functools import reduce\nfrom operator import mul\nfrom sys import set_int_max_str_digits, setrecursionlimit\nfrom timeit import Timer, default_timer\n\nset_int_max_str_digits(10**6)\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# diagonal1(xss) es la diagonal de la matriz xss. Por ejemplo,\n#    diagonal1([[3,5,2],[4,7,1],[6,9,0]])  ==  [3,7,0]\n#    diagonal1([[3,5],[4,7],[6,9]])        ==  [3,7]\n#    diagonal1([[3,5,2],[4,7,1]])          ==  [3,7]\ndef diagonal1(xss: list[list[int]]) -> list[int]:\n    if not xss:\n        return []\n    if not xss[0]:\n        return []\n    return [xss[0][0]] + diagonal1(list(map((lambda ys : ys[1:]), xss[1:])))\n\ndef producto(xs: list[int]) -> int:\n    return reduce(mul, xs)\n\ndef productoDiagonal1(xss: list[list[int]]) -> int:\n    return producto(diagonal1(xss))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef diagonal2(xss: list[list[int]]) -> list[int]:\n    n = min(len(xss), len(xss[0]))\n    return [xss[k][k] for k in range(n)]\n\ndef productoDiagonal2(xss: list[list[int]]) -> int:\n    return producto(diagonal2(xss))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef productoDiagonal3(xss: list[list[int]]) -> int:\n    if not xss:\n        return 1\n    if not xss[0]:\n        return 1\n    return xss[0][0] * productoDiagonal3(list(map((lambda ys : ys[1:]), xss[1:])))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_productoDiagonal() -> None:\n    for productoDiagonal in [productoDiagonal1, productoDiagonal2,\n                             productoDiagonal3]:\n        assert productoDiagonal([[3,5,2],[4,7,1],[6,9,8]]) == 168\n        assert productoDiagonal([[1, 2, 3, 4, 5]]*5) == 120\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_productoDiagonal()\n#    Verificado\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\n# ejemplo(n) es la matriz con n filas formadas por los n\u00fameros de 1 a\n# n. Por ejemplo,\n#    >>> ejemplo(3)\n#    [[1, 2, 3], [1, 2, 3], [1, 2, 3]]\ndef ejemplo(n: int) -> list[list[int]]:\n    return [list(range(1, n+1))]*n\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('productoDiagonal1(ejemplo(1200))')\n#    1.97 segundos\n#    >>> tiempo('productoDiagonal2(ejemplo(1200))')\n#    0.00 segundos\n#    >>> tiempo('productoDiagonal3(ejemplo(1200))')\n#    1.56 segundos\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Reconocimiento de potencias de 4<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   esPotenciaDe4 :: Integral a => a -> Bool\n<\/pre>\n<p>tal que (esPotenciaDe4 n) se verifica si n es una potencia de 4. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   esPotenciaDe4 16                ==  True\n   esPotenciaDe4 17                ==  False\n   esPotenciaDe4 (4^(4*10^5))      ==  True\n   esPotenciaDe4 (1 + 4^(4*10^5))  ==  False\n<\/pre>\n<p><a name=\"haskell\"><\/a><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Reconocimiento_de_potencias_de_4 where\n\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_1 :: Integral a => a -> Bool\nesPotenciaDe4_1 0 = False\nesPotenciaDe4_1 1 = True\nesPotenciaDe4_1 n = n `mod` 4 == 0 && esPotenciaDe4_1 (n `div` 4)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_2 :: Integral a => a -> Bool\nesPotenciaDe4_2 n = n `pertenece` potenciasDe4\n\n-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,\n--    take 5 potenciasDe4  ==  [1,4,16,64,256]\npotenciasDe4 :: Integral a => [a]\npotenciasDe4 = [4^x | x <- [0..]]\n\n-- (pertenece x ys) se verifica si x pertenece a la lista ordenada\n-- (posiblemente infinita xs). Por ejemplo,\n--    pertenece 8 [2,4..]  ==  True\n--    pertenece 9 [2,4..]  ==  False\npertenece :: Integral a => a -> [a] -> Bool\npertenece x ys = x == head (dropWhile (<x) ys)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_3 :: Integral a => a -> Bool\nesPotenciaDe4_3 n = n `pertenece` potenciasDe4_2\n\n-- potenciassDe4 es la lista de las potencias de 4. Por ejemplo,\n--    take 5 potenciasDe4  ==  [1,4,16,64,256]\npotenciasDe4_2 :: Integral a => [a]\npotenciasDe4_2 = iterate (*4) 1\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_4 :: Integral n => n -> Bool\nesPotenciaDe4_4 n =\n  n == head (dropWhile (<n) (iterate (*4) 1))\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nesPotenciaDe4_5 :: Integral n => n -> Bool\nesPotenciaDe4_5 n =\n  n == until (>=n) (*4) 1\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> Bool) -> Spec\nspecG esPotenciaDe4 = do\n  it \"e1\" $\n    esPotenciaDe4 16 `shouldBe` True\n  it \"e2\" $\n    esPotenciaDe4 17 `shouldBe` False\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG esPotenciaDe4_1\n  describe \"def. 2\" $ specG esPotenciaDe4_2\n  describe \"def. 3\" $ specG esPotenciaDe4_3\n  describe \"def. 4\" $ specG esPotenciaDe4_4\n  describe \"def. 5\" $ specG esPotenciaDe4_5\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    10 examples, 0 failures\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> esPotenciaDe4_1 (4^(4*10^4))\n--    True\n--    (0.18 secs, 233,903,248 bytes)\n--    \u03bb> esPotenciaDe4_2 (4^(4*10^4))\n--    True\n--    (2.01 secs, 756,125,712 bytes)\n--    \u03bb> esPotenciaDe4_3 (4^(4*10^4))\n--    True\n--    (0.05 secs, 212,019,464 bytes)\n--    \u03bb> esPotenciaDe4_4 (4^(4*10^4))\n--    True\n--    (0.05 secs, 212,019,368 bytes)\n--    \u03bb> esPotenciaDe4_5 (4^(4*10^4))\n--    True\n--    (0.07 secs, 209,779,888 bytes)\n--\n--    \u03bb> esPotenciaDe4_3 (4^(2*10^5))\n--    True\n--    (0.64 secs, 5,184,667,280 bytes)\n--    \u03bb> esPotenciaDe4_4 (4^(2*10^5))\n--    True\n--    (0.64 secs, 5,184,667,200 bytes)\n--    \u03bb> esPotenciaDe4_5 (4^(2*10^5))\n--    True\n--    (0.63 secs, 5,173,467,656 bytes)\n--\n--    \u03bb> esPotenciaDe4_3 (4^(4*10^5))\n--    True\n--    (2.27 secs, 20,681,727,464 bytes)\n--    \u03bb> esPotenciaDe4_4 (4^(4*10^5))\n--    True\n--    (2.30 secs, 20,681,727,320 bytes)\n--    \u03bb> esPotenciaDe4_5 (4^(4*10^5))\n--    True\n--    (2.28 secs, 20,659,327,352 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><\/p>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom itertools import count, dropwhile, islice\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Callable, Iterator\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef esPotenciaDe4_1(n: int) -> bool:\n    if n == 0:\n        return False\n    if n == 1:\n        return True\n    return n % 4 == 0 and esPotenciaDe4_1(n \/\/ 4)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# potenciassDe4() es la lista de las potencias de 4. Por ejemplo,\n#    >>> list(islice(potenciasDe4(), 5))\n#    [1, 4, 16, 64, 256]\ndef potenciasDe4() -> Iterator[int]:\n    return (4 ** n for n in count())\n\n# pertenece(x, ys) se verifica si x pertenece a la lista ordenada\n# (posiblemente infinita xs). Por ejemplo,\n#    >>> pertenece(8, count(2, 2))\n#    True\n#    >>> pertenece(9, count(2, 2))\n#    False\ndef pertenece(x: int, ys: Iterator[int]) -> bool:\n    return next(dropwhile(lambda y: y < x, ys), None) == x\n\ndef esPotenciaDe4_2(n: int) -> bool:\n    return pertenece(n, potenciasDe4())\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\n# iterate(f, x) es el iterador obtenido aplicando f a x y continuando\n# aplicando f al resultado anterior. Por ejemplo,\n#    >>> list(islice(iterate(lambda x : 4 * x, 1), 5))\n#    [1, 4, 16, 64, 256]\ndef iterate(f: Callable[[int], int], x: int) -> Iterator[int]:\n    r = x\n    while True:\n        yield r\n        r = f(r)\n\ndef potenciasDe4_2() -> Iterator[int]:\n    return iterate(lambda x : 4 * x, 1)\n\ndef esPotenciaDe4_3(n: int) -> bool:\n    return pertenece(n, potenciasDe4_2())\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef esPotenciaDe4_4(n: int) -> bool:\n    return next(dropwhile(lambda y: y < n,\n                          iterate(lambda x : 4 * x, 1)),\n                          None) == n\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef esPotenciaDe4_5(n: int) -> bool:\n    r = 1\n    while r < n:\n        r = 4 * r\n    return r == n\n\n# Verificaci\u00f3n\n# ============\n\ndef test_esPotenciaDe4() -> None:\n    for esPotenciaDe4 in [esPotenciaDe4_1, esPotenciaDe4_2,\n                          esPotenciaDe4_3, esPotenciaDe4_4,\n                          esPotenciaDe4_5]:\n        assert esPotenciaDe4(16)\n        assert not esPotenciaDe4(17)\n    assert list(islice(potenciasDe4(), 5)) == [1, 4, 16, 64, 256]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_esPotenciaDe4()\n#    Verificado\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('esPotenciaDe4_1(4**(2*10**4))')\n#    0.33 segundos\n#    >>> tiempo('esPotenciaDe4_2(4**(2*10**4))')\n#    0.63 segundos\n#    >>> tiempo('esPotenciaDe4_3(4**(2*10**4))')\n#    0.04 segundos\n#    >>> tiempo('esPotenciaDe4_4(4**(2*10**4))')\n#    0.05 segundos\n#    >>> tiempo('esPotenciaDe4_5(4**(2*10**4))')\n#    0.04 segundos\n#\n#    >>> tiempo('esPotenciaDe4_3(4**(3*10**5))')\n#    2.29 segundos\n#    >>> tiempo('esPotenciaDe4_4(4**(3*10**5))')\n#    2.28 segundos\n#    >>> tiempo('esPotenciaDe4_5(4**(3*10**5))')\n#    2.31 segundos\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Exponente en la factorizaci\u00f3n<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   exponente :: Integer -> Integer -> Int\n<\/pre>\n<p>tal que (exponente x n) es el exponente de x en la factorizaci\u00f3n prima de n (se supone que x > 1 y n > 0). Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   exponente 2 24  ==  3\n   exponente 3 24  ==  1\n   exponente 6 24  ==  0\n   exponente 7 24  ==  0\n<\/pre>\n<p><a name=\"haskell\"><\/a><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Exponente_en_la_factorizacion where\n\nimport Data.Numbers.Primes (primeFactors)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nexponente1 :: Integer -> Integer -> Int\nexponente1 x n\n  | esPrimo x = aux n\n  | otherwise = 0\n  where aux m | m `mod` x == 0 = 1 + aux (m `div` x)\n              | otherwise      = 0\n\n-- (esPrimo x) se verifica si x es un n\u00famero primo. Por ejemplo,\n--    esPrimo 7  ==  True\n--    esPrimo 8  ==  False\nesPrimo :: Integer -> Bool\nesPrimo x =\n  [y | y <- [1..x], x `mod` y == 0] == [1,x]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nexponente2 :: Integer -> Integer -> Int\nexponente2 x n\n  | esPrimo x = length (takeWhile (`divisible` x) (iterate (`div` x) n))\n  | otherwise = 0\n\n-- (divisible n x) se verifica si n es divisible por x. Por ejemplo,\n--    divisible 6 2  ==  True\n--    divisible 7 2  ==  False\ndivisible :: Integer -> Integer -> Bool\ndivisible n x = n `mod` x == 0\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nexponente3 :: Integer -> Integer -> Int\nexponente3 x n =\n  length (filter (==x) (primeFactors n))\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> Integer -> Int) -> Spec\nspecG exponente = do\n  it \"e1\" $\n    exponente 2 24  `shouldBe`  3\n  it \"e2\" $\n    exponente 3 24  `shouldBe`  1\n  it \"e3\" $\n    exponente 6 24  `shouldBe`  0\n  it \"e4\" $\n    exponente 7 24  `shouldBe`  0\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG exponente1\n  describe \"def. 2\" $ specG exponente2\n  describe \"def. 3\" $ specG exponente3\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    12 examples, 0 failures\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_exponente :: Integer -> Integer -> Property\nprop_exponente x n =\n  x > 1 && n > 0 ==>\n  exponente1 x n == exponente2 x n &&\n  exponente1 x n == exponente3 x n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_exponente\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><\/p>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom itertools import takewhile\nfrom typing import Callable, Iterator\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\nfrom sympy.ntheory import factorint\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# esPrimo(x) se verifica si x es un n\u00famero primo. Por ejemplo,\n#    esPrimo(7)  ==  True\n#    esPrimo(8)  ==  False\ndef esPrimo(x: int) -> bool:\n    return [y for y in range(1, x+1) if x % y == 0] == [1,x]\n\ndef exponente1(x: int, n: int) -> int:\n    def aux (m: int) -> int:\n        if m % x == 0:\n            return 1 + aux(m \/\/ x)\n        return 0\n    if esPrimo(x):\n        return aux(n)\n    return 0\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# iterate(f, x) es el iterador obtenido aplicando f a x y continuando\n# aplicando f al resultado anterior. Por ejemplo,\n#    >>> list(islice(iterate(lambda x : 4 * x, 1), 5))\n#    [1, 4, 16, 64, 256]\ndef iterate(f: Callable[[int], int], x: int) -> Iterator[int]:\n    r = x\n    while True:\n        yield r\n        r = f(r)\n\n# divisible(n, x) se verifica si n es divisible por x. Por ejemplo,\n#    divisible(6, 2)  ==  True\n#    divisible(7, 2)  ==  False\ndef divisible(n: int, x: int) -> bool:\n    return n % x == 0\n\ndef exponente2(x: int, n: int) -> int:\n    if esPrimo(x):\n        return len(list(takewhile(lambda m : divisible(m, x),\n                                  iterate(lambda m : m \/\/ x, n))))\n    return 0\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef exponente3(x: int, n: int) -> int:\n    return factorint(n, multiple = True).count(x)\n\n# Verificaci\u00f3n\n# ============\n\ndef test_exponente() -> None:\n    for exponente in [exponente1, exponente2, exponente3]:\n        assert exponente(2, 24) == 3\n        assert exponente(3, 24) == 1\n        assert exponente(6, 24) == 0\n        assert exponente(7, 24) == 0\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_exponente()\n#    Verificado\n\n# Equivalencia de las definiciones\n# ================================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000),\n       st.integers(min_value=0, max_value=1000))\ndef test_exponente_equiv(x: int, n: int) -> None:\n    r = exponente1(x, n)\n    assert r == exponente2(x, n)\n    assert r == exponente3(x, n)\n\n# La comprobaci\u00f3n es\n#    >>> test_exponente_equiv()\n#    >>>\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Mayor \u00f3rbita de la sucesi\u00f3n de Collatz<\/h3>\n<p>Se considera la siguiente operaci\u00f3n, aplicable a cualquier n\u00famero entero positivo:<\/p>\n<ul>\n<li>Si el n\u00famero es par, se divide entre 2.<\/li>\n<li>Si el n\u00famero es impar, se multiplica por 3 y se suma 1.<\/li>\n<\/ul>\n<p>Dado un n\u00famero cualquiera, podemos calcular su \u00f3rbita; es decir, las im\u00e1genes sucesivas al iterar la funci\u00f3n. Por ejemplo, la \u00f3rbita de 13 es<\/p>\n<pre lang=\"haskell\">\n   13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...\n<\/pre>\n<p>Si observamos este ejemplo, la \u00f3rbita de 13 es peri\u00f3dica, es decir,<br \/>\nse repite indefinidamente a partir de un momento dado). La conjetura<br \/>\nde Collatz dice que siempre alcanzaremos el 1 para cualquier n\u00famero<br \/>\ncon el que comencemos. Ejemplos:<\/p>\n<ul>\n<li>Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.<\/li>\n<li>Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.<\/li>\n<li>Empezando en n = 27, la sucesi\u00f3n tiene 112 pasos, llegando hasta<br \/>\n9232 antes de descender a 1:  27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   mayoresGeneradores :: Integer -> [Integer]\n<\/pre>\n<p>tal que (mayoresGeneradores n) es la lista de los n\u00fameros menores o iguales que n cuyas \u00f3rbitas de Collatz son las de mayor longitud. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   mayoresGeneradores 20      ==  [18,19]\n   mayoresGeneradores (10^6)  ==  [837799]\n<\/pre>\n<p><a name=\"haskell\"><\/a><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Mayor_orbita_de_la_sucesion_de_Collatz where\n\nimport qualified Data.MemoCombinators as Memo (integral)\nimport Data.List (genericLength, genericTake)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores1 :: Integer -> [Integer]\nmayoresGeneradores1 n =\n  [x | (x,y) <- ps, y == m]\n  where ps = genericTake n longitudesOrbitas\n        m  = maximum (map snd ps)\n\n-- longitudesOrbita es la lista de los n\u00fameros junto a las longitudes de\n-- las \u00f3rbitas de Collatz que generan. Por ejemplo,\n--    \u03bb> take 10 longitudesOrbitas\n--    [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]\nlongitudesOrbitas :: [(Integer, Integer)]\nlongitudesOrbitas =\n  [(n, genericLength (collatz n)) | n <- [1..]]\n\n-- (siguiente n) es el siguiente de n en la sucesi\u00f3n de Collatz. Por\n-- ejemplo,\n--    siguiente 13  ==  40\n--    siguiente 40  ==  20\nsiguiente :: Integer -> Integer\nsiguiente n | even n    = n `div` 2\n            | otherwise = 3*n+1\n\n-- (collatz1 n) es la \u00f3rbita de Collatz de n hasta alcanzar el\n-- 1. Por ejemplo,\n--    collatz 13  ==  [13,40,20,10,5,16,8,4,2,1]\n\n-- 1\u00aa definici\u00f3n de collatz\ncollatz1 :: Integer -> [Integer]\ncollatz1 1 = [1]\ncollatz1 n = n : collatz1 (siguiente n)\n\n-- 2\u00aa definici\u00f3n de collatz\ncollatz2 :: Integer -> [Integer]\ncollatz2 n = takeWhile (\/=1) (iterate siguiente n) ++ [1]\n\n-- Usaremos la 2\u00aa definici\u00f3n de collatz\ncollatz :: Integer -> [Integer]\ncollatz = collatz2\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores2 :: Integer -> [Integer]\nmayoresGeneradores2 n =\n  [x | (x,y) <- ps, y == m]\n  where ps = [(x, longitudOrbita x) | x <- [1..n]]\n        m  = maximum (map snd ps)\n\n-- (longitudOrbita x) es la longitud de la \u00f3rbita de x. Por ejemplo,\n--    longitudOrbita 13  ==  10\nlongitudOrbita :: Integer -> Integer\nlongitudOrbita 1 = 1\nlongitudOrbita x = 1 + longitudOrbita (siguiente x)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmayoresGeneradores3 :: Integer -> [Integer]\nmayoresGeneradores3 n =\n  [x | (x,y) <- ps, y == m]\n  where ps = [(x, longitudOrbita2 x) | x <- [1..n]]\n        m  = maximum (map snd ps)\n\nlongitudOrbita2 :: Integer -> Integer\nlongitudOrbita2 = Memo.integral longitudOrbita2'\n  where\n    longitudOrbita2' 1 = 1\n    longitudOrbita2' x = 1 + longitudOrbita2 (siguiente x)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: (Integer -> [Integer]) -> Spec\nspecG mayoresGeneradores = do\n  it \"e1\" $\n    mayoresGeneradores 20 `shouldBe` [18,19]\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG mayoresGeneradores1\n  describe \"def. 2\" $ specG mayoresGeneradores2\n  describe \"def. 3\" $ specG mayoresGeneradores3\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    3 examples, 0 failures\n\n-- Equivalencia de definiciones\n-- ============================\n\n-- La propiedad es\nprop_mayoresGeneradores :: Positive Integer -> Bool\nprop_mayoresGeneradores (Positive n) =\n  all (== mayoresGeneradores1 n)\n      [mayoresGeneradores2 n,\n       mayoresGeneradores3 n]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_mayoresGeneradores\n--    +++ OK, passed 100 tests.\n\n-- Comprobaci\u00f3n de eficiencia\n-- ==========================\n\n-- La comprobaci\u00f3n es\n--    \u03bb> mayoresGeneradores (10^5)\n--    [77031]\n--    (5.43 secs, 6,232,320,064 bytes)\n--    \u03bb> mayoresGeneradores2 (10^5)\n--    [77031]\n--    (7.68 secs, 5,238,991,616 bytes)\n--    \u03bb> mayoresGeneradores3 (10^5)\n--    [77031]\n--    (0.88 secs, 571,788,736 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><\/p>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom functools import lru_cache\nfrom itertools import count, islice\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# siguiente(n) es el siguiente de n en la sucesi\u00f3n de Collatz. Por\n# ejemplo,\n#    siguiente(13)  ==  40\n#    siguiente(40)  ==  20\ndef siguiente (n: int) -> int:\n    if n % 2 == 0:\n        return n \/\/ 2\n    return 3*n+1\n\n# collatz1(n) es la \u00f3rbita de Collatz de n hasta alcanzar el\n# 1. Por ejemplo,\n#    collatz1(13)  ==  [13,40,20,10,5,16,8,4,2,1]\ndef collatz1(n: int) -> list[int]:\n    if n == 1:\n        return [1]\n    return [n]+ collatz1(siguiente(n))\n\n# longitudesOrbita() es la lista de los n\u00fameros junto a las longitudes de\n# las \u00f3rbitas de Collatz que generan. Por ejemplo,\n#    >>> list(islice(longitudesOrbitas(), 10))\n#    [(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]\ndef longitudesOrbitas() -> Iterator[tuple[int, int]]:\n    return ((n, len(collatz1(n))) for n in count(1))\n\ndef mayoresGeneradores1(n: int) -> list[int]:\n    ps = list(islice(longitudesOrbitas(), n))\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef collatz2(n: int) -> list[int]:\n    r = [n]\n    while n != 1:\n        n = siguiente(n)\n        r.append(n)\n    return r\n\ndef longitudesOrbitas2() -> Iterator[tuple[int, int]]:\n    return ((n, len(collatz2(n))) for n in count(1))\n\ndef mayoresGeneradores2(n: int) -> list[int]:\n    ps = list(islice(longitudesOrbitas2(), n))\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\n# longitudOrbita(x) es la longitud de la \u00f3rbita de x. Por ejemplo,\n#    longitudOrbita(13)  ==  10\ndef longitudOrbita(x: int) -> int:\n    if x == 1:\n        return 1\n    return 1 + longitudOrbita(siguiente(x))\n\ndef mayoresGeneradores3(n: int) -> list[int]:\n    ps = [(x, longitudOrbita(x)) for x in range(1, n+1)]\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\n# longitudOrbita2(x) es la longitud de la \u00f3rbita de x. Por ejemplo,\n#    longitudOrbita2(13)  ==  10\ndef longitudOrbita2(x: int) -> int:\n    r = 0\n    while x != 1:\n        x = siguiente(x)\n        r += 1\n    return r + 1\n\ndef mayoresGeneradores4(n: int) -> list[int]:\n    ps = [(x, longitudOrbita2(x)) for x in range(1, n+1)]\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\n@lru_cache(maxsize=None)\ndef longitudOrbita3(x: int) -> int:\n    if x == 1:\n        return 1\n    return 1 + longitudOrbita3(siguiente(x))\n\ndef mayoresGeneradores5(n: int) -> list[int]:\n    ps = [(x, longitudOrbita3(x)) for x in range(1, n+1)]\n    m = max((y for (_, y) in ps))\n    return [x for (x,y) in ps if y == m]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_mayoresGeneradores() -> None:\n    for mayoresGeneradores in [mayoresGeneradores1,\n                               mayoresGeneradores2,\n                               mayoresGeneradores3,\n                               mayoresGeneradores4,\n                               mayoresGeneradores5]:\n        assert mayoresGeneradores(20) == [18,19]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_mayoresGeneradores()\n#    Verificado\n\n# Equivalencia de definiciones\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=1000))\ndef test_mayoresGeneradores_equiv(n: int) -> None:\n    r = mayoresGeneradores1(n)\n    assert mayoresGeneradores2(n) == r\n    assert mayoresGeneradores3(n) == r\n\n# La comprobaci\u00f3n es\n#    >>> test_mayoresGeneradores_equiv()\n#    >>>\n\n# Comprobaci\u00f3n de eficiencia\n# ==========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comprobaci\u00f3n es\n#    >>> tiempo('mayoresGeneradores1(10**5)')\n#    4.08 segundos\n#    >>> tiempo('mayoresGeneradores2(10**5)')\n#    1.95 segundos\n#    >>> tiempo('mayoresGeneradores3(10**5)')\n#    2.16 segundos\n#    >>> tiempo('mayoresGeneradores4(10**5)')\n#    1.71 segundos\n#    >>> tiempo('mayoresGeneradores5(10**5)')\n#    0.14 segundos\n<\/pre>\n<p><a name=\"ej6\"><\/a><\/p>\n<h3>6. M\u00e1ximos locales<\/h3>\n<p>Un m\u00e1ximo local de una lista es un elemento de la lista que es mayor que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un m\u00e1ximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   maximosLocales :: Ord a => [a] -> [a]\n<\/pre>\n<p>tal que (maximosLocales xs) es la lista de los m\u00e1ximos locales de la lista xs. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   maximosLocales [3,2,5,3,7,7,1,6,2]  ==  [5,6]\n   maximosLocales [1..100]             ==  []\n   maximosLocales \"adbpmqexyz\"         ==  \"dpq\"\n<\/pre>\n<p><a name=\"haskell\"><\/a><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Maximos_locales where\n\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmaximosLocales1 :: Ord a => [a] -> [a]\nmaximosLocales1 (x:y:z:xs)\n  | y > x && y > z = y : maximosLocales1 (z:xs)\n  | otherwise      = maximosLocales1 (y:z:xs)\nmaximosLocales1 _ = []\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmaximosLocales2 :: Ord a => [a] -> [a]\nmaximosLocales2 xs =\n  [y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y > x, y > z]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: ([Int] -> [Int]) -> Spec\nspecG maximosLocales = do\n  it \"e1\" $\n    maximosLocales [3,2,5,3,7,7,1,6,2]  `shouldBe`  [5,6]\n  it \"e2\" $\n    maximosLocales [1..100]             `shouldBe`  []\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG maximosLocales1\n  describe \"def. 2\" $ specG maximosLocales2\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    4 examples, 0 failures\n\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_maximosLocales :: [Int] -> Property\nprop_maximosLocales xs =\n  maximosLocales1 xs === maximosLocales2 xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_maximosLocales\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> last (maximosLocales1 (take (6*10^6) (cycle \"abc\")))\n--    'c'\n--    (3.26 secs, 1,904,464,984 bytes)\n--    \u03bb> last (maximosLocales2 (take (6*10^6) (cycle \"abc\")))\n--    'c'\n--    (2.79 secs, 1,616,465,088 bytes)\n<\/pre>\n<p><a name=\"python\"><\/a><\/p>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef maximosLocales1(xs: list[int]) -> list[int]:\n    if len(xs) < 3:\n        return []\n    x, y, z, *ys = xs\n    if y > x and y > z:\n        return [y] + maximosLocales1([z] + ys)\n    return maximosLocales1([y, z] + ys)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef maximosLocales2(xs: list[int]) -> list[int]:\n    ys: list[int] = []\n    if len(xs) < 3:\n        return ys\n    for i in range(1, len(xs) - 1):\n        if xs[i] > xs[i - 1] and xs[i] > xs[i + 1]:\n            ys.append(xs[i])\n    return ys\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef maximosLocales3(xs: list[int]) -> list[int]:\n    return [y for x, y, z in zip(xs, xs[1:], xs[2:]) if y > x and y > z]\n\n# Verificaci\u00f3n\n# ============\n\ndef test_maximosLocales() -> None:\n    for maximosLocales in [maximosLocales1,\n                           maximosLocales2,\n                           maximosLocales3]:\n        assert maximosLocales([3,2,5,3,7,7,1,6,2]) == [5,6]\n        assert maximosLocales(list(range(0, 100))) == []\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_maximosLocales()\n#    Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers()))\ndef test_maximosLocales_equiv(xs: list[int]) -> None:\n    r = maximosLocales1(xs)\n    assert maximosLocales2(xs) == r\n    assert maximosLocales3(xs) == r\n\n# La comprobaci\u00f3n es\n#    >>> test_maximosLocales_equiv()\n#    >>>\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('maximosLocales1([1,2,3]*(10**4))')\n#    3.19 segundos\n#    >>> tiempo('maximosLocales2([1,2,3]*(10**4))')\n#    0.01 segundos\n#    >>> tiempo('maximosLocales3([1,2,3]*(10**4))')\n#    0.01 segundos\n#\n#    >>> tiempo('maximosLocales2([1,2,3]*(10**7))')\n#    3.95 segundos\n#    >>> tiempo('maximosLocales3([1,2,3]*(10**7))')\n#    1.85 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Durante el mes de marzo he publicado en Exercitium las soluciones de los siguientes problemas: 1. Reiteraci\u00f3n de suma de consecutivos 2. Producto de los elementos de la diagonal principal 3. Reconocimiento de potencias de 4 4. Exponente en la factorizaci\u00f3n 5. Mayor \u00f3rbita de la sucesi\u00f3n de Collatz 6. M\u00e1ximos locales A continuaci\u00f3n se&#8230;<\/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":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_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\/8171"}],"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=8171"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8171\/revisions"}],"predecessor-version":[{"id":8172,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/8171\/revisions\/8172"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=8171"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=8171"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=8171"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}