{"id":7834,"date":"2022-11-05T11:29:13","date_gmt":"2022-11-05T10:29:13","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7834"},"modified":"2022-11-05T11:34:19","modified_gmt":"2022-11-05T10:34:19","slug":"pfh-la-semana-en-exercitium-4-de-noviembre-de-2022","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-4-de-noviembre-de-2022\/","title":{"rendered":"PFH: La semana en Exercitium (4 de noviembre de 2022)"},"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. N\u00famero a partir de sus d\u00edgitos<\/a><\/li>\n<li><a href=\"#ej2\">2. Exponente de la mayor potencia de x que divide a y<\/a><\/li>\n<li><a href=\"#ej3\">3. Producto cartesiano de dos conjuntos<\/a><\/li>\n<li><a href=\"#ej4\">4. Subconjuntos de un conjunto<\/a><\/li>\n<li><a href=\"#ej5\">5. El algoritmo de Luhn<\/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. N\u00famero a partir de sus d\u00edgitos<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   listaNumero :: [Integer] -> Integer\n<\/pre>\n<p>tal que <code>listaNumero xs<\/code> es el n\u00famero formado por los d\u00edgitos <code>xs<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   listaNumero [5]        == 5\n   listaNumero [1,3,4,7]  == 1347\n   listaNumero [0,0,1]    == 1\n<\/pre>\n<p><b>1.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Data.List (foldl')\nimport Data.Digits (unDigits)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nlistaNumero1 :: [Integer] -> Integer\nlistaNumero1 = aux . reverse\n  where\n    aux :: [Integer] -> Integer\n    aux []     = 0\n    aux (x:xs) = x + 10 * aux xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nlistaNumero2 :: [Integer] -> Integer\nlistaNumero2 = aux 0\n  where\n    aux :: Integer -> [Integer] -> Integer\n    aux r []     = r\n    aux r (x:xs) = aux (x+10*r) xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nlistaNumero3 :: [Integer] -> Integer\nlistaNumero3 = aux 0\n  where\n    aux :: Integer -> [Integer] -> Integer\n    aux = foldl (\\ r x -> x + 10 * r)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nlistaNumero4 :: [Integer] -> Integer\nlistaNumero4 = foldl' (\\ r x -> x + 10 * r) 0\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nlistaNumero5 :: [Integer] -> Integer\nlistaNumero5 xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nlistaNumero6 :: [Integer] -> Integer\nlistaNumero6 xs = sum (zipWith (\\ y n -> y*10^n) (reverse xs) [0..])\n\n-- 7\u00aa soluci\u00f3n\n-- ===========\n\nlistaNumero7 :: [Integer] -> Integer\nlistaNumero7 = unDigits 10\n\n-- 7\u00aa soluci\u00f3n\n-- ===========\n\nlistaNumero8 :: [Integer] -> Integer\nlistaNumero8 = read . concatMap show\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_listaNumero :: NonEmptyList Integer -> Bool\nprop_listaNumero (NonEmpty xs) =\n  all (== listaNumero1 ys)\n      [listaNumero2 ys,\n       listaNumero3 ys,\n       listaNumero4 ys,\n       listaNumero5 ys,\n       listaNumero6 ys,\n       listaNumero7 ys,\n       listaNumero8 ys]\n  where ys = map (`mod` 10) xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_listaNumero\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (show (listaNumero1 (replicate (10^5) 9)))\n--    100000\n--    (4.01 secs, 4,309,740,064 bytes)\n--    \u03bb> length (show (listaNumero2 (replicate (10^5) 9)))\n--    100000\n--    (4.04 secs, 4,307,268,856 bytes)\n--    \u03bb> length (show (listaNumero3 (replicate (10^5) 9)))\n--    100000\n--    (4.08 secs, 4,300,868,816 bytes)\n--    \u03bb> length (show (listaNumero4 (replicate (10^5) 9)))\n--    100000\n--    (0.42 secs, 4,288,480,208 bytes)\n--    \u03bb> length (show (listaNumero4 (replicate (10^5) 9)))\n--    100000\n--    (0.41 secs, 4,288,480,208 bytes)\n--    \u03bb> length (show (listaNumero5 (replicate (10^5) 9)))\n--    100000\n--    (43.35 secs, 10,702,827,328 bytes)\n--    \u03bb> length (show (listaNumero6 (replicate (10^5) 9)))\n--    100000\n--    (46.89 secs, 10,693,227,280 bytes)\n--    \u03bb> length (show (listaNumero7 (replicate (10^5) 9)))\n--    100000\n--    (4.33 secs, 4,297,499,344 bytes)\n--    \u03bb> length (show (listaNumero8 (replicate (10^5) 9)))\n--    100000\n--    (0.03 secs, 60,760,360 bytes)\n<\/pre>\n<p><b>1.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom functools import reduce\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 listaNumero1(xs: list[int]) -> int:\n    def aux(ys: list[int]) -> int:\n        if ys:\n            return ys[0] + 10 * aux(ys[1:])\n        return 0\n    return aux(list(reversed(xs)))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef listaNumero2(xs: list[int]) -> int:\n    def aux(r: int, ys: list[int]) -> int:\n        if ys:\n            return aux(ys[0] + 10 * r, ys[1:])\n        return r\n    return aux(0, xs)\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef listaNumero3(xs: list[int]) -> int:\n    return reduce((lambda r, x: x + 10 * r), xs)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef listaNumero4(xs: list[int]) -> int:\n    r = 0\n    for x in xs:\n        r = x + 10 * r\n    return r\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef listaNumero5(xs: list[int]) -> int:\n    return sum((y * 10**n\n                for (y, n) in zip(list(reversed(xs)), range(0, len(xs)))))\n\n# 6\u00aa soluci\u00f3n\n# ===========\n\ndef listaNumero6(xs: list[int]) -> int:\n    return int(\"\".join(list(map(str, xs))))\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers(min_value=0, max_value=9), min_size=1))\ndef test_listaNumero(xs: list[int]) -> None:\n    r = listaNumero1(xs)\n    assert listaNumero2(xs) == r\n    assert listaNumero3(xs) == r\n    assert listaNumero4(xs) == r\n    assert listaNumero5(xs) == r\n    assert listaNumero6(xs) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q numero_a_partir_de_sus_digitos.py\n#    1 passed in 0.27s\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('listaNumero1([9]*(10**4))')\n#    0.28 segundos\n#    >>> tiempo('listaNumero2([9]*(10**4))')\n#    0.16 segundos\n#    >>> tiempo('listaNumero3([9]*(10**4))')\n#    0.01 segundos\n#    >>> tiempo('listaNumero4([9]*(10**4))')\n#    0.01 segundos\n#    >>> tiempo('listaNumero5([9]*(10**4))')\n#    0.41 segundos\n#    >>> tiempo('listaNumero6([9]*(10**4))')\n#    0.00 segundos\n#\n#    >>> tiempo('listaNumero3([9]*(2*10**5))')\n#    3.45 segundos\n#    >>> tiempo('listaNumero4([9]*(2*10**5))')\n#    3.29 segundos\n#    >>> tiempo('listaNumero6([9]*(2*10**5))')\n#    0.19 segundos\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Exponente de la mayor potencia de x que divide a y<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   mayorExponente :: Integer -> Integer -> Integer\n<\/pre>\n<p>tal que <code>mayorExponente a b<\/code> es el exponente de la mayor potencia de <code>a<\/code> que divide a <code>b<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   mayorExponente 2 8    ==  3\n   mayorExponente 2 9    ==  0\n   mayorExponente 5 100  ==  2\n   mayorExponente 2 60   ==  2\n<\/pre>\n<p>Nota: Se supone que a > 1 y b > 0.<\/p>\n<p><b>2.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmayorExponente1 :: Integer -> Integer -> Integer\nmayorExponente1 a b\n  | rem b a \/= 0 = 0\n  | otherwise    = 1 + mayorExponente1 a (b `div` a)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmayorExponente2 :: Integer -> Integer -> Integer\nmayorExponente2 a b = aux b 0\n  where\n    aux c r | rem c a \/= 0 = r\n            | otherwise    = aux (c `div` a) (r + 1)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmayorExponente3 :: Integer -> Integer -> Integer\nmayorExponente3 a b = head [x-1 | x <- [0..], mod b (a^x) \/= 0]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nmayorExponente4 :: Integer -> Integer -> Integer\nmayorExponente4 a b =\n  fst (until (\\ (_,c) -> rem c a \/= 0)\n             (\\ (r,c) -> (r+1, c `div` a))\n             (0,b))\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_mayorExponente :: Integer -> Integer -> Property\nprop_mayorExponente a b =\n  a > 1 && b > 0 ==>\n  all (== mayorExponente1 a b)\n      [mayorExponente2 a b,\n       mayorExponente3 a b,\n       mayorExponente4 a b]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_mayorExponente\n--    +++ OK, passed 100 tests; 457 discarded.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> mayorExponente1 2 (2^(5*10^4))\n--    50000\n--    (0.12 secs, 179,578,424 bytes)\n--    \u03bb> mayorExponente2 2 (2^(5*10^4))\n--    50000\n--    (0.13 secs, 181,533,376 bytes)\n--    \u03bb> mayorExponente3 2 (2^(5*10^4))\n--    50000\n--    (3.88 secs, 818,319,096 bytes)\n--    \u03bb> mayorExponente4 2 (2^(5*10^4))\n--    50000\n--    (0.13 secs, 181,133,344 bytes)\n--\n--    \u03bb> mayorExponente1 2 (2^(3*10^5))\n--    300000\n--    (2.94 secs, 5,762,199,064 bytes)\n--    \u03bb> mayorExponente2 2 (2^(3*10^5))\n--    300000\n--    (2.91 secs, 5,773,829,624 bytes)\n--    \u03bb> mayorExponente4 2 (2^(3*10^5))\n--    300000\n--    (3.70 secs, 5,771,396,824 bytes)\n<\/pre>\n<p><b>2.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom itertools import islice\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import Iterator\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef mayorExponente1(a: int, b: int) -> int:\n    if b % a != 0:\n        return 0\n    return 1 + mayorExponente1(a, b \/\/ a)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef mayorExponente2(a: int, b: int) -> int:\n    def aux(c: int, r: int) -> int:\n        if c % a != 0:\n            return r\n        return aux(c \/\/ a, r + 1)\n    return aux(b, 0)\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\n# naturales es el generador de los n\u00fameros naturales, Por ejemplo,\n#    >>> list(islice(naturales(), 5))\n#    [0, 1, 2, 3, 4]\ndef naturales() -> Iterator[int]:\n    i = 0\n    while True:\n        yield i\n        i += 1\n\ndef mayorExponente3(a: int, b: int) -> int:\n    return list(islice((x - 1 for x in naturales() if b % (a**x) != 0), 1))[0]\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef mayorExponente4(a: int, b: int) -> int:\n    r = 0\n    while b % a == 0:\n        b = b \/\/ a\n        r = r + 1\n    return r\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\ndef prueba1() -> None:\n    for x in range(2, 11):\n        for y in range(1, 11):\n            print(x, y, mayorExponente4(x, y))\n\n\n# La propiedad es\n@given(st.integers(min_value=2, max_value=10),\n       st.integers(min_value=1, max_value=10))\ndef test_mayorExponente(a: int, b: int) -> None:\n    r = mayorExponente1(a, b)\n    assert mayorExponente2(a, b) == r\n    assert mayorExponente3(a, b) == r\n    assert mayorExponente4(a, b) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q exponente_mayor.py\n#    1 passed in 0.16s\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('mayorExponente1(2, 2**(2*10**4))')\n#    0.13 segundos\n#    >>> tiempo('mayorExponente2(2, 2**(2*10**4))')\n#    0.13 segundos\n#    >>> tiempo('mayorExponente3(2, 2**(2*10**4))')\n#    1.81 segundos\n#    >>> tiempo('mayorExponente4(2, 2**(2*10**4))')\n#    0.12 segundos\n#\n#    >>> tiempo('mayorExponente4(2, 2**(2*10**5))')\n#    12.19 segundos\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Producto cartesiano de dos conjuntos<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   producto :: [a] -> [b] -> [(a,b)]\n<\/pre>\n<p>tal que <code>producto xs ys<\/code> es el producto cartesiano de <code>xs<\/code> e <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]\n<\/pre>\n<p>Comprobar con QuickCheck que el n\u00famero de elementos de <code>producto xs y<\/code> es el producto del n\u00famero de elementos de <code>xs<\/code> y de <code>ys<\/code>.<\/p>\n<p><b>3.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nproducto1 :: [a] -> [a] -> [(a,a)]\nproducto1 xs ys = [(x,y) | x <- xs, y <- ys]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nproducto2 :: [a] -> [a] -> [(a,a)]\nproducto2 []     _  = []\nproducto2 (x:xs) ys = [(x,y) | y <- ys] ++ producto2 xs ys\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_producto :: [Int] -> [Int] -> Bool\nprop_producto xs ys =\n  producto1 xs ys `iguales` producto2 xs ys\n\n-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,\n--    iguales [3,2,3] [2,3]    ==  True\n--    iguales [3,2,3] [2,3,2]  ==  True\n--    iguales [3,2,3] [2,3,4]  ==  False\n--    iguales [2,3] [4,5]      ==  False\niguales :: Ord a => [a] -> [a] -> Bool\niguales xs ys =\n  subconjunto xs ys && subconjunto ys xs\n\n-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. por\n-- ejemplo,\n--    subconjunto [3,2,3] [2,5,3,5]  ==  True\n--    subconjunto [3,2,3] [2,5,6,5]  ==  False\nsubconjunto :: Ord a => [a] -> [a] -> Bool\nsubconjunto xs ys =\n  [x | x <- xs, x `elem` ys] == xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_producto\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (producto1 [1..4000] [1..4000])\n--    16000000\n--    (2.33 secs, 1,537,551,208 bytes)\n--    \u03bb> length (producto2 [1..4000] [1..4000])\n--    16000000\n--    (2.87 secs, 2,434,095,160 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_elementos_producto :: [Int] -> [Int] -> Bool\nprop_elementos_producto xs ys =\n  length (producto1 xs ys) == length xs * length ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_elementos_producto\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><b>3.2. Soluciones en Python<\/b><\/p>\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\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\nB = TypeVar('B')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef producto1(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:\n    return [(x, y) for x in xs for y in ys]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef producto2(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:\n    if xs:\n        return [(xs[0], y) for y in ys] + producto2(xs[1:], ys)\n    return []\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers()),\n       st.lists(st.integers()))\ndef test_producto(xs: list[int], ys: list[int]) -> None:\n    assert sorted(producto1(xs, ys)) == sorted(producto2(xs, ys))\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py\n#    1 passed in 0.31s\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('len(producto1(range(0, 1000), range(0, 500)))')\n#    0.03 segundos\n#    >>> tiempo('len(producto2(range(0, 1000), range(0, 500)))')\n#    2.58 segundos\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers()),\n       st.lists(st.integers()))\ndef test_elementos_producto(xs: list[int], ys: list[int]) -> None:\n    assert len(producto1(xs, ys)) == len(xs) * len(ys)\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py\n#    2 passed in 0.48s\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Subconjuntos de un conjunto<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   subconjuntos :: [a] -> [[a]]\n<\/pre>\n<p>tal que <code>subconjuntos xs<\/code> es la lista de las subconjuntos de la lista <code>xs<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> subconjuntos [2,3,4]\n   [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]\n   \u03bb> subconjuntos [1,2,3,4]\n   [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],\n      [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]\n<\/pre>\n<p>Comprobar con QuickChek que el n\u00famero de elementos de <code>subconjuntos xs<\/code> es 2 elevado al n\u00famero de elementos de <code>xs<\/code>.<\/p>\n<p><b> 4.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Data.List (sort, subsequences)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsubconjuntos1 :: [a] -> [[a]]\nsubconjuntos1 []     = [[]]\nsubconjuntos1 (x:xs) = [x:ys | ys <- sub] ++ sub\n  where sub = subconjuntos1 xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsubconjuntos2 :: [a] -> [[a]]\nsubconjuntos2 []     = [[]]\nsubconjuntos2 (x:xs) = map (x:) sub ++ sub\n  where sub = subconjuntos2 xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsubconjuntos3 :: [a] -> [[a]]\nsubconjuntos3 = subsequences\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_subconjuntos :: [Int] -> Bool\nprop_subconjuntos xs =\n  all (== sort (subconjuntos1 xs))\n      [sort (subconjuntos2 xs),\n       sort (subconjuntos3 xs)]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (subconjuntos1 [1..23])\n--    8388608\n--    (2.05 secs, 1,476,991,840 bytes)\n--    \u03bb> length (subconjuntos2 [1..23])\n--    8388608\n--    (0.87 secs, 1,208,555,312 bytes)\n--    \u03bb> length (subconjuntos3 [1..23])\n--    8388608\n--    (0.09 secs, 873,006,608 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_length_subconjuntos :: [Int] -> Bool\nprop_length_subconjuntos xs =\n  length (subconjuntos1 xs) == 2 ^ length xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=7}) prop_length_subconjuntos\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><b>4.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom itertools import combinations\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\nfrom sympy import FiniteSet\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef subconjuntos1(xs: list[A]) -> list[list[A]]:\n    if xs:\n        sub = subconjuntos1(xs[1:])\n        return [[xs[0]] + ys for ys in sub] + sub\n    return [[]]\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef subconjuntos2(xs: list[A]) -> list[list[A]]:\n    if xs:\n        sub = subconjuntos1(xs[1:])\n        return list(map((lambda ys: [xs[0]] + ys), sub)) + sub\n    return [[]]\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef subconjuntos3(xs: list[A]) -> list[list[A]]:\n    c = FiniteSet(*xs)\n    return list(map(list, c.powerset()))\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef subconjuntos4(xs: list[A]) -> list[list[A]]:\n    return [list(ys)\n            for r in range(len(xs)+1)\n            for ys in combinations(xs, r)]\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers(), max_size=5))\ndef test_subconjuntos(xs: list[int]) -> None:\n    ys = list(set(xs))\n    r = sorted([sorted(zs) for zs in subconjuntos1(ys)])\n    assert sorted([sorted(zs) for zs in subconjuntos2(ys)]) == r\n    assert sorted([sorted(zs) for zs in subconjuntos3(ys)]) == r\n    assert sorted([sorted(zs) for zs in subconjuntos4(ys)]) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q subconjuntos_de_un_conjunto.py\n#    1 passed in 0.89s\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('subconjuntos1(range(14))')\n#    0.00 segundos\n#    >>> tiempo('subconjuntos2(range(14))')\n#    0.00 segundos\n#    >>> tiempo('subconjuntos3(range(14))')\n#    6.01 segundos\n#    >>> tiempo('subconjuntos4(range(14))')\n#    0.00 segundos\n#\n#    >>> tiempo('subconjuntos1(range(23))')\n#    1.95 segundos\n#    >>> tiempo('subconjuntos2(range(23))')\n#    2.27 segundos\n#    >>> tiempo('subconjuntos4(range(23))')\n#    1.62 segundos\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers(), max_size=7))\ndef test_length_subconjuntos(xs: list[int]) -> None:\n    assert len(subconjuntos1(xs)) == 2 ** len(xs)\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q subconjuntos_de_un_conjunto.py\n#    2 passed in 0.95s\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. El algoritmo de Luhn<\/h3>\n<p>El objetivo de este ejercicio es estudiar un algoritmo para validar algunos identificadores num\u00e9ricos como los n\u00fameros de algunas tarjetas de cr\u00e9dito; por ejemplo, las de tipo Visa o Master Card.<\/p>\n<p>El algoritmo que vamos a estudiar es el <a href=\"https:\/\/bit.ly\/3DX1llv\">algoritmo de Luhn<\/a> consistente en aplicar los siguientes pasos a los d\u00edgitos del n\u00famero de la tarjeta.<\/p>\n<ol>\n<li>Se invierten los d\u00edgitos del n\u00famero; por ejemplo, [9,4,5,5] se transforma en [5,5,4,9].<\/li>\n<li>Se duplican los d\u00edgitos que se encuentra en posiciones impares (empezando a contar en 0); por ejemplo, [5,5,4,9] se transforma en [5,10,4,18].<\/li>\n<li>Se suman los d\u00edgitos de cada n\u00famero; por ejemplo, [5,10,4,18] se transforma en 5 + (1 + 0) + 4 + (1 + 8) = 19.<\/li>\n<li>Si el \u00faltimo d\u00edgito de la suma es 0, el n\u00famero es v\u00e1lido; y no lo es, en caso contrario.<\/li>\n<\/ol>\n<p>A los n\u00fameros v\u00e1lidos, se les llama n\u00fameros de Luhn.<\/p>\n<p>Definir las siguientes funciones:<\/p>\n<pre lang=\"text\">\n   digitosInv    :: Integer -> [Integer]\n   doblePosImpar :: [Integer] -> [Integer]\n   sumaDigitos   :: [Integer] -> Integer\n   ultimoDigito  :: Integer -> Integer\n   luhn          :: Integer -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>digitosInv n<\/code> es la lista de los d\u00edgitos del n\u00famero <code>n<\/code>, en orden inverso. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     digitosInv 320274  ==  [4,7,2,0,2,3]\n<\/pre>\n<ul>\n<li><code>doblePosImpar ns<\/code> es la lista obtenida doblando los elementos de <code>ns<\/code> en las posiciones impares (empezando a contar en cero y dejando igual a los que est\u00e1n en posiciones pares. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     doblePosImpar [4,9,5,5]    ==  [4,18,5,10]\n     doblePosImpar [4,9,5,5,7]  ==  [4,18,5,10,7]\n<\/pre>\n<ul>\n<li><code>sumaDigitos ns<\/code> es la suma de los d\u00edgitos de <code>ns<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     sumaDigitos [10,5,18,4] = 1 + 0 + 5 + 1 + 8 + 4 =\n                             = 19\n<\/pre>\n<ul>\n<li><code>ultimoDigito n<\/code> es el \u00faltimo d\u00edgito de <code>n<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     ultimoDigito 123 == 3\n     ultimoDigito   0 == 0\n<\/pre>\n<ul>\n<li><code>luhn n<\/code> se verifica si <code>n<\/code> es un n\u00famero de Luhn. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     luhn 5594589764218858  ==  True\n     luhn 1234567898765432  ==  False\n<\/pre>\n<p><b>5.1. Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\n-- Definici\u00f3n de digitosInv\n-- ========================\n\ndigitosInv :: Integer -> [Integer]\ndigitosInv n = [read [x] | x <- reverse (show n)]\n\n-- Nota: En el ejercicio \"D\u00edgitos de un n\u00famero\" https:\/\/bit.ly\/3Tkhc2T\n-- se presentan otras definiciones.\n\n-- Definiciones de doblePosImpar\n-- =============================\n\n-- 1\u00aa definici\u00f3n\ndoblePosImpar :: [Integer] -> [Integer]\ndoblePosImpar []       = []\ndoblePosImpar [x]      = [x]\ndoblePosImpar (x:y:zs) = x : 2*y : doblePosImpar zs\n\n-- 2\u00aa definici\u00f3n\ndoblePosImpar2 :: [Integer] -> [Integer]\ndoblePosImpar2 (x:y:zs) = x : 2*y : doblePosImpar2 zs\ndoblePosImpar2 xs       = xs\n\n-- 3\u00aa definici\u00f3n\ndoblePosImpar3 :: [Integer] -> [Integer]\ndoblePosImpar3 xs = [f n x | (n,x) <- zip [0..] xs]\n  where f n x | odd n     = 2*x\n              | otherwise = x\n\n-- Definiciones de sumaDigitos\n-- ===========================\n\nsumaDigitos :: [Integer] -> Integer\nsumaDigitos ns = sum [sum (digitosInv n) | n <- ns]\n\n-- Nota: En el ejercicio \"Suma de los d\u00edgitos de un n\u00famero\"\n-- https:\/\/bit.ly\/3U4u7WR se presentan otras definiciones.\n\n-- Definici\u00f3n de ultimoDigito\n-- ==========================\n\nultimoDigito :: Integer -> Integer\nultimoDigito n = n `rem` 10\n\n-- Definiciones de luhn\n-- ====================\n\n-- 1\u00aa definici\u00f3n\nluhn1 :: Integer -> Bool\nluhn1 n =\n  ultimoDigito (sumaDigitos (doblePosImpar (digitosInv n))) == 0\n\n-- 2\u00aa definici\u00f3n\nluhn2 :: Integer -> Bool\nluhn2 =\n  (==0) . ultimoDigito . sumaDigitos . doblePosImpar . digitosInv\n<\/pre>\n<p><b>5.2. Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\n# Definici\u00f3n de digitosInv\n# ========================\n\ndef digitosInv(n: int) -> list[int]:\n    return [int(x) for x in reversed(str(n))]\n\n# Nota: En el ejercicio \"D\u00edgitos de un n\u00famero\" https:\/\/bit.ly\/3Tkhc2T\n# se presentan otras definiciones.\n\n# Definiciones de doblePosImpar\n# =============================\n\n# 1\u00aa definici\u00f3n\ndef doblePosImpar(xs: list[int]) -> list[int]:\n    if len(xs) <= 1:\n        return xs\n    return [xs[0]] + [2*xs[1]] + doblePosImpar(xs[2:])\n\n# 2\u00aa definici\u00f3n\ndef doblePosImpar2(xs: list[int]) -> list[int]:\n    def f(n: int, x: int) -> int:\n        if n % 2 == 1:\n            return 2 * x\n        return x\n    return [f(n, x) for (n, x) in enumerate(xs)]\n\n# Definiciones de sumaDigitos\n# ===========================\n\ndef sumaDigitos(ns: list[int]) -> int:\n    return sum((sum(digitosInv(n)) for n in ns))\n\n# Nota: En el ejercicio \"Suma de los d\u00edgitos de un n\u00famero\"\n# https:\/\/bit.ly\/3U4u7WR se presentan otras definiciones.\n\n# Definici\u00f3n de ultimoDigito\n# ==========================\n\ndef ultimoDigito(n: int) -> int:\n    return n % 10\n\n# Definiciones de luhn\n# ====================\n\ndef luhn(n: int) -> bool:\n    return ultimoDigito(sumaDigitos(doblePosImpar(digitosInv(n)))) == 0\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. N\u00famero a partir de sus d\u00edgitos 2. Exponente de la mayor potencia de x que divide a y 3. Producto cartesiano de dos conjuntos 4. Subconjuntos de un conjunto 5. El algoritmo de Luhn 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\/7834"}],"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=7834"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7834\/revisions"}],"predecessor-version":[{"id":7836,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7834\/revisions\/7836"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7834"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7834"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7834"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}