PFH: La semana en Exercitium (21 de octubre de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Ternas pitagóricas
- 2. Ternas pitagóricas con suma dada
- 3. Producto escalar
- 4. Suma de elementos consecutivos
- 5. Representación densa de polinomios
A continuación se muestran las soluciones.
1. Ternas pitagóricas
Una terna (x,y,z) de enteros positivos es pitagórica si x² + y² = z² y x < y < z.
Definir la función
|
1 |
pitagoricas :: Int -> [(Int,Int,Int)] |
tal que pitagoricas n es la lista de todas las ternas pitagóricas cuyas componentes están entre 1 y n. Por ejemplo,
|
1 2 |
pitagoricas 10 == [(3,4,5),(6,8,10)] pitagoricas 15 == [(3,4,5),(5,12,13),(6,8,10),(9,12,15)] |
[expand title=”Soluciones en Haskell”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
import Test.QuickCheck -- 1ª solución -- =========== pitagoricas1 :: Int -> [(Int,Int,Int)] pitagoricas1 n = [(x,y,z) | x <- [1..n] , y <- [1..n] , z <- [1..n] , x^2 + y^2 == z^2 , x < y && y < z] -- 2ª solución -- =========== pitagoricas2 :: Int -> [(Int,Int,Int)] pitagoricas2 n = [(x,y,z) | x <- [1..n] , y <- [x+1..n] , z <- [ceiling (sqrt (fromIntegral (x^2+y^2)))..n] , x^2 + y^2 == z^2] -- 3ª solución -- =========== pitagoricas3 :: Int -> [(Int,Int,Int)] pitagoricas3 n = [(x,y,z) | x <- [1..n] , y <- [x+1..n] , let z = round (sqrt (fromIntegral (x^2+y^2))) , y < z , z <= n , x^2 + y^2 == z^2] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_pitagoricas :: Positive Int -> Bool prop_pitagoricas (Positive n) = all (== pitagoricas1 n) [pitagoricas2 n, pitagoricas3 n] -- La comprobación es -- λ> quickCheck prop_pitagoricas -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (pitagoricas1 200) -- 127 -- (12.25 secs, 12,680,320,400 bytes) -- λ> length (pitagoricas2 200) -- 127 -- (1.61 secs, 1,679,376,824 bytes) -- λ> length (pitagoricas3 200) -- 127 -- (0.06 secs, 55,837,072 bytes) |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Ternas_pitagoricas.hs).
[/expand]
[expand title=”Soluciones en Python”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
from math import ceil, sqrt from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st # 1ª solución # =========== def pitagoricas1(n: int) -> list[tuple[int, int, int]]: return [(x, y, z) for x in range(1, n+1) for y in range(1, n+1) for z in range(1, n+1) if x**2 + y**2 == z**2 and x < y < z] # 2ª solución # =========== def pitagoricas2(n: int) -> list[tuple[int, int, int]]: return [(x, y, z) for x in range(1, n+1) for y in range(x+1, n+1) for z in range(ceil(sqrt(x**2+y**2)), n+1) if x**2 + y**2 == z**2] # 3ª solución # =========== def pitagoricas3(n: int) -> list[tuple[int, int, int]]: return [(x, y, z) for x in range(1, n+1) for y in range(x+1, n+1) for z in [ceil(sqrt(x**2+y**2))] if y < z <= n and x**2 + y**2 == z**2] # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=50)) def test_pitagoricas(n: int) -> None: r = pitagoricas1(n) assert pitagoricas2(n) == r assert pitagoricas3(n) == r # La comprobación es # src> poetry run pytest -q ternas_pitagoricas.py # 1 passed in 1.83s # Comparación de eficiencia de pitagoricas # ====================================== def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('pitagoricas1(200)') # 4.76 segundos # >>> tiempo('pitagoricas2(200)') # 0.69 segundos # >>> tiempo('pitagoricas3(200)') # 0.02 segundos |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/ternas_pitagoricas.py).
[/expand]
2. Ternas pitagóricas con suma dada
Una terna pitagórica es una terna de números naturales (a,b,c) tal que a<b<c y a²+b²=c². Por ejemplo (3,4,5) es una terna pitagórica.
Definir la función
|
1 |
ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)] |
tal que ternasPitagoricas x es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,
|
1 2 3 |
ternasPitagoricas 12 == [(3,4,5)] ternasPitagoricas 60 == [(10,24,26),(15,20,25)] ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)] |
[expand title=”Soluciones con Haskell”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
import Data.List (nub,sort) import Test.QuickCheck -- 1ª solución -- -- =========== ternasPitagoricas1 :: Integer -> [(Integer,Integer,Integer)] ternasPitagoricas1 x = [(a,b,c) | a <- [0..x], b <- [a+1..x], c <- [b+1..x], a^2 + b^2 == c^2, a+b+c == x] -- 2ª solución -- -- =========== ternasPitagoricas2 :: Integer -> [(Integer,Integer,Integer)] ternasPitagoricas2 x = [(a,b,c) | a <- [1..x], b <- [a+1..x-a], let c = x-a-b, a^2+b^2 == c^2] -- 3ª solución -- -- =========== -- Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse -- por -- a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2, -- con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ). ternasPitagoricas3 :: Integer -> [(Integer,Integer,Integer)] ternasPitagoricas3 x = nub [(d*a,d*b,d*c) | d <- [1..x], x `mod` d == 0, (a,b,c) <- aux (x `div` d)] where aux y = [(a,b,c) | m <- [2..limite], n <- [1..m-1], let [a,b] = sort [m^2 - n^2, 2*m*n], let c = m^2 + n^2, a+b+c == y] where limite = ceiling (sqrt (fromIntegral y)) -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_ternasPitagoricas :: Positive Integer -> Bool prop_ternasPitagoricas (Positive x) = all (== (ternasPitagoricas1 x)) [ternasPitagoricas2 x, ternasPitagoricas3 x] -- La comprobación es -- λ> quickCheck prop_ternasPitagoricas -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> ternasPitagoricas1 200 -- [(40,75,85)] -- (1.90 secs, 2,404,800,856 bytes) -- λ> ternasPitagoricas2 200 -- [(40,75,85)] -- (0.06 secs, 19,334,232 bytes) -- λ> ternasPitagoricas3 200 -- [(40,75,85)] -- (0.01 secs, 994,224 bytes) -- -- λ> ternasPitagoricas2 3000 -- [(500,1200,1300),(600,1125,1275),(750,1000,1250)] -- (4.41 secs, 4,354,148,136 bytes) -- λ> ternasPitagoricas3 3000 -- [(500,1200,1300),(600,1125,1275),(750,1000,1250)] -- (0.05 secs, 17,110,360 bytes) |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Ternas_pitagoricas_con_suma_dada.hs).
[/expand]
[expand title=”Soluciones con Python”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
from math import ceil, sqrt from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st # 1ª solución -- # =========== def ternasPitagoricas1(x: int) -> list[tuple[int, int, int]]: return [(a, b, c) for a in range(0, x+1) for b in range(a+1, x+1) for c in range(b+1, x+1) if a**2 + b**2 == c**2 and a + b + c == x] # 2ª solución -- # =========== def ternasPitagoricas2(x: int) -> list[tuple[int, int, int]]: return [(a, b, c) for a in range(1, x+1) for b in range(a+1, x-a+1) for c in [x - a - b] if a**2 + b**2 == c**2] # 3ª solución -- # =========== # Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse # por # a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2, # con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ). def ternasPitagoricas3(x: int) -> list[tuple[int, int, int]]: def aux(y: int) -> list[tuple[int, int, int]]: return [(a, b, c) for m in range(2, 1 + ceil(sqrt(y))) for n in range(1, m) for a in [min(m**2 - n**2, 2*m*n)] for b in [max(m**2 - n**2, 2*m*n)] for c in [m**2 + n**2] if a+b+c == y] return list(set(((d*a, d*b, d*c) for d in range(1, x+1) for (a, b, c) in aux(x // d) if x % d == 0))) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=50)) def test_ternasPitagoricas(n: int) -> None: r = set(ternasPitagoricas1(n)) assert set(ternasPitagoricas2(n)) == r assert set(ternasPitagoricas3(n)) == r # La comprobación es # src> poetry run pytest -q ternas_pitagoricas_con_suma_dada.py # 1 passed in 0.35s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('ternasPitagoricas1(300)') # 2.83 segundos # >>> tiempo('ternasPitagoricas2(300)') # 0.01 segundos # >>> tiempo('ternasPitagoricas3(300)') # 0.00 segundos # # >>> tiempo('ternasPitagoricas2(3000)') # 1.48 segundos # >>> tiempo('ternasPitagoricas3(3000)') # 0.02 segundos |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/ternas_pitagoricas_con_suma_dada.py).
[/expand]
3. Producto escalar
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.
Definir la función
|
1 |
productoEscalar :: [Integer] -> [Integer] -> Integer |
tal que productoEscalar xs ys es el producto escalar de las listas xs e ys. Por ejemplo,
|
1 |
productoEscalar [1,2,3] [4,5,6] == 32 |
[expand title=”Soluciones en Haskell”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
import Numeric.LinearAlgebra ((<.>), vector) import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== productoEscalar1 :: [Integer] -> [Integer] -> Integer productoEscalar1 xs ys = sum [x*y | (x,y) <- zip xs ys] -- 2ª solución -- =========== productoEscalar2 :: [Integer] -> [Integer] -> Integer productoEscalar2 xs ys = sum (zipWith (*) xs ys) -- 3ª solución -- =========== productoEscalar3 :: [Integer] -> [Integer] -> Integer productoEscalar3 = (sum .) . zipWith (*) -- 4ª solución -- =========== productoEscalar4 :: [Integer] -> [Integer] -> Integer productoEscalar4 [] _ = 0 productoEscalar4 _ [] = 0 productoEscalar4 (x:xs) (y:ys) = x*y + productoEscalar4 xs ys -- 5ª solución -- =========== productoEscalar5 :: [Integer] -> [Integer] -> Integer productoEscalar5 (x:xs) (y:ys) = x*y + productoEscalar5 xs ys productoEscalar5 _ _ = 0 -- 6ª solución -- =========== productoEscalar6 :: [Integer] -> [Integer] -> Integer productoEscalar6 xs ys = round (vector xs' <.> vector ys') where xs' = map fromIntegral xs ys' = map fromIntegral ys -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_productoEscalar :: [Integer] -> [Integer] -> Bool prop_productoEscalar xs ys = all (== productoEscalar1 xs ys) [productoEscalar2 xs ys, productoEscalar3 xs ys, productoEscalar4 xs ys, productoEscalar5 xs ys, productoEscalar6 xs' ys'] where n = min (length xs) (length ys) xs' = take n xs ys' = take n ys -- La comprobación es -- λ> quickCheck prop_productoEscalar -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> productoEscalar1 (replicate (2*10^6) 1) (replicate (2*10^6) 1) -- 2000000 -- (1.37 secs, 803,827,520 bytes) -- λ> productoEscalar2 (replicate (2*10^6) 1) (replicate (2*10^6) 1) -- 2000000 -- (0.69 secs, 611,008,272 bytes) -- λ> productoEscalar3 (replicate (2*10^6) 1) (replicate (2*10^6) 1) -- 2000000 -- (0.69 secs, 611,008,536 bytes) -- λ> productoEscalar4 (replicate (2*10^6) 1) (replicate (2*10^6) 1) -- 2000000 -- (1.64 secs, 742,290,272 bytes) -- λ> productoEscalar5 (replicate (2*10^6) 1) (replicate (2*10^6) 1) -- 2000000 -- (1.63 secs, 742,290,064 bytes) -- λ> productoEscalar6 (replicate (2*10^6) 1) (replicate (2*10^6) 1) -- 2000000 -- (0.32 secs, 835,679,200 bytes) -- -- λ> productoEscalar2 (replicate (6*10^6) 1) (replicate (6*10^6) 1) -- 6000000 -- (1.90 secs, 1,831,960,336 bytes) -- λ> productoEscalar3 (replicate (6*10^6) 1) (replicate (6*10^6) 1) -- 6000000 -- (1.87 secs, 1,831,960,600 bytes) -- λ> productoEscalar6 (replicate (6*10^6) 1) (replicate (6*10^6) 1) -- 6000000 -- (0.78 secs, 2,573,005,952 bytes) |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Producto_escalar.hs).
[/expand]
[expand title=”Soluciones en Python”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
from operator import mul from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st from numpy import dot setrecursionlimit(10**6) # 1ª solución # =========== def productoEscalar1(xs: list[int], ys: list[int]) -> int: return sum(x * y for (x, y) in zip(xs, ys)) # 2ª solución # =========== def productoEscalar2(xs: list[int], ys: list[int]) -> int: return sum(map(mul, xs, ys)) # 3ª solución # =========== def productoEscalar3(xs: list[int], ys: list[int]) -> int: if xs and ys: return xs[0] * ys[0] + productoEscalar3(xs[1:], ys[1:]) return 0 # 4ª solución # =========== def productoEscalar4(xs: list[int], ys: list[int]) -> int: return dot(xs, ys) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.integers(min_value=1, max_value=100)), st.lists(st.integers(min_value=1, max_value=100))) def test_productoEscalar(xs: list[int], ys: list[int]) -> None: r = productoEscalar1(xs, ys) assert productoEscalar2(xs, ys) == r assert productoEscalar3(xs, ys) == r n = min(len(xs), len(ys)) xs1 = xs[:n] ys1 = ys[:n] assert productoEscalar4(xs1, ys1) == r # La comprobación es # src> poetry run pytest -q producto_escalar.py # 1 passed in 0.37s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('productoEscalar1([1]*(10**4), [1]*(10**4))') # 0.00 segundos # >>> tiempo('productoEscalar3([1]*(10**4), [1]*(10**4))') # 0.55 segundos # # >>> tiempo('productoEscalar1([1]*(10**7), [1]*(10**7))') # 0.60 segundos # >>> tiempo('productoEscalar2([1]*(10**7), [1]*(10**7))') # 0.26 segundos # >>> tiempo('productoEscalar4([1]*(10**7), [1]*(10**7))') # 1.73 segundos |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/producto_escalar.py).
[/expand]
4. Suma de elementos consecutivos
Definir la función
|
1 |
sumaConsecutivos :: [Integer] -> [Integer] |
tal que sumaConsecutivos xs es la suma de los pares de elementos consecutivos de la lista xs. Por ejemplo,
|
1 2 3 |
sumaConsecutivos [3,1,5,2] == [4,6,7] sumaConsecutivos [3] == [] last (sumaConsecutivos [1..10^8]) == 199999999 |
[expand title=”Soluciones en Haskell”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
import Test.QuickCheck -- 1ª solución -- =========== sumaConsecutivos1 :: [Integer] -> [Integer] sumaConsecutivos1 xs = [x+y | (x,y) <- zip xs (tail xs)] -- 2ª solución -- =========== sumaConsecutivos2 :: [Integer] -> [Integer] sumaConsecutivos2 xs = zipWith (+) xs (tail xs) -- 3ª solución -- =========== sumaConsecutivos3 :: [Integer] -> [Integer] sumaConsecutivos3 = zipWith (+) <*> tail -- 4ª solución -- =========== sumaConsecutivos4 :: [Integer] -> [Integer] sumaConsecutivos4 (x:y:zs) = x+y : sumaConsecutivos4 (y:zs) sumaConsecutivos4 _ = [] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_sumaConsecutivos :: [Integer] -> Bool prop_sumaConsecutivos xs = all (== sumaConsecutivos1 xs) [sumaConsecutivos2 xs, sumaConsecutivos3 xs, sumaConsecutivos4 xs] -- La comprobación es -- λ> quickCheck prop_sumaConsecutivos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (sumaConsecutivos1 [1..8*10^6]) -- 15999999 -- (1.98 secs, 2,176,566,784 bytes) -- λ> last (sumaConsecutivos2 [1..8*10^6]) -- 15999999 -- (0.19 secs, 1,408,566,840 bytes) -- λ> last (sumaConsecutivos3 [1..8*10^6]) -- 15999999 -- (0.19 secs, 1,408,566,936 bytes) -- λ> last (sumaConsecutivos4 [1..8*10^6]) -- 15999999 -- (2.78 secs, 2,560,566,832 bytes) |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Suma_elementos_consecutivos.hs).
[/expand]
[expand title=”Soluciones en Python”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
from operator import add from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # 1ª solución # =========== def sumaConsecutivos1(xs: list[int]) -> list[int]: return [x + y for (x, y) in zip(xs, xs[1:])] # 2ª solución # =========== def sumaConsecutivos2(xs: list[int]) -> list[int]: return list(map(add, xs, xs[1:])) # 3ª solución # =========== def sumaConsecutivos3(xs: list[int]) -> list[int]: if len(xs) >= 2: return [xs[0] + xs[1]] + sumaConsecutivos3(xs[1:]) return [] # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.integers(min_value=1, max_value=100))) def test_sumaConsecutivos(xs: list[int]) -> None: r = sumaConsecutivos1(xs) assert sumaConsecutivos2(xs) == r assert sumaConsecutivos3(xs) == r # La comprobación es # src> poetry run pytest -q suma_elementos_consecutivos.py # 1 passed in 0.26s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('sumaConsecutivos1(range(1, 10**4))') # 0.00 segundos # >>> tiempo('sumaConsecutivos2(range(1, 10**4))') # 0.00 segundos # >>> tiempo('sumaConsecutivos3(range(1, 10**4))') # 0.18 segundos # # >>> tiempo('sumaConsecutivos1(range(1, 10**8))') # 8.34 segundos # >>> tiempo('sumaConsecutivos2(range(1, 10**8))') # 6.28 segundos |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/suma_elementos_consecutivos.py).
[/expand]
5. Representación densa de polinomios
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)].
Definir la función
|
1 |
densa :: [Int] -> [(Int,Int)] |
tal que densa xs es la representación densa del polinomio cuya representación dispersa es xs. Por ejemplo,
|
1 2 3 |
densa [6,0,-5,4,-7] == [(4,6),(2,-5),(1,4),(0,-7)] densa [6,0,0,3,0,4] == [(5,6),(2,3),(0,4)] densa [0] == [(0,0)] |
[expand title=”Soluciones en Haskell”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
import Test.QuickCheck -- 1ª solución -- =========== densa1 :: [Int] -> [(Int,Int)] densa1 xs = [(x,y) | (x,y) <- zip [n-1,n-2..1] xs, y /= 0] ++ [(0, last xs)] where n = length xs -- 2ª solución -- =========== densa2 :: [Int] -> [(Int,Int)] densa2 xs = filter (\ (_,y) -> y /= 0) (zip [n-1,n-2..1] xs) ++ [(0, last xs)] where n = length xs -- 3ª solución -- =========== densa3 :: [Int] -> [(Int,Int)] densa3 xs = filter ((/= 0) . snd) (zip [n-1,n-2..1] xs) ++ [(0, last xs)] where n = length xs -- 4ª solución -- =========== densa4 :: [Int] -> [(Int,Int)] densa4 xs = aux xs (length xs - 1) where aux [y] 0 = [(0, y)] aux (y:ys) n | y == 0 = aux ys (n-1) | otherwise = (n,y) : aux ys (n-1) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_densa :: NonEmptyList Int -> Bool prop_densa (NonEmpty xs) = all (== densa1 xs) [densa2 xs, densa3 xs, densa4 xs] -- La comprobación es -- λ> quickCheck prop_densa -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (densa1 [1..2*10^6]) -- (0,2000000) -- (0.95 secs, 880,569,400 bytes) -- λ> last (densa2 [1..2*10^6]) -- (0,2000000) -- (0.52 secs, 800,569,432 bytes) -- λ> last (densa3 [1..2*10^6]) -- (0,2000000) -- (0.53 secs, 752,569,552 bytes) -- λ> last (densa4 [1..2*10^6]) -- (0,2000000) -- (3.05 secs, 1,267,842,032 bytes) -- -- λ> last (densa1 [1..10^7]) -- (0,10000000) -- (5.43 secs, 4,400,570,128 bytes) -- λ> last (densa2 [1..10^7]) -- (0,10000000) -- (3.03 secs, 4,000,570,160 bytes) -- λ> last (densa3 [1..10^7]) -- (0,10000000) -- (2.34 secs, 3,760,570,280 bytes) |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Representacion_densa_de_polinomios.hs).
[/expand]
[expand title=”Soluciones en Python”]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
from sys import setrecursionlimit from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # 1ª solución # =========== def densa1(xs: list[int]) -> list[tuple[int, int]]: n = len(xs) return [(x, y) for (x, y) in zip(range(n-1, 0, -1), xs) if y != 0] + [(0, xs[-1])] # 2ª solución # =========== def densa2(xs: list[int]) -> list[tuple[int, int]]: n = len(xs) return list(filter(lambda p: p[1] != 0, zip(range(n-1, 0, -1), xs))) + [(0, xs[-1])] # 3ª solución # =========== def densa3(xs: list[int]) -> list[tuple[int, int]]: def aux(ys: list[int], n: int) -> list[tuple[int, int]]: if n == 0: return [(0, ys[0])] if ys[0] == 0: return aux(ys[1:], n-1) return [(n, ys[0])] + aux(ys[1:], n-1) return aux(xs, len(xs) - 1) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.integers(), min_size=1)) def test_densa(xs: list[int]) -> None: r = densa1(xs) assert densa2(xs) == r assert densa3(xs) == r # La comprobación es # src> poetry run pytest -q representacion_densa_de_polinomios.py # 1 passed in 0.27s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('densa1(range(1, 10**4))') # 0.00 segundos # >>> tiempo('densa2(range(1, 10**4))') # 0.00 segundos # >>> tiempo('densa3(range(1, 10**4))') # 0.25 segundos # # >>> tiempo('densa1(range(1, 10**7))') # 1.87 segundos # >>> tiempo('densa2(range(1, 10**7))') # 2.15 segundos |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium-Python/blob/main/src/representacion_densa_de_polinomios.py)
[/expand]