{"id":7819,"date":"2022-10-23T16:52:59","date_gmt":"2022-10-23T14:52:59","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7819"},"modified":"2022-10-23T16:52:59","modified_gmt":"2022-10-23T14:52:59","slug":"pfh-la-semana-en-exercitium-21-de-octubre-de-2022","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-21-de-octubre-de-2022\/","title":{"rendered":"PFH: La semana en Exercitium (21 de octubre 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. Ternas pitag\u00f3ricas<\/a><\/li>\n<li><a href=\"#ej2\">2. Ternas pitag\u00f3ricas con suma dada<\/a><\/li>\n<li><a href=\"#ej3\">3. Producto escalar<\/a><\/li>\n<li><a href=\"#ej4\">4. Suma de elementos consecutivos<\/a><\/li>\n<li><a href=\"#ej5\">5. Representaci\u00f3n densa de polinomios<\/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. Ternas pitag\u00f3ricas<\/h3>\n<p>Una terna (x,y,z) de enteros positivos es pitag\u00f3rica si x\u00b2 + y\u00b2 = z\u00b2 y x &lt; y &lt; z.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   pitagoricas :: Int -> [(Int,Int,Int)]\n<\/pre>\n<p>tal que <code>pitagoricas n<\/code> es la lista de todas las ternas pitag\u00f3ricas cuyas componentes est\u00e1n entre 1 y <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   pitagoricas 10  ==  [(3,4,5),(6,8,10)]\n   pitagoricas 15  ==  [(3,4,5),(5,12,13),(6,8,10),(9,12,15)]\n<\/pre>\n<p>[expand title=&#8221;Soluciones en Haskell&#8221;]<\/p>\n<pre lang=\"haskell\">\r\nimport Test.QuickCheck\r\n\r\n-- 1\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\npitagoricas1 :: Int -> [(Int,Int,Int)]\r\npitagoricas1 n = [(x,y,z) | x <- [1..n]\r\n                          , y <- [1..n]\r\n                          , z <- [1..n]\r\n                          , x^2 + y^2 == z^2\r\n                          , x < y &#038;&#038; y < z]\r\n\r\n-- 2\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\npitagoricas2 :: Int -> [(Int,Int,Int)]\r\npitagoricas2 n = [(x,y,z) | x <- [1..n]\r\n                          , y <- [x+1..n]\r\n                          , z <- [ceiling (sqrt (fromIntegral (x^2+y^2)))..n]\r\n                          , x^2 + y^2 == z^2]\r\n\r\n-- 3\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\npitagoricas3 :: Int -> [(Int,Int,Int)]\r\npitagoricas3 n = [(x,y,z) | x <- [1..n]\r\n                          , y <- [x+1..n]\r\n                          , let z = round (sqrt (fromIntegral (x^2+y^2)))\r\n                          , y < z\r\n                          , z <= n\r\n                          , x^2 + y^2 == z^2]\r\n\r\n-- Comprobaci\u00f3n de equivalencia\r\n-- ============================\r\n\r\n-- La propiedad es\r\nprop_pitagoricas :: Positive Int -> Bool\r\nprop_pitagoricas (Positive n) =\r\n  all (== pitagoricas1 n)\r\n      [pitagoricas2 n,\r\n       pitagoricas3 n]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    \u03bb> quickCheck prop_pitagoricas\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n-- La comparaci\u00f3n es\r\n--    \u03bb> length (pitagoricas1 200)\r\n--    127\r\n--    (12.25 secs, 12,680,320,400 bytes)\r\n--    \u03bb> length (pitagoricas2 200)\r\n--    127\r\n--    (1.61 secs, 1,679,376,824 bytes)\r\n--    \u03bb> length (pitagoricas3 200)\r\n--    127\r\n--    (0.06 secs, 55,837,072 bytes)\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Ternas_pitagoricas.hs).<br \/>\n[\/expand]<\/p>\n<p>[expand title=&#8221;Soluciones en Python&#8221;]<\/p>\n<pre lang=\"python\">\r\nfrom math import ceil, sqrt\r\nfrom timeit import Timer, default_timer\r\n\r\nfrom hypothesis import given\r\nfrom hypothesis import strategies as st\r\n\r\n# 1\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef pitagoricas1(n: int) -> list[tuple[int, int, int]]:\r\n    return [(x, y, z)\r\n            for x in range(1, n+1)\r\n            for y in range(1, n+1)\r\n            for z in range(1, n+1)\r\n            if x**2 + y**2 == z**2 and x < y < z]\r\n\r\n# 2\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef pitagoricas2(n: int) -> list[tuple[int, int, int]]:\r\n    return [(x, y, z)\r\n            for x in range(1, n+1)\r\n            for y in range(x+1, n+1)\r\n            for z in range(ceil(sqrt(x**2+y**2)), n+1)\r\n            if x**2 + y**2 == z**2]\r\n\r\n# 3\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef pitagoricas3(n: int) -> list[tuple[int, int, int]]:\r\n    return [(x, y, z)\r\n            for x in range(1, n+1)\r\n            for y in range(x+1, n+1)\r\n            for z in [ceil(sqrt(x**2+y**2))]\r\n            if y < z <= n and x**2 + y**2 == z**2]\r\n\r\n# Comprobaci\u00f3n de equivalencia\r\n# ============================\r\n\r\n# La propiedad es\r\n@given(st.integers(min_value=1, max_value=50))\r\ndef test_pitagoricas(n: int) -> None:\r\n    r = pitagoricas1(n)\r\n    assert pitagoricas2(n) == r\r\n    assert pitagoricas3(n) == r\r\n\r\n# La comprobaci\u00f3n es\r\n#    src> poetry run pytest -q ternas_pitagoricas.py\r\n#    1 passed in 1.83s\r\n\r\n# Comparaci\u00f3n de eficiencia de pitagoricas\r\n# ======================================\r\n\r\ndef tiempo(e: str) -> None:\r\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\r\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\r\n    print(f\"{t:0.2f} segundos\")\r\n\r\n# La comparaci\u00f3n es\r\n#    >>> tiempo('pitagoricas1(200)')\r\n#    4.76 segundos\r\n#    >>> tiempo('pitagoricas2(200)')\r\n#    0.69 segundos\r\n#    >>> tiempo('pitagoricas3(200)')\r\n#    0.02 segundos\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium-Python\/blob\/main\/src\/ternas_pitagoricas.py).<br \/>\n[\/expand]<\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Ternas pitag\u00f3ricas con suma dada<\/h3>\n<p>Una terna pitag\u00f3rica es una terna de n\u00fameros naturales (a,b,c) tal que a&lt;b&lt;c y a\u00b2+b\u00b2=c\u00b2. Por ejemplo (3,4,5) es una terna pitag\u00f3rica.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]\n<\/pre>\n<p>tal que <code>ternasPitagoricas x<\/code> es la lista de las ternas pitag\u00f3ricas cuya suma es <code>x<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ternasPitagoricas 12     == [(3,4,5)]\n   ternasPitagoricas 60     == [(10,24,26),(15,20,25)]\n   ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]\n<\/pre>\n<p>[expand title=&#8221;Soluciones con Haskell&#8221;]<\/p>\n<pre lang=\"haskell\">\r\nimport Data.List (nub,sort)\r\nimport Test.QuickCheck\r\n\r\n-- 1\u00aa soluci\u00f3n                                                   --\r\n-- ===========\r\n\r\nternasPitagoricas1 :: Integer -> [(Integer,Integer,Integer)]\r\nternasPitagoricas1 x =\r\n  [(a,b,c) | a <- [0..x],\r\n             b <- [a+1..x],\r\n             c <- [b+1..x],\r\n             a^2 + b^2 == c^2,\r\n             a+b+c == x]\r\n\r\n-- 2\u00aa soluci\u00f3n                                                   --\r\n-- ===========\r\n\r\nternasPitagoricas2 :: Integer -> [(Integer,Integer,Integer)]\r\nternasPitagoricas2 x =\r\n  [(a,b,c) | a <- [1..x],\r\n             b <- [a+1..x-a],\r\n             let c = x-a-b,\r\n             a^2+b^2 == c^2]\r\n\r\n-- 3\u00aa soluci\u00f3n                                                   --\r\n-- ===========\r\n\r\n-- Todas las ternas pitag\u00f3ricas primitivas (a,b,c) pueden representarse\r\n-- por\r\n--    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,\r\n-- con 1 <= n < m. (Ver en https:\/\/bit.ly\/35UNY6L ).\r\n\r\nternasPitagoricas3 :: Integer -> [(Integer,Integer,Integer)]\r\nternasPitagoricas3 x =\r\n  nub [(d*a,d*b,d*c) | d <- [1..x],\r\n                       x `mod` d == 0,\r\n                       (a,b,c) <- aux (x `div` d)]\r\n  where\r\n    aux y = [(a,b,c) | m <- [2..limite],\r\n                       n <- [1..m-1],\r\n                       let [a,b] = sort [m^2 - n^2, 2*m*n],\r\n                       let c = m^2 + n^2,\r\n                       a+b+c == y]\r\n      where limite = ceiling (sqrt (fromIntegral y))\r\n\r\n-- Equivalencia de las definiciones\r\n-- ================================\r\n\r\n-- La propiedad es\r\nprop_ternasPitagoricas :: Positive Integer -> Bool\r\nprop_ternasPitagoricas (Positive x) =\r\n  all (== (ternasPitagoricas1 x))\r\n      [ternasPitagoricas2 x,\r\n       ternasPitagoricas3 x]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    \u03bb> quickCheck prop_ternasPitagoricas\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n-- La comparaci\u00f3n es\r\n--    \u03bb> ternasPitagoricas1 200\r\n--    [(40,75,85)]\r\n--    (1.90 secs, 2,404,800,856 bytes)\r\n--    \u03bb> ternasPitagoricas2 200\r\n--    [(40,75,85)]\r\n--    (0.06 secs, 19,334,232 bytes)\r\n--    \u03bb> ternasPitagoricas3 200\r\n--    [(40,75,85)]\r\n--    (0.01 secs, 994,224 bytes)\r\n--\r\n--    \u03bb> ternasPitagoricas2 3000\r\n--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]\r\n--    (4.41 secs, 4,354,148,136 bytes)\r\n--    \u03bb> ternasPitagoricas3 3000\r\n--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]\r\n--    (0.05 secs, 17,110,360 bytes)\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Ternas_pitagoricas_con_suma_dada.hs).<br \/>\n[\/expand]<\/p>\n<p>[expand title=&#8221;Soluciones con Python&#8221;]<\/p>\n<pre lang=\"python\">\r\nfrom math import ceil, sqrt\r\nfrom timeit import Timer, default_timer\r\n\r\nfrom hypothesis import given\r\nfrom hypothesis import strategies as st\r\n\r\n# 1\u00aa soluci\u00f3n                                                   --\r\n# ===========\r\n\r\ndef ternasPitagoricas1(x: int) -> list[tuple[int, int, int]]:\r\n    return [(a, b, c)\r\n            for a in range(0, x+1)\r\n            for b in range(a+1, x+1)\r\n            for c in range(b+1, x+1)\r\n            if a**2 + b**2 == c**2 and a + b + c == x]\r\n\r\n# 2\u00aa soluci\u00f3n                                                   --\r\n# ===========\r\n\r\ndef ternasPitagoricas2(x: int) -> list[tuple[int, int, int]]:\r\n    return [(a, b, c)\r\n            for a in range(1, x+1)\r\n            for b in range(a+1, x-a+1)\r\n            for c in [x - a - b]\r\n            if a**2 + b**2 == c**2]\r\n\r\n# 3\u00aa soluci\u00f3n                                                   --\r\n# ===========\r\n\r\n# Todas las ternas pitag\u00f3ricas primitivas (a,b,c) pueden representarse\r\n# por\r\n#    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,\r\n# con 1 <= n < m. (Ver en https:\/\/bit.ly\/35UNY6L ).\r\n\r\ndef ternasPitagoricas3(x: int) -> list[tuple[int, int, int]]:\r\n    def aux(y: int) -> list[tuple[int, int, int]]:\r\n        return [(a, b, c)\r\n                for m in range(2, 1 + ceil(sqrt(y)))\r\n                for n in range(1, m)\r\n                for a in [min(m**2 - n**2, 2*m*n)]\r\n                for b in [max(m**2 - n**2, 2*m*n)]\r\n                for c in [m**2 + n**2]\r\n                if a+b+c == y]\r\n\r\n    return list(set(((d*a, d*b, d*c)\r\n                     for d in range(1, x+1)\r\n                     for (a, b, c) in aux(x \/\/ d)\r\n                     if x % d == 0)))\r\n\r\n# Comprobaci\u00f3n de equivalencia\r\n# ============================\r\n\r\n# La propiedad es\r\n@given(st.integers(min_value=1, max_value=50))\r\ndef test_ternasPitagoricas(n: int) -> None:\r\n    r = set(ternasPitagoricas1(n))\r\n    assert set(ternasPitagoricas2(n)) == r\r\n    assert set(ternasPitagoricas3(n)) == r\r\n\r\n# La comprobaci\u00f3n es\r\n#    src> poetry run pytest -q ternas_pitagoricas_con_suma_dada.py\r\n#    1 passed in 0.35s\r\n\r\n# Comparaci\u00f3n de eficiencia\r\n# =========================\r\n\r\ndef tiempo(e: str) -> None:\r\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\r\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\r\n    print(f\"{t:0.2f} segundos\")\r\n\r\n# La comparaci\u00f3n es\r\n#    >>> tiempo('ternasPitagoricas1(300)')\r\n#    2.83 segundos\r\n#    >>> tiempo('ternasPitagoricas2(300)')\r\n#    0.01 segundos\r\n#    >>> tiempo('ternasPitagoricas3(300)')\r\n#    0.00 segundos\r\n#\r\n#    >>> tiempo('ternasPitagoricas2(3000)')\r\n#    1.48 segundos\r\n#    >>> tiempo('ternasPitagoricas3(3000)')\r\n#    0.02 segundos\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium-Python\/blob\/main\/src\/ternas_pitagoricas_con_suma_dada.py).<br \/>\n[\/expand]<\/p>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Producto escalar<\/h3>\n<p>El producto escalar de dos listas de enteros xs y ys de longitud n viene dado por la suma de los productos de los elementos correspondientes.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   productoEscalar :: [Integer] -> [Integer] -> Integer\n<\/pre>\n<p>tal que <code>productoEscalar xs ys<\/code> es el producto escalar de las listas <code>xs<\/code> e <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   productoEscalar [1,2,3] [4,5,6]  ==  32\n<\/pre>\n<p>[expand title=&#8221;Soluciones en Haskell&#8221;]<\/p>\n<pre lang=\"haskell\">\r\nimport Numeric.LinearAlgebra ((<.>), vector)\r\nimport Test.QuickCheck (quickCheck)\r\n\r\n-- 1\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nproductoEscalar1 :: [Integer] -> [Integer] -> Integer\r\nproductoEscalar1 xs ys = sum [x*y | (x,y) <- zip xs ys]\r\n\r\n-- 2\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nproductoEscalar2 :: [Integer] -> [Integer] -> Integer\r\nproductoEscalar2 xs ys = sum (zipWith (*) xs ys)\r\n\r\n-- 3\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nproductoEscalar3 :: [Integer] -> [Integer] -> Integer\r\nproductoEscalar3 = (sum .) . zipWith (*)\r\n\r\n-- 4\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nproductoEscalar4 :: [Integer] -> [Integer] -> Integer\r\nproductoEscalar4 [] _          = 0\r\nproductoEscalar4 _ []          = 0\r\nproductoEscalar4 (x:xs) (y:ys) = x*y + productoEscalar4 xs ys\r\n\r\n-- 5\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nproductoEscalar5 :: [Integer] -> [Integer] -> Integer\r\nproductoEscalar5 (x:xs) (y:ys) = x*y + productoEscalar5 xs ys\r\nproductoEscalar5 _ _           = 0\r\n\r\n-- 6\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nproductoEscalar6 :: [Integer] -> [Integer] -> Integer\r\nproductoEscalar6 xs ys =\r\n  round (vector xs' <.> vector ys')\r\n  where xs' = map fromIntegral xs\r\n        ys' = map fromIntegral ys\r\n\r\n-- Comprobaci\u00f3n de equivalencia\r\n-- ============================\r\n\r\n-- La propiedad es\r\nprop_productoEscalar :: [Integer] -> [Integer] -> Bool\r\nprop_productoEscalar xs ys =\r\n  all (== productoEscalar1 xs ys)\r\n      [productoEscalar2 xs ys,\r\n       productoEscalar3 xs ys,\r\n       productoEscalar4 xs ys,\r\n       productoEscalar5 xs ys,\r\n       productoEscalar6 xs' ys']\r\n  where n = min (length xs) (length ys)\r\n        xs' = take n xs\r\n        ys' = take n ys\r\n\r\n-- La comprobaci\u00f3n es\r\n--    \u03bb> quickCheck prop_productoEscalar\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n-- La comparaci\u00f3n es\r\n--    \u03bb> productoEscalar1 (replicate (2*10^6) 1) (replicate (2*10^6) 1)\r\n--    2000000\r\n--    (1.37 secs, 803,827,520 bytes)\r\n--    \u03bb> productoEscalar2 (replicate (2*10^6) 1) (replicate (2*10^6) 1)\r\n--    2000000\r\n--    (0.69 secs, 611,008,272 bytes)\r\n--    \u03bb> productoEscalar3 (replicate (2*10^6) 1) (replicate (2*10^6) 1)\r\n--    2000000\r\n--    (0.69 secs, 611,008,536 bytes)\r\n--    \u03bb> productoEscalar4 (replicate (2*10^6) 1) (replicate (2*10^6) 1)\r\n--    2000000\r\n--    (1.64 secs, 742,290,272 bytes)\r\n--    \u03bb> productoEscalar5 (replicate (2*10^6) 1) (replicate (2*10^6) 1)\r\n--    2000000\r\n--    (1.63 secs, 742,290,064 bytes)\r\n--    \u03bb> productoEscalar6 (replicate (2*10^6) 1) (replicate (2*10^6) 1)\r\n--    2000000\r\n--    (0.32 secs, 835,679,200 bytes)\r\n--\r\n--    \u03bb> productoEscalar2 (replicate (6*10^6) 1) (replicate (6*10^6) 1)\r\n--    6000000\r\n--    (1.90 secs, 1,831,960,336 bytes)\r\n--    \u03bb> productoEscalar3 (replicate (6*10^6) 1) (replicate (6*10^6) 1)\r\n--    6000000\r\n--    (1.87 secs, 1,831,960,600 bytes)\r\n--    \u03bb> productoEscalar6 (replicate (6*10^6) 1) (replicate (6*10^6) 1)\r\n--    6000000\r\n--    (0.78 secs, 2,573,005,952 bytes)\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Producto_escalar.hs).<br \/>\n[\/expand]<\/p>\n<p>[expand title=&#8221;Soluciones en Python&#8221;]<\/p>\n<pre lang=\"python\">\r\nfrom operator import mul\r\nfrom sys import setrecursionlimit\r\nfrom timeit import Timer, default_timer\r\n\r\nfrom hypothesis import given\r\nfrom hypothesis import strategies as st\r\nfrom numpy import dot\r\n\r\nsetrecursionlimit(10**6)\r\n\r\n# 1\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef productoEscalar1(xs: list[int], ys: list[int]) -> int:\r\n    return sum(x * y for (x, y) in zip(xs, ys))\r\n\r\n# 2\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef productoEscalar2(xs: list[int], ys: list[int]) -> int:\r\n    return sum(map(mul, xs, ys))\r\n\r\n# 3\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef productoEscalar3(xs: list[int], ys: list[int]) -> int:\r\n    if xs and ys:\r\n        return xs[0] * ys[0] + productoEscalar3(xs[1:], ys[1:])\r\n    return 0\r\n\r\n# 4\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef productoEscalar4(xs: list[int], ys: list[int]) -> int:\r\n    return dot(xs, ys)\r\n\r\n# Comprobaci\u00f3n de equivalencia\r\n# ============================\r\n\r\n# La propiedad es\r\n@given(st.lists(st.integers(min_value=1, max_value=100)),\r\n       st.lists(st.integers(min_value=1, max_value=100)))\r\ndef test_productoEscalar(xs: list[int], ys: list[int]) -> None:\r\n    r = productoEscalar1(xs, ys)\r\n    assert productoEscalar2(xs, ys) == r\r\n    assert productoEscalar3(xs, ys) == r\r\n    n = min(len(xs), len(ys))\r\n    xs1 = xs[:n]\r\n    ys1 = ys[:n]\r\n    assert productoEscalar4(xs1, ys1) == r\r\n\r\n# La comprobaci\u00f3n es\r\n#    src> poetry run pytest -q producto_escalar.py\r\n#    1 passed in 0.37s\r\n\r\n# Comparaci\u00f3n de eficiencia\r\n# =========================\r\n\r\ndef tiempo(e: str) -> None:\r\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\r\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\r\n    print(f\"{t:0.2f} segundos\")\r\n\r\n# La comparaci\u00f3n es\r\n#    >>> tiempo('productoEscalar1([1]*(10**4), [1]*(10**4))')\r\n#    0.00 segundos\r\n#    >>> tiempo('productoEscalar3([1]*(10**4), [1]*(10**4))')\r\n#    0.55 segundos\r\n#\r\n#    >>> tiempo('productoEscalar1([1]*(10**7), [1]*(10**7))')\r\n#    0.60 segundos\r\n#    >>> tiempo('productoEscalar2([1]*(10**7), [1]*(10**7))')\r\n#    0.26 segundos\r\n#    >>> tiempo('productoEscalar4([1]*(10**7), [1]*(10**7))')\r\n#    1.73 segundos\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium-Python\/blob\/main\/src\/producto_escalar.py).<br \/>\n[\/expand]<\/p>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Suma de elementos consecutivos<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   sumaConsecutivos :: [Integer] -> [Integer]\n<\/pre>\n<p>tal que <code>sumaConsecutivos xs<\/code> es la suma de los pares de elementos consecutivos de la lista xs. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   sumaConsecutivos [3,1,5,2]  ==  [4,6,7]\n   sumaConsecutivos [3]        ==  []\n   last (sumaConsecutivos [1..10^8])  ==  199999999\n<\/pre>\n<p>[expand title=&#8221;Soluciones en Haskell&#8221;]<\/p>\n<pre lang=\"haskell\">\r\nimport Test.QuickCheck\r\n\r\n-- 1\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsumaConsecutivos1 :: [Integer] -> [Integer]\r\nsumaConsecutivos1 xs = [x+y | (x,y) <- zip xs (tail xs)]\r\n\r\n-- 2\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsumaConsecutivos2 :: [Integer] -> [Integer]\r\nsumaConsecutivos2 xs = zipWith (+) xs (tail xs)\r\n\r\n-- 3\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsumaConsecutivos3 :: [Integer] -> [Integer]\r\nsumaConsecutivos3 = zipWith (+) <*> tail\r\n\r\n-- 4\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsumaConsecutivos4 :: [Integer] -> [Integer]\r\nsumaConsecutivos4 (x:y:zs) = x+y : sumaConsecutivos4 (y:zs)\r\nsumaConsecutivos4 _        = []\r\n\r\n-- Comprobaci\u00f3n de equivalencia\r\n-- ============================\r\n\r\n-- La propiedad es\r\nprop_sumaConsecutivos :: [Integer] -> Bool\r\nprop_sumaConsecutivos xs =\r\n  all (== sumaConsecutivos1 xs)\r\n      [sumaConsecutivos2 xs,\r\n       sumaConsecutivos3 xs,\r\n       sumaConsecutivos4 xs]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    \u03bb> quickCheck prop_sumaConsecutivos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n-- La comparaci\u00f3n es\r\n--    \u03bb> last (sumaConsecutivos1 [1..8*10^6])\r\n--    15999999\r\n--    (1.98 secs, 2,176,566,784 bytes)\r\n--    \u03bb> last (sumaConsecutivos2 [1..8*10^6])\r\n--    15999999\r\n--    (0.19 secs, 1,408,566,840 bytes)\r\n--    \u03bb> last (sumaConsecutivos3 [1..8*10^6])\r\n--    15999999\r\n--    (0.19 secs, 1,408,566,936 bytes)\r\n--    \u03bb> last (sumaConsecutivos4 [1..8*10^6])\r\n--    15999999\r\n--    (2.78 secs, 2,560,566,832 bytes)\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Suma_elementos_consecutivos.hs).<br \/>\n[\/expand]<\/p>\n<p>[expand title=&#8221;Soluciones en Python&#8221;]<\/p>\n<pre lang=\"python\">\r\nfrom operator import add\r\nfrom sys import setrecursionlimit\r\nfrom timeit import Timer, default_timer\r\n\r\nfrom hypothesis import given\r\nfrom hypothesis import strategies as st\r\n\r\nsetrecursionlimit(10**6)\r\n\r\n# 1\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef sumaConsecutivos1(xs: list[int]) -> list[int]:\r\n    return [x + y for (x, y) in zip(xs, xs[1:])]\r\n\r\n# 2\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef sumaConsecutivos2(xs: list[int]) -> list[int]:\r\n    return list(map(add, xs, xs[1:]))\r\n\r\n# 3\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef sumaConsecutivos3(xs: list[int]) -> list[int]:\r\n    if len(xs) >= 2:\r\n        return [xs[0] + xs[1]] + sumaConsecutivos3(xs[1:])\r\n    return []\r\n\r\n# Comprobaci\u00f3n de equivalencia\r\n# ============================\r\n\r\n# La propiedad es\r\n@given(st.lists(st.integers(min_value=1, max_value=100)))\r\ndef test_sumaConsecutivos(xs: list[int]) -> None:\r\n    r = sumaConsecutivos1(xs)\r\n    assert sumaConsecutivos2(xs) == r\r\n    assert sumaConsecutivos3(xs) == r\r\n\r\n# La comprobaci\u00f3n es\r\n#    src> poetry run pytest -q suma_elementos_consecutivos.py\r\n#    1 passed in 0.26s\r\n\r\n# Comparaci\u00f3n de eficiencia\r\n# =========================\r\n\r\ndef tiempo(e: str) -> None:\r\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\r\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\r\n    print(f\"{t:0.2f} segundos\")\r\n\r\n# La comparaci\u00f3n es\r\n#    >>> tiempo('sumaConsecutivos1(range(1, 10**4))')\r\n#    0.00 segundos\r\n#    >>> tiempo('sumaConsecutivos2(range(1, 10**4))')\r\n#    0.00 segundos\r\n#    >>> tiempo('sumaConsecutivos3(range(1, 10**4))')\r\n#    0.18 segundos\r\n#\r\n#    >>> tiempo('sumaConsecutivos1(range(1, 10**8))')\r\n#    8.34 segundos\r\n#    >>> tiempo('sumaConsecutivos2(range(1, 10**8))')\r\n#    6.28 segundos\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium-Python\/blob\/main\/src\/suma_elementos_consecutivos.py).<br \/>\n[\/expand]<\/p>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Representaci\u00f3n densa de polinomios<\/h3>\n<p>Los polinomios pueden representarse de forma dispersa o densa. Por ejemplo, el polinomio 6x^4-5x^2+4x-7 se puede representar de forma dispersa por [6,0,-5,4,-7] y de forma densa por [(4,6),(2,-5),(1,4),(0,-7)].<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   densa :: [Int] -> [(Int,Int)]\n<\/pre>\n<p>tal que <code>densa xs<\/code> es la representaci\u00f3n densa del polinomio cuya representaci\u00f3n dispersa es <code>xs<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   densa [6,0,-5,4,-7]  ==  [(4,6),(2,-5),(1,4),(0,-7)]\n   densa [6,0,0,3,0,4]  ==  [(5,6),(2,3),(0,4)]\n   densa [0]            ==  [(0,0)]\n<\/pre>\n<p>[expand title=&#8221;Soluciones en Haskell&#8221;]<\/p>\n<pre lang=\"haskell\">\r\nimport Test.QuickCheck\r\n\r\n-- 1\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\ndensa1 :: [Int] -> [(Int,Int)]\r\ndensa1 xs =\r\n  [(x,y) | (x,y) <- zip [n-1,n-2..1] xs, y \/= 0]\r\n  ++ [(0, last xs)]\r\n  where n = length xs\r\n\r\n-- 2\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\ndensa2 :: [Int] -> [(Int,Int)]\r\ndensa2 xs =\r\n  filter (\\ (_,y) -> y \/= 0) (zip [n-1,n-2..1] xs)\r\n  ++ [(0, last xs)]\r\n  where n = length xs\r\n\r\n-- 3\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\ndensa3 :: [Int] -> [(Int,Int)]\r\ndensa3 xs = filter ((\/= 0) . snd) (zip [n-1,n-2..1] xs)\r\n  ++ [(0, last xs)]\r\n  where n = length xs\r\n\r\n-- 4\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\ndensa4 :: [Int] -> [(Int,Int)]\r\ndensa4 xs = aux xs (length xs - 1)\r\n  where aux [y] 0 = [(0, y)]\r\n        aux (y:ys) n | y == 0    = aux ys (n-1)\r\n                     | otherwise = (n,y) : aux ys (n-1)\r\n\r\n-- Comprobaci\u00f3n de equivalencia\r\n-- ============================\r\n\r\n-- La propiedad es\r\nprop_densa :: NonEmptyList Int -> Bool\r\nprop_densa (NonEmpty xs) =\r\n  all (== densa1 xs)\r\n      [densa2 xs,\r\n       densa3 xs,\r\n       densa4 xs]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    \u03bb> quickCheck prop_densa\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n-- La comparaci\u00f3n es\r\n--    \u03bb> last (densa1 [1..2*10^6])\r\n--    (0,2000000)\r\n--    (0.95 secs, 880,569,400 bytes)\r\n--    \u03bb> last (densa2 [1..2*10^6])\r\n--    (0,2000000)\r\n--    (0.52 secs, 800,569,432 bytes)\r\n--    \u03bb> last (densa3 [1..2*10^6])\r\n--    (0,2000000)\r\n--    (0.53 secs, 752,569,552 bytes)\r\n--    \u03bb> last (densa4 [1..2*10^6])\r\n--    (0,2000000)\r\n--    (3.05 secs, 1,267,842,032 bytes)\r\n--\r\n--    \u03bb> last (densa1 [1..10^7])\r\n--    (0,10000000)\r\n--    (5.43 secs, 4,400,570,128 bytes)\r\n--    \u03bb> last (densa2 [1..10^7])\r\n--    (0,10000000)\r\n--    (3.03 secs, 4,000,570,160 bytes)\r\n--    \u03bb> last (densa3 [1..10^7])\r\n--    (0,10000000)\r\n--    (2.34 secs, 3,760,570,280 bytes)\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Representacion_densa_de_polinomios.hs).<br \/>\n[\/expand]<\/p>\n<p>[expand title=&#8221;Soluciones en Python&#8221;]<\/p>\n<pre lang=\"python\">\r\nfrom sys import setrecursionlimit\r\nfrom timeit import Timer, default_timer\r\n\r\nfrom hypothesis import given\r\nfrom hypothesis import strategies as st\r\n\r\nsetrecursionlimit(10**6)\r\n\r\n# 1\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef densa1(xs: list[int]) -> list[tuple[int, int]]:\r\n    n = len(xs)\r\n    return [(x, y)\r\n            for (x, y) in zip(range(n-1, 0, -1), xs)\r\n            if y != 0] + [(0, xs[-1])]\r\n\r\n# 2\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef densa2(xs: list[int]) -> list[tuple[int, int]]:\r\n    n = len(xs)\r\n    return list(filter(lambda p: p[1] != 0,\r\n                       zip(range(n-1, 0, -1), xs))) + [(0, xs[-1])]\r\n\r\n# 3\u00aa soluci\u00f3n\r\n# ===========\r\n\r\ndef densa3(xs: list[int]) -> list[tuple[int, int]]:\r\n    def aux(ys: list[int], n: int) -> list[tuple[int, int]]:\r\n        if n == 0:\r\n            return [(0, ys[0])]\r\n        if ys[0] == 0:\r\n            return aux(ys[1:], n-1)\r\n        return [(n, ys[0])] + aux(ys[1:], n-1)\r\n\r\n    return aux(xs, len(xs) - 1)\r\n\r\n# Comprobaci\u00f3n de equivalencia\r\n# ============================\r\n\r\n# La propiedad es\r\n@given(st.lists(st.integers(), min_size=1))\r\ndef test_densa(xs: list[int]) -> None:\r\n    r = densa1(xs)\r\n    assert densa2(xs) == r\r\n    assert densa3(xs) == r\r\n\r\n# La comprobaci\u00f3n es\r\n#    src> poetry run pytest -q representacion_densa_de_polinomios.py\r\n#    1 passed in 0.27s\r\n\r\n# Comparaci\u00f3n de eficiencia\r\n# =========================\r\n\r\ndef tiempo(e: str) -> None:\r\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\r\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\r\n    print(f\"{t:0.2f} segundos\")\r\n\r\n# La comparaci\u00f3n es\r\n#    >>> tiempo('densa1(range(1, 10**4))')\r\n#    0.00 segundos\r\n#    >>> tiempo('densa2(range(1, 10**4))')\r\n#    0.00 segundos\r\n#    >>> tiempo('densa3(range(1, 10**4))')\r\n#    0.25 segundos\r\n#\r\n#    >>> tiempo('densa1(range(1, 10**7))')\r\n#    1.87 segundos\r\n#    >>> tiempo('densa2(range(1, 10**7))')\r\n#    2.15 segundos\r\n<\/pre>\n<p>El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium-Python\/blob\/main\/src\/representacion_densa_de_polinomios.py)<br \/>\n[\/expand]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Ternas pitag\u00f3ricas 2. Ternas pitag\u00f3ricas con suma dada 3. Producto escalar 4. Suma de elementos consecutivos 5. Representaci\u00f3n densa de polinomios 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\/7819"}],"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=7819"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7819\/revisions"}],"predecessor-version":[{"id":7820,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7819\/revisions\/7820"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7819"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7819"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7819"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}