septiembre 2022 – Exercitium

Triángulo aritmético

PorJosé A. Alonso 30-septiembre-202214-diciembre-2022

Los triángulos aritméticos se forman como sigue

    1
    2  3
    4  5  6
    7  8  9 10
   11 12 13 14 15
   16 17 18 19 20 21

2 3

4 5 6

7 8 9 10

11 12 13 14 15

16 17 18 19 20 21

Definir las funciones

   linea     :: Integer -> [Integer]
   triangulo :: Integer -> [[Integer]]

1 2	linea :: Integer -> [Integer] triangulo :: Integer -> [[Integer]]

tales que

linea n es la línea n-ésima de los triángulos aritméticos. Por ejemplo,

     linea 4  ==  [7,8,9,10]
     linea 5  ==  [11,12,13,14,15]
     head (linea (10^20)) == 4999999999999999999950000000000000000001

linea 4 == [7,8,9,10]

linea 5 == [11,12,13,14,15]

head (linea (10^20)) == 4999999999999999999950000000000000000001

triangulo n es el triángulo aritmético de altura n. Por ejemplo,

     triangulo 3  ==  [[1],[2,3],[4,5,6]]
     triangulo 4  ==  [[1],[2,3],[4,5,6],[7,8,9,10]]

1 2	triangulo 3 == [[1],[2,3],[4,5,6]] triangulo 4 == [[1],[2,3],[4,5,6],[7,8,9,10]]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

-- 1ª definición de línea
-- ======================

linea1 :: Integer -> [Integer]
linea1 n = [suma1 (n-1)+1..suma1 n]

-- (suma n) es la suma de los n primeros números. Por ejemplo,
--    suma 3  ==  6
suma1 :: Integer -> Integer
suma1 n = sum [1..n]

-- 2ª definición de línea
-- ======================

linea2 :: Integer -> [Integer]
linea2 n = [s+1..s+n]
  where s = suma1 (n-1)

-- 3ª definición de línea
-- ======================

linea3 :: Integer -> [Integer]
linea3 n = [s+1..s+n]
  where s = suma2 (n-1)

suma2 :: Integer -> Integer
suma2 n = (1+n)*n `div` 2

-- Comprobación de equivalencia de linea
-- =====================================

-- La propiedad es
prop_linea :: Positive Integer -> Bool
prop_linea (Positive n) =
  all (== linea1 n)
      [linea2 n,
       linea3 n]

-- La comprobación es
--    λ> quickCheck prop_linea
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia de linea
-- ==================================

-- La comparación es
--    λ> last (linea1 (10^7))
--    50000005000000
--    (5.10 secs, 3,945,159,856 bytes)
--    λ> last (linea2 (10^7))
--    50000005000000
--    (3.11 secs, 2,332,859,512 bytes)
--    λ> last (linea3 (10^7))
--    50000005000000
--    (0.16 secs, 720,559,384 bytes)

-- 1ª definición de triangulo
-- ==========================

triangulo1 :: Integer -> [[Integer]]
triangulo1 n = [linea1 m | m <- [1..n]]

-- 2ª definición de triangulo
-- ==========================

triangulo2 :: Integer -> [[Integer]]
triangulo2 n = [linea2 m | m <- [1..n]]

-- 3ª definición de triangulo
-- ==========================

triangulo3 :: Integer -> [[Integer]]
triangulo3 n = [linea3 m | m <- [1..n]]

-- Comprobación de equivalencia de triangulo
-- =========================================

-- La propiedad es
prop_triangulo :: Positive Integer -> Bool
prop_triangulo (Positive n) =
  all (== triangulo1 n)
      [triangulo2 n,
       triangulo3 n]

-- La comprobación es
--    λ> quickCheck prop_triangulo
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia de triangulo
-- ======================================

-- La comparación es
--    λ> last (last (triangulo1 (3*10^6)))
--    4500001500000
--    (2.25 secs, 1,735,919,184 bytes)
--    λ> last (last (triangulo2 (3*10^6)))
--    4500001500000
--    (1.62 secs, 1,252,238,872 bytes)
--    λ> last (last (triangulo3 (3*10^6)))
--    4500001500000
--    (0.79 secs, 768,558,776 bytes)

100

101

102

103

import Test.QuickCheck

-- 1ª definición de línea

-- ======================

linea1 :: Integer -> [Integer]

linea1 n = [suma1 (n-1)+1..suma1 n]

-- (suma n) es la suma de los n primeros números. Por ejemplo,

-- suma 3 == 6

suma1 :: Integer -> Integer

suma1 n = sum [1..n]

-- 2ª definición de línea

-- ======================

linea2 :: Integer -> [Integer]

linea2 n = [s+1..s+n]

where s = suma1 (n-1)

-- 3ª definición de línea

-- ======================

linea3 :: Integer -> [Integer]

linea3 n = [s+1..s+n]

where s = suma2 (n-1)

suma2 :: Integer -> Integer

suma2 n = (1+n)*n `div` 2

-- Comprobación de equivalencia de linea

-- =====================================

-- La propiedad es

prop_linea :: Positive Integer -> Bool

prop_linea (Positive n) =

all (== linea1 n)

[linea2 n,

linea3 n]

-- La comprobación es

-- λ> quickCheck prop_linea

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de linea

-- ==================================

-- La comparación es

-- λ> last (linea1 (10^7))

-- 50000005000000

-- (5.10 secs, 3,945,159,856 bytes)

-- λ> last (linea2 (10^7))

-- 50000005000000

-- (3.11 secs, 2,332,859,512 bytes)

-- λ> last (linea3 (10^7))

-- 50000005000000

-- (0.16 secs, 720,559,384 bytes)

-- 1ª definición de triangulo

-- ==========================

triangulo1 :: Integer -> [[Integer]]

triangulo1 n = [linea1 m | m <- [1..n]]

-- 2ª definición de triangulo

-- ==========================

triangulo2 :: Integer -> [[Integer]]

triangulo2 n = [linea2 m | m <- [1..n]]

-- 3ª definición de triangulo

-- ==========================

triangulo3 :: Integer -> [[Integer]]

triangulo3 n = [linea3 m | m <- [1..n]]

-- Comprobación de equivalencia de triangulo

-- =========================================

-- La propiedad es

prop_triangulo :: Positive Integer -> Bool

prop_triangulo (Positive n) =

all (== triangulo1 n)

[triangulo2 n,

triangulo3 n]

-- La comprobación es

-- λ> quickCheck prop_triangulo

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de triangulo

-- ======================================

-- La comparación es

-- λ> last (last (triangulo1 (3*10^6)))

-- 4500001500000

-- (2.25 secs, 1,735,919,184 bytes)

-- λ> last (last (triangulo2 (3*10^6)))

-- 4500001500000

-- (1.62 secs, 1,252,238,872 bytes)

-- λ> last (last (triangulo3 (3*10^6)))

-- 4500001500000

-- (0.79 secs, 768,558,776 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer
from hypothesis import given, strategies as st

# 1ª definición de línea
# ======================

# suma(n) es la suma de los n primeros números. Por ejemplo,
#    suma(3)  ==  6
def suma1(n: int) -> int:
    return sum(range(1, n + 1))

def linea1(n: int) -> list[int]:
    return list(range(suma1(n - 1) + 1, suma1(n) + 1))

# 2ª definición de línea
# ======================

def linea2(n: int) -> list[int]:
    s = suma1(n-1)
    return list(range(s + 1, s + n + 1))

# 3ª definición de línea
# ======================

def suma2(n: int) -> int:
    return (1 + n) * n // 2

def linea3(n: int) -> list[int]:
    s = suma2(n-1)
    return list(range(s + 1, s + n + 1))

# Comprobación de equivalencia de linea
# =====================================

@given(st.integers(min_value=1, max_value=1000))
def test_suma(n):
    r = linea1(n)
    assert linea2(n) == r
    assert linea3(n) == r

# La comprobación es
#    src> poetry run pytest -q triangulo_aritmetico.py
#    1 passed in 0.15s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('linea1(10**7)')
#    0.53 segundos
#    >>> tiempo('linea2(10**7)')
#    0.40 segundos
#    >>> tiempo('linea3(10**7)')
#    0.29 segundos

# 1ª definición de triangulo
# ==========================

def triangulo1(n: int) -> list[list[int]]:
    return [linea1(m) for m in range(1, n + 1)]

# 2ª definición de triangulo
# ==========================

def triangulo2(n: int) -> list[list[int]]:
    return [linea2(m) for m in range(1, n + 1)]

# 3ª definición de triangulo
# ==========================

def triangulo3(n: int) -> list[list[int]]:
    return [linea3(m) for m in range(1, n + 1)]

# Comprobación de equivalencia de triangulo
# =========================================

@given(st.integers(min_value=1, max_value=1000))
def test_triangulo(n):
    r = triangulo1(n)
    assert triangulo2(n) == r
    assert triangulo3(n) == r

# La comprobación es
#    src> poetry run pytest -q triangulo_aritmetico.py
#    1 passed in 3.44s

# Comparación de eficiencia de triangulo
# ======================================
#
# La comparación es
#    >>> tiempo('triangulo1(10**4)')
#    2.58 segundos
#    >>> tiempo('triangulo2(10**4)')
#    1.91 segundos
#    >>> tiempo('triangulo3(10**4)')
#    1.26 segundos

100

101

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

# 1ª definición de línea

# ======================

# suma(n) es la suma de los n primeros números. Por ejemplo,

# suma(3) == 6

def suma1(n: int) -> int:

return sum(range(1, n + 1))

def linea1(n: int) -> list[int]:

return list(range(suma1(n - 1) + 1, suma1(n) + 1))

# 2ª definición de línea

# ======================

def linea2(n: int) -> list[int]:

s = suma1(n-1)

return list(range(s + 1, s + n + 1))

# 3ª definición de línea

# ======================

def suma2(n: int) -> int:

return (1 + n) * n // 2

def linea3(n: int) -> list[int]:

s = suma2(n-1)

return list(range(s + 1, s + n + 1))

# Comprobación de equivalencia de linea

# =====================================

@given(st.integers(min_value=1, max_value=1000))

def test_suma(n):

r = linea1(n)

assert linea2(n) == r

assert linea3(n) == r

# La comprobación es

# src> poetry run pytest -q triangulo_aritmetico.py

# 1 passed in 0.15s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('linea1(10**7)')

# 0.53 segundos

# >>> tiempo('linea2(10**7)')

# 0.40 segundos

# >>> tiempo('linea3(10**7)')

# 0.29 segundos

# 1ª definición de triangulo

# ==========================

def triangulo1(n: int) -> list[list[int]]:

return [linea1(m) for m in range(1, n + 1)]

# 2ª definición de triangulo

# ==========================

def triangulo2(n: int) -> list[list[int]]:

return [linea2(m) for m in range(1, n + 1)]

# 3ª definición de triangulo

# ==========================

def triangulo3(n: int) -> list[list[int]]:

return [linea3(m) for m in range(1, n + 1)]

# Comprobación de equivalencia de triangulo

# =========================================

@given(st.integers(min_value=1, max_value=1000))

def test_triangulo(n):

r = triangulo1(n)

assert triangulo2(n) == r

assert triangulo3(n) == r

# La comprobación es

# src> poetry run pytest -q triangulo_aritmetico.py

# 1 passed in 3.44s

# Comparación de eficiencia de triangulo

# ======================================

# La comparación es

# >>> tiempo('triangulo1(10**4)')

# 2.58 segundos

# >>> tiempo('triangulo2(10**4)')

# 1.91 segundos

# >>> tiempo('triangulo3(10**4)')

# 1.26 segundos

El código se encuentra en GitHub.

Suma de cuadrados menos cuadrado de la suma

PorJosé A. Alonso 29-septiembre-202214-diciembre-2022

Definir la función

   euler6 :: Integer -> Integer

1	euler6 :: Integer -> Integer

tal que euler6 n es la diferencia entre el cuadrado de la suma de los n primeros números y la suma de los cuadrados de los nprimeros números. Por ejemplo,

   euler6 10       ==  2640
   euler6 (10^10)  ==  2500000000166666666641666666665000000000

1 2	euler6 10 == 2640 euler6 (10^10) == 2500000000166666666641666666665000000000

Nota: Este ejercicio está basado en el problema 6 del proyecto Euler.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (foldl')
import Test.QuickCheck

-- 1ª solución
-- ===========

euler6a :: Integer -> Integer
euler6a n = (suma1 n)^2 - sumaDeCuadrados1 n

-- (suma n) es la suma de los n primeros números. Por ejemplo,
--    suma 3  ==  6
suma1 :: Integer -> Integer
suma1 n = sum [1..n]

-- (sumaDeCuadrados n) es la suma de los cuadrados de los
-- primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,
--    sumaDeCuadrados 3    ==  14
--    sumaDeCuadrados 100  ==  338350

sumaDeCuadrados1 :: Integer -> Integer
sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

-- 2ª solución
-- ===========

euler6b :: Integer -> Integer
euler6b n = (suma2 n)^ 2 - sumaDeCuadrados2 n

suma2 :: Integer -> Integer
suma2 n = (1+n)*n `div` 2

sumaDeCuadrados2 :: Integer -> Integer
sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

-- 3ª solución
-- ===========

euler6c :: Integer -> Integer
euler6c n = (suma3 n)^ 2 - sumaDeCuadrados3 n

suma3 :: Integer -> Integer
suma3 1 = 1
suma3 n = n + suma3 (n-1)

sumaDeCuadrados3 :: Integer -> Integer
sumaDeCuadrados3 1 = 1
sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

-- 4ª solución
-- ===========

euler6d :: Integer -> Integer
euler6d n = (suma4 n)^ 2 - sumaDeCuadrados4 n

suma4 :: Integer -> Integer
suma4 n = foldl (+) 0 [0..n]

sumaDeCuadrados4 :: Integer -> Integer
sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

-- 5ª solución
-- ===========

euler6e :: Integer -> Integer
euler6e n = (suma5 n)^ 2 - sumaDeCuadrados5 n

suma5 :: Integer -> Integer
suma5 n = foldl' (+) 0 [0..n]

sumaDeCuadrados5 :: Integer -> Integer
sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_euler6 :: Positive Integer -> Bool
prop_euler6 (Positive n) =
  all (== euler6a n)
      [euler6b n,
       euler6c n,
       euler6d n,
       euler6e n]

-- La comprobación es
--    λ> quickCheck prop_euler6
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> euler6a (3*10^6)
--    20250004499997749999500000
--    (3.32 secs, 2,577,174,640 bytes)
--    λ> euler6b (3*10^6)
--    20250004499997749999500000
--    (0.01 secs, 569,288 bytes)
--    λ> euler6c (3*10^6)
--    20250004499997749999500000
--    (5.60 secs, 2,849,479,288 bytes)
--    λ> euler6d (3*10^6)
--    20250004499997749999500000
--    (2.52 secs, 2,457,175,248 bytes)
--    λ> euler6e (3*10^6)
--    20250004499997749999500000
--    (1.08 secs, 2,016,569,472 bytes)
--
--    λ> euler6a (10^7)
--    2500000166666641666665000000
--    (11.14 secs, 8,917,796,648 bytes)
--    λ> euler6b (10^7)
--    2500000166666641666665000000
--    (0.01 secs, 570,752 bytes)
--    λ> euler6c (10^7)
--    *** Exception: stack overflow
--    λ> euler6d (10^7)
--    2500000166666641666665000000
--    (9.47 secs, 8,517,796,760 bytes)
--    λ> euler6e (10^7)
--    2500000166666641666665000000
--    (3.78 secs, 7,049,100,104 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

import Data.List (foldl')

import Test.QuickCheck

-- 1ª solución

-- ===========

euler6a :: Integer -> Integer

euler6a n = (suma1 n)^2 - sumaDeCuadrados1 n

-- (suma n) es la suma de los n primeros números. Por ejemplo,

-- suma 3 == 6

suma1 :: Integer -> Integer

suma1 n = sum [1..n]

-- (sumaDeCuadrados n) es la suma de los cuadrados de los

-- primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,

-- sumaDeCuadrados 3 == 14

-- sumaDeCuadrados 100 == 338350

sumaDeCuadrados1 :: Integer -> Integer

sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

-- 2ª solución

-- ===========

euler6b :: Integer -> Integer

euler6b n = (suma2 n)^ 2 - sumaDeCuadrados2 n

suma2 :: Integer -> Integer

suma2 n = (1+n)*n `div` 2

sumaDeCuadrados2 :: Integer -> Integer

sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

-- 3ª solución

-- ===========

euler6c :: Integer -> Integer

euler6c n = (suma3 n)^ 2 - sumaDeCuadrados3 n

suma3 :: Integer -> Integer

suma3 1 = 1

suma3 n = n + suma3 (n-1)

sumaDeCuadrados3 :: Integer -> Integer

sumaDeCuadrados3 1 = 1

sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

-- 4ª solución

-- ===========

euler6d :: Integer -> Integer

euler6d n = (suma4 n)^ 2 - sumaDeCuadrados4 n

suma4 :: Integer -> Integer

suma4 n = foldl (+) 0 [0..n]

sumaDeCuadrados4 :: Integer -> Integer

sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

-- 5ª solución

-- ===========

euler6e :: Integer -> Integer

euler6e n = (suma5 n)^ 2 - sumaDeCuadrados5 n

suma5 :: Integer -> Integer

suma5 n = foldl' (+) 0 [0..n]

sumaDeCuadrados5 :: Integer -> Integer

sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_euler6 :: Positive Integer -> Bool

prop_euler6 (Positive n) =

all (== euler6a n)

[euler6b n,

euler6c n,

euler6d n,

euler6e n]

-- La comprobación es

-- λ> quickCheck prop_euler6

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> euler6a (3*10^6)

-- 20250004499997749999500000

-- (3.32 secs, 2,577,174,640 bytes)

-- λ> euler6b (3*10^6)

-- 20250004499997749999500000

-- (0.01 secs, 569,288 bytes)

-- λ> euler6c (3*10^6)

-- 20250004499997749999500000

-- (5.60 secs, 2,849,479,288 bytes)

-- λ> euler6d (3*10^6)

-- 20250004499997749999500000

-- (2.52 secs, 2,457,175,248 bytes)

-- λ> euler6e (3*10^6)

-- 20250004499997749999500000

-- (1.08 secs, 2,016,569,472 bytes)

-- λ> euler6a (10^7)

-- 2500000166666641666665000000

-- (11.14 secs, 8,917,796,648 bytes)

-- λ> euler6b (10^7)

-- 2500000166666641666665000000

-- (0.01 secs, 570,752 bytes)

-- λ> euler6c (10^7)

-- *** Exception: stack overflow

-- λ> euler6d (10^7)

-- 2500000166666641666665000000

-- (9.47 secs, 8,517,796,760 bytes)

-- λ> euler6e (10^7)

-- 2500000166666641666665000000

-- (3.78 secs, 7,049,100,104 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from functools import reduce
from operator import add
from sys import setrecursionlimit
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
setrecursionlimit(10**6)

# 1ª solución
# ===========

def euler6a(n: int) -> int:
    return suma1(n)**2 - sumaDeCuadrados1(n)

# suma(n) es la suma de los n primeros números. Por ejemplo,
#    suma(3)  ==  6
def suma1(n: int) -> int:
    return sum(range(1, n + 1))

# sumaDeCuadrados(n) es la suma de los cuadrados de los
# primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,
#    sumaDeCuadrados(3)    ==  14
#    sumaDeCuadrados(100)  ==  338350
def sumaDeCuadrados1(n: int) -> int:
    return sum(x**2 for x in range(1, n + 1))

# 2ª solución
# ===========

def euler6b(n: int) -> int:
    return suma2(n)**2 - sumaDeCuadrados2(n)

def suma2(n: int) -> int:
    return (1 + n) * n // 2

def sumaDeCuadrados2(n: int) -> int:
    return n * (n + 1) * (2 * n + 1) // 6

# 3ª solución
# ===========

def euler6c(n: int) -> int:
    return suma3(n)**2 - sumaDeCuadrados3(n)

def suma3(n: int) -> int:
    if n == 1:
        return 1
    return n + suma3(n - 1)

def sumaDeCuadrados3(n: int) -> int:
    if n == 1:
        return 1
    return n**2 + sumaDeCuadrados3(n - 1)

# 4ª solución
# ===========

def euler6d(n: int) -> int:
    return suma4(n)**2 - sumaDeCuadrados4(n)

def suma4(n: int) -> int:
    return reduce(add, range(1, n + 1))

def sumaDeCuadrados4(n: int) -> int:
    return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución
# ===========

def euler6e(n: int) -> int:
    return suma5(n)**2 - sumaDeCuadrados5(n)

def suma5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x
        x = x + 1
    return r

def sumaDeCuadrados5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x**2
        x = x + 1
    return r

# 6ª solución
# ===========

def euler6f(n: int) -> int:
    return suma6(n)**2 - sumaDeCuadrados6(n)

def suma6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x
    return r

def sumaDeCuadrados6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x**2
    return r

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_euler6(n):
    r = euler6a(n)
    assert euler6b(n) == r
    assert euler6c(n) == r
    assert euler6d(n) == r
    assert euler6e(n) == r
    assert euler6f(n) == r

# La comprobación es
#    src> poetry run pytest -q suma_de_cuadrados_menos_cuadrado_de_la_suma.py
#    1 passed in 0.21s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('euler6a(20000)')
#    0.02 segundos
#    >>> tiempo('euler6b(20000)')
#    0.00 segundos
#    >>> tiempo('euler6c(20000)')
#    0.02 segundos
#    >>> tiempo('euler6d(20000)')
#    0.01 segundos
#    >>> tiempo('euler6e(20000)')
#    0.01 segundos
#    >>> tiempo('euler6f(20000)')
#    0.01 segundos
#
#    >>> tiempo('euler6a(10**7)')
#    2.26 segundos
#    >>> tiempo('euler6b(10**7)')
#    0.00 segundos
#    >>> tiempo('euler6d(10**7)')
#    2.58 segundos
#    >>> tiempo('euler6e(10**7)')
#    2.89 segundos
#    >>> tiempo('euler6f(10**7)')
#    2.45 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

from functools import reduce

from operator import add

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

def euler6a(n: int) -> int:

return suma1(n)**2 - sumaDeCuadrados1(n)

# suma(n) es la suma de los n primeros números. Por ejemplo,

# suma(3) == 6

def suma1(n: int) -> int:

return sum(range(1, n + 1))

# sumaDeCuadrados(n) es la suma de los cuadrados de los

# primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,

# sumaDeCuadrados(3) == 14

# sumaDeCuadrados(100) == 338350

def sumaDeCuadrados1(n: int) -> int:

return sum(x**2 for x in range(1, n + 1))

# 2ª solución

# ===========

def euler6b(n: int) -> int:

return suma2(n)**2 - sumaDeCuadrados2(n)

def suma2(n: int) -> int:

return (1 + n) * n // 2

def sumaDeCuadrados2(n: int) -> int:

return n * (n + 1) * (2 * n + 1) // 6

# 3ª solución

# ===========

def euler6c(n: int) -> int:

return suma3(n)**2 - sumaDeCuadrados3(n)

def suma3(n: int) -> int:

if n == 1:

return 1

return n + suma3(n - 1)

def sumaDeCuadrados3(n: int) -> int:

if n == 1:

return 1

return n**2 + sumaDeCuadrados3(n - 1)

# 4ª solución

# ===========

def euler6d(n: int) -> int:

return suma4(n)**2 - sumaDeCuadrados4(n)

def suma4(n: int) -> int:

return reduce(add, range(1, n + 1))

def sumaDeCuadrados4(n: int) -> int:

return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución

# ===========

def euler6e(n: int) -> int:

return suma5(n)**2 - sumaDeCuadrados5(n)

def suma5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x

x = x + 1

return r

def sumaDeCuadrados5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x**2

x = x + 1

return r

# 6ª solución

# ===========

def euler6f(n: int) -> int:

return suma6(n)**2 - sumaDeCuadrados6(n)

def suma6(n: int) -> int:

r = 0

for x in range(1, n + 1):

r = r + x

return r

def sumaDeCuadrados6(n: int) -> int:

r = 0

for x in range(1, n + 1):

r = r + x**2

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000))

def test_euler6(n):

r = euler6a(n)

assert euler6b(n) == r

assert euler6c(n) == r

assert euler6d(n) == r

assert euler6e(n) == r

assert euler6f(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_cuadrados_menos_cuadrado_de_la_suma.py

# 1 passed in 0.21s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('euler6a(20000)')

# 0.02 segundos

# >>> tiempo('euler6b(20000)')

# 0.00 segundos

# >>> tiempo('euler6c(20000)')

# 0.02 segundos

# >>> tiempo('euler6d(20000)')

# 0.01 segundos

# >>> tiempo('euler6e(20000)')

# 0.01 segundos

# >>> tiempo('euler6f(20000)')

# 0.01 segundos

# >>> tiempo('euler6a(10**7)')

# 2.26 segundos

# >>> tiempo('euler6b(10**7)')

# 0.00 segundos

# >>> tiempo('euler6d(10**7)')

# 2.58 segundos

# >>> tiempo('euler6e(10**7)')

# 2.89 segundos

# >>> tiempo('euler6f(10**7)')

# 2.45 segundos

El código se encuentra en GitHub.

Suma de los cuadrados de los primeros números naturales

PorJosé A. Alonso 28-septiembre-202214-diciembre-2022

Definir la función

   sumaDeCuadrados :: Integer -> Integer

1	sumaDeCuadrados :: Integer -> Integer

tal que sumaDeCuadrados n es la suma de los cuadrados de los primeros n números; es decir, 1² + 2² + … + n². Por ejemplo,

   sumaDeCuadrados 3    ==  14
   sumaDeCuadrados 100  ==  338350
   length (show (sumaDeCuadrados (10^100)))  ==  300

sumaDeCuadrados 3 == 14

sumaDeCuadrados 100 == 338350

length (show (sumaDeCuadrados (10^100))) == 300

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (foldl')
import Test.QuickCheck

-- 1ª solución
-- ===========

sumaDeCuadrados1 :: Integer -> Integer
sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

-- 2ª solución
-- ===========

sumaDeCuadrados2 :: Integer -> Integer
sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

-- 3ª solución
-- ===========

sumaDeCuadrados3 :: Integer -> Integer
sumaDeCuadrados3 1 = 1
sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

-- 4ª solución
-- ===========

sumaDeCuadrados4 :: Integer -> Integer
sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

-- 5ª solución
-- ===========

sumaDeCuadrados5 :: Integer -> Integer
sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_sumaDeCuadrados :: Positive Integer -> Bool
prop_sumaDeCuadrados (Positive n) =
  all (== sumaDeCuadrados1 n)
      [sumaDeCuadrados2 n,
       sumaDeCuadrados3 n,
       sumaDeCuadrados4 n,
       sumaDeCuadrados5 n]

-- La comprobación es
--    λ> quickCheck prop_sumaDeCuadrados
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> sumaDeCuadrados1 (2*10^6)
--    2666668666667000000
--    (1.90 secs, 1,395,835,576 bytes)
--    λ> sumaDeCuadrados2 (2*10^6)
--    2666668666667000000
--    (0.01 secs, 563,168 bytes)
--    λ> sumaDeCuadrados3 (2*10^6)
--    2666668666667000000
--    (2.37 secs, 1,414,199,400 bytes)
--    λ> sumaDeCuadrados4 (2*10^6)
--    2666668666667000000
--    (1.33 secs, 1,315,836,128 bytes)
--    λ> sumaDeCuadrados5 (2*10^6)
--    2666668666667000000
--    (0.71 secs, 1,168,563,384 bytes)

import Data.List (foldl')

import Test.QuickCheck

-- 1ª solución

-- ===========

sumaDeCuadrados1 :: Integer -> Integer

sumaDeCuadrados1 n = sum [x^2 | x <- [1..n]]

-- 2ª solución

-- ===========

sumaDeCuadrados2 :: Integer -> Integer

sumaDeCuadrados2 n = n*(n+1)*(2*n+1) `div` 6

-- 3ª solución

-- ===========

sumaDeCuadrados3 :: Integer -> Integer

sumaDeCuadrados3 1 = 1

sumaDeCuadrados3 n = n^2 + sumaDeCuadrados3 (n-1)

-- 4ª solución

-- ===========

sumaDeCuadrados4 :: Integer -> Integer

sumaDeCuadrados4 n = foldl (+) 0 (map (^2) [0..n])

-- 5ª solución

-- ===========

sumaDeCuadrados5 :: Integer -> Integer

sumaDeCuadrados5 n = foldl' (+) 0 (map (^2) [0..n])

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_sumaDeCuadrados :: Positive Integer -> Bool

prop_sumaDeCuadrados (Positive n) =

all (== sumaDeCuadrados1 n)

[sumaDeCuadrados2 n,

sumaDeCuadrados3 n,

sumaDeCuadrados4 n,

sumaDeCuadrados5 n]

-- La comprobación es

-- λ> quickCheck prop_sumaDeCuadrados

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> sumaDeCuadrados1 (2*10^6)

-- 2666668666667000000

-- (1.90 secs, 1,395,835,576 bytes)

-- λ> sumaDeCuadrados2 (2*10^6)

-- 2666668666667000000

-- (0.01 secs, 563,168 bytes)

-- λ> sumaDeCuadrados3 (2*10^6)

-- 2666668666667000000

-- (2.37 secs, 1,414,199,400 bytes)

-- λ> sumaDeCuadrados4 (2*10^6)

-- 2666668666667000000

-- (1.33 secs, 1,315,836,128 bytes)

-- λ> sumaDeCuadrados5 (2*10^6)

-- 2666668666667000000

-- (0.71 secs, 1,168,563,384 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from operator import add
from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
setrecursionlimit(10**6)

# 1ª solución
# ===========

def sumaDeCuadrados1(n: int) -> int:
    return sum(x**2 for x in range(1, n + 1))

# 2ª solución
# ===========

def sumaDeCuadrados2(n: int) -> int:
    return n * (n + 1) * (2 * n + 1) // 6

# 3ª solución
# ===========

def sumaDeCuadrados3(n: int) -> int:
    if n == 1:
        return 1
    return n**2 + sumaDeCuadrados3(n - 1)

# 4ª solución
# ===========

def sumaDeCuadrados4(n: int) -> int:
    return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución
# ===========

def sumaDeCuadrados5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x**2
        x = x + 1
    return r

# 6ª solución
# ===========

def sumaDeCuadrados6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x**2
    return r

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_sumaDeCuadrados(n):
    r = sumaDeCuadrados1(n)
    assert sumaDeCuadrados2(n) == r
    assert sumaDeCuadrados3(n) == r
    assert sumaDeCuadrados4(n) == r
    assert sumaDeCuadrados5(n) == r
    assert sumaDeCuadrados6(n) == r

# La comprobación es
#    src> poetry run pytest -q suma_de_los_cuadrados_de_los_primeros_numeros_naturales.py
#    1 passed in 0.19s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('sumaDeCuadrados1(20000)')
#    0.01 segundos
#    >>> tiempo('sumaDeCuadrados2(20000)')
#    0.00 segundos
#    >>> tiempo('sumaDeCuadrados3(20000)')
#    0.02 segundos
#    >>> tiempo('sumaDeCuadrados4(20000)')
#    0.02 segundos
#    >>> tiempo('sumaDeCuadrados5(20000)')
#    0.02 segundos
#    >>> tiempo('sumaDeCuadrados6(20000)')
#    0.02 segundos
#
#    >>> tiempo('sumaDeCuadrados1(10**7)')
#    2.19 segundos
#    >>> tiempo('sumaDeCuadrados2(10**7)')
#    0.00 segundos
#    >>> tiempo('sumaDeCuadrados4(10**7)')
#    2.48 segundos
#    >>> tiempo('sumaDeCuadrados5(10**7)')
#    2.53 segundos
#    >>> tiempo('sumaDeCuadrados6(10**7)')
#    2.22 segundos

100

101

from operator import add

from functools import reduce

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

def sumaDeCuadrados1(n: int) -> int:

return sum(x**2 for x in range(1, n + 1))

# 2ª solución

# ===========

def sumaDeCuadrados2(n: int) -> int:

return n * (n + 1) * (2 * n + 1) // 6

# 3ª solución

# ===========

def sumaDeCuadrados3(n: int) -> int:

if n == 1:

return 1

return n**2 + sumaDeCuadrados3(n - 1)

# 4ª solución

# ===========

def sumaDeCuadrados4(n: int) -> int:

return reduce(add, (x**2 for x in range(1, n + 1)))

# 5ª solución

# ===========

def sumaDeCuadrados5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x**2

x = x + 1

return r

# 6ª solución

# ===========

def sumaDeCuadrados6(n: int) -> int:

r = 0

for x in range(1, n + 1):

r = r + x**2

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000))

def test_sumaDeCuadrados(n):

r = sumaDeCuadrados1(n)

assert sumaDeCuadrados2(n) == r

assert sumaDeCuadrados3(n) == r

assert sumaDeCuadrados4(n) == r

assert sumaDeCuadrados5(n) == r

assert sumaDeCuadrados6(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_los_cuadrados_de_los_primeros_numeros_naturales.py

# 1 passed in 0.19s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('sumaDeCuadrados1(20000)')

# 0.01 segundos

# >>> tiempo('sumaDeCuadrados2(20000)')

# 0.00 segundos

# >>> tiempo('sumaDeCuadrados3(20000)')

# 0.02 segundos

# >>> tiempo('sumaDeCuadrados4(20000)')

# 0.02 segundos

# >>> tiempo('sumaDeCuadrados5(20000)')

# 0.02 segundos

# >>> tiempo('sumaDeCuadrados6(20000)')

# 0.02 segundos

# >>> tiempo('sumaDeCuadrados1(10**7)')

# 2.19 segundos

# >>> tiempo('sumaDeCuadrados2(10**7)')

# 0.00 segundos

# >>> tiempo('sumaDeCuadrados4(10**7)')

# 2.48 segundos

# >>> tiempo('sumaDeCuadrados5(10**7)')

# 2.53 segundos

# >>> tiempo('sumaDeCuadrados6(10**7)')

# 2.22 segundos

El código se encuentra en GitHub.

Suma de los primeros números naturales

PorJosé A. Alonso 27-septiembre-202214-diciembre-2022

Definir la función

   suma :: Integer -> Integer

1	suma :: Integer -> Integer

tal suma n es la suma de los n primeros números. Por ejemplo,

   suma 3  ==  6
   length (show (suma (10^100)))  ==  200

1 2	suma 3 == 6 length (show (suma (10^100))) == 200

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (foldl')
import Test.QuickCheck

-- 1ª solución
-- ===========

suma1 :: Integer -> Integer
suma1 n = sum [1..n]

-- 2ª solución
-- ===========

suma2 :: Integer -> Integer
suma2 n = (1+n)*n `div` 2

-- 3ª solución
-- ===========

suma3 :: Integer -> Integer
suma3 1 = 1
suma3 n = n + suma3 (n-1)

-- 4ª solución
-- ===========

suma4 :: Integer -> Integer
suma4 n = foldl (+) 0 [0..n]

-- 5ª solución
-- ===========

suma5 :: Integer -> Integer
suma5 n = foldl' (+) 0 [0..n]

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_suma :: Positive Integer -> Bool
prop_suma (Positive n) =
  all (== suma1 n)
      [suma2 n,
       suma3 n,
       suma4 n,
       suma5 n]

-- La comprobación es
--    λ> quickCheck prop_suma
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> suma1 (5*10^6)
--    12500002500000
--    (1.23 secs, 806,692,792 bytes)
--    λ> suma2 (5*10^6)
--    12500002500000
--    (0.02 secs, 559,064 bytes)
--    λ> suma3 (5*10^6)
--    12500002500000
--    (3.06 secs, 1,214,684,352 bytes)
--    λ> suma4 (5*10^6)
--    12500002500000
--    (1.25 secs, 806,692,848 bytes)
--    λ> suma5 (5*10^6)
--    12500002500000
--    (0.26 secs, 440,559,048 bytes)

import Data.List (foldl')

import Test.QuickCheck

-- 1ª solución

-- ===========

suma1 :: Integer -> Integer

suma1 n = sum [1..n]

-- 2ª solución

-- ===========

suma2 :: Integer -> Integer

suma2 n = (1+n)*n `div` 2

-- 3ª solución

-- ===========

suma3 :: Integer -> Integer

suma3 1 = 1

suma3 n = n + suma3 (n-1)

-- 4ª solución

-- ===========

suma4 :: Integer -> Integer

suma4 n = foldl (+) 0 [0..n]

-- 5ª solución

-- ===========

suma5 :: Integer -> Integer

suma5 n = foldl' (+) 0 [0..n]

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_suma :: Positive Integer -> Bool

prop_suma (Positive n) =

all (== suma1 n)

[suma2 n,

suma3 n,

suma4 n,

suma5 n]

-- La comprobación es

-- λ> quickCheck prop_suma

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> suma1 (5*10^6)

-- 12500002500000

-- (1.23 secs, 806,692,792 bytes)

-- λ> suma2 (5*10^6)

-- 12500002500000

-- (0.02 secs, 559,064 bytes)

-- λ> suma3 (5*10^6)

-- 12500002500000

-- (3.06 secs, 1,214,684,352 bytes)

-- λ> suma4 (5*10^6)

-- 12500002500000

-- (1.25 secs, 806,692,848 bytes)

-- λ> suma5 (5*10^6)

-- 12500002500000

-- (0.26 secs, 440,559,048 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from operator import add
from functools import reduce
from sys import setrecursionlimit
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
setrecursionlimit(10**8)

# 1ª solución
# ===========

def suma1(n: int) -> int:
    return sum(range(1, n + 1))

# 2ª solución
# ===========

def suma2(n: int) -> int:
    return (1 + n) * n // 2

# 3ª solución
# ===========

def suma3(n: int) -> int:
    if n == 1:
        return 1
    return n + suma3(n - 1)

# 4ª solución
# ===========

def suma4(n: int) -> int:
    return reduce(add, range(1, n + 1))

# 5ª solución
# ===========

def suma5(n: int) -> int:
    x, r = 1, 0
    while x <= n:
        r = r + x
        x = x + 1
    return r

# 6ª solución
# ===========

def suma6(n: int) -> int:
    r = 0
    for x in range(1, n + 1):
        r = r + x
    return r

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=1, max_value=1000))
def test_suma(n):
    r = suma1(n)
    assert suma2(n) == r
    assert suma3(n) == r
    assert suma4(n) == r
    assert suma5(n) == r
    assert suma6(n) == r

# La comprobación es
#    src> poetry run pytest -q suma_de_los_primeros_numeros_naturales.py
#    1 passed in 0.16s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('suma3(20000)')
#    0.04 segundos
#    >>> tiempo('suma1(20000)')
#    0.00 segundos
#    >>> tiempo('suma2(20000)')
#    0.00 segundos
#    >>> tiempo('suma3(20000)')
#    0.02 segundos
#    >>> tiempo('suma4(20000)')
#    0.00 segundos
#    >>> tiempo('suma5(20000)')
#    0.01 segundos
#    >>> tiempo('suma6(20000)')
#    0.00 segundos
#
#    >>> tiempo('suma1(10**8)')
#    1.55 segundos
#    >>> tiempo('suma2(10**8)')
#    0.00 segundos
#    >>> tiempo('suma4(10**8)')
#    3.69 segundos
#    >>> tiempo('suma5(10**8)')
#    7.04 segundos
#    >>> tiempo('suma6(10**8)')
#    4.23 segundos

100

101

102

103

from operator import add

from functools import reduce

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

setrecursionlimit(10**8)

# 1ª solución

# ===========

def suma1(n: int) -> int:

return sum(range(1, n + 1))

# 2ª solución

# ===========

def suma2(n: int) -> int:

return (1 + n) * n // 2

# 3ª solución

# ===========

def suma3(n: int) -> int:

if n == 1:

return 1

return n + suma3(n - 1)

# 4ª solución

# ===========

def suma4(n: int) -> int:

return reduce(add, range(1, n + 1))

# 5ª solución

# ===========

def suma5(n: int) -> int:

x, r = 1, 0

while x <= n:

r = r + x

x = x + 1

return r

# 6ª solución

# ===========

def suma6(n: int) -> int:

r = 0

for x in range(1, n + 1):

r = r + x

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=1, max_value=1000))

def test_suma(n):

r = suma1(n)

assert suma2(n) == r

assert suma3(n) == r

assert suma4(n) == r

assert suma5(n) == r

assert suma6(n) == r

# La comprobación es

# src> poetry run pytest -q suma_de_los_primeros_numeros_naturales.py

# 1 passed in 0.16s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('suma3(20000)')

# 0.04 segundos

# >>> tiempo('suma1(20000)')

# 0.00 segundos

# >>> tiempo('suma2(20000)')

# 0.00 segundos

# >>> tiempo('suma3(20000)')

# 0.02 segundos

# >>> tiempo('suma4(20000)')

# 0.00 segundos

# >>> tiempo('suma5(20000)')

# 0.01 segundos

# >>> tiempo('suma6(20000)')

# 0.00 segundos

# >>> tiempo('suma1(10**8)')

# 1.55 segundos

# >>> tiempo('suma2(10**8)')

# 0.00 segundos

# >>> tiempo('suma4(10**8)')

# 3.69 segundos

# >>> tiempo('suma5(10**8)')

# 7.04 segundos

# >>> tiempo('suma6(10**8)')

# 4.23 segundos

El código se encuentra en GitHub

Números libres de cuadrados

PorJosé A. Alonso 26-septiembre-202214-diciembre-2022

Un número es libre de cuadrados si no es divisible por el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

   libreDeCuadrados :: Integer -> Bool

1	libreDeCuadrados :: Integer -> Bool

tal que libreDeCuadrados x se verifica si x es libre de cuadrados. Por ejemplo,

   libreDeCuadrados 70  ==  True
   libreDeCuadrados 40  ==  False
   libreDeCuadrados (product (take 30000 primes))  ==  True

libreDeCuadrados 70 == True

libreDeCuadrados 40 == False

libreDeCuadrados (product (take 30000 primes)) == True

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (nub)
import Data.Numbers.Primes (primeFactors, primes)
import Test.QuickCheck

-- 1ª solución
-- ===========

libreDeCuadrados1 :: Integer -> Bool
libreDeCuadrados1 n =
  null [x | x <- [2..n], rem n (x^2) == 0]

-- 2ª solución
-- ===========

libreDeCuadrados2 :: Integer -> Bool
libreDeCuadrados2 x =
  x == product (divisoresPrimos2 x)

-- (divisoresPrimos x) es la lista de los divisores primos de x. Por
-- ejemplo,
--    divisoresPrimos 40 == [2,5]
--    divisoresPrimos 70 == [2,5,7]
divisoresPrimos2 :: Integer -> [Integer]
divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,
--    divisores 25  ==  [1,5,25]
--    divisores 30  ==  [1,2,3,5,6,10,15,30]
divisores2 :: Integer -> [Integer]
divisores2 n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,
--    primo 30  == False
--    primo 31  == True
primo2 :: Integer -> Bool
primo2 n = divisores2 n == [1, n]

-- 3ª solución
-- ===========

libreDeCuadrados3 :: Integer -> Bool
libreDeCuadrados3 n
  | even n = n `mod` 4 /= 0 && libreDeCuadrados3 (n `div` 2)
  | otherwise = aux n [3,5..n]
  where aux 1 _  = True
        aux _ [] = True
        aux m (x:xs)
          | m `mod` x == 0 = m `mod` (x^2) /= 0 && aux (m `div` x) xs
          | otherwise      = aux m xs

-- 4ª solución
-- ===========

libreDeCuadrados4 :: Integer -> Bool
libreDeCuadrados4 x =
  x == product (divisoresPrimos4 x)

divisoresPrimos4 :: Integer -> [Integer]
divisoresPrimos4 = nub . primeFactors

-- 5ª solución
-- ===========

libreDeCuadrados5 :: Integer -> Bool
libreDeCuadrados5 =
  sinRepetidos . primeFactors

-- (sinRepetidos xs) se verifica si xs no tiene elementos repetidos. Por
-- ejemplo,
--    sinRepetidos [3,2,5]  ==  True
--    sinRepetidos [3,2,5,2]  ==  False
sinRepetidos :: [Integer] -> Bool
sinRepetidos xs =
  nub xs == xs

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_libreDeCuadrados :: Integer -> Property
prop_libreDeCuadrados x =
  x > 1 ==>
  all (== libreDeCuadrados1 x)
      [libreDeCuadrados2 x,
       libreDeCuadrados3 x,
       libreDeCuadrados4 x,
       libreDeCuadrados5 x]

-- La comprobación es
--    λ> quickCheck prop_libreDeCuadrados
--    +++ OK, passed 100 tests; 165 discarded.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> libreDeCuadrados1 9699690
--    True
--    (8.54 secs, 6,441,144,248 bytes)
--    λ> libreDeCuadrados2 9699690
--    True
--    (4.78 secs, 1,940,781,632 bytes)
--    λ> libreDeCuadrados3 9699690
--    True
--    (0.01 secs, 561,400 bytes)
--    λ> libreDeCuadrados4 9699690
--    True
--    (0.01 secs, 568,160 bytes)
--    λ> libreDeCuadrados5 9699690
--    True
--    (0.01 secs, 567,536 bytes)
--
--    λ> libreDeCuadrados3 (product (take 30000 primes))
--    True
--    (2.30 secs, 2,369,316,208 bytes)
--    λ> libreDeCuadrados4 (product (take 30000 primes))
--    True
--    (6.68 secs, 4,565,617,408 bytes)
--    λ> libreDeCuadrados5 (product (take 30000 primes))
--    True
--    (5.54 secs, 3,411,701,752 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

import Data.List (nub)

import Data.Numbers.Primes (primeFactors, primes)

import Test.QuickCheck

-- 1ª solución

-- ===========

libreDeCuadrados1 :: Integer -> Bool

libreDeCuadrados1 n =

null [x | x <- [2..n], rem n (x^2) == 0]

-- 2ª solución

-- ===========

libreDeCuadrados2 :: Integer -> Bool

libreDeCuadrados2 x =

x == product (divisoresPrimos2 x)

-- (divisoresPrimos x) es la lista de los divisores primos de x. Por

-- ejemplo,

-- divisoresPrimos 40 == [2,5]

-- divisoresPrimos 70 == [2,5,7]

divisoresPrimos2 :: Integer -> [Integer]

divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,

-- divisores 25 == [1,5,25]

-- divisores 30 == [1,2,3,5,6,10,15,30]

divisores2 :: Integer -> [Integer]

divisores2 n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,

-- primo 30 == False

-- primo 31 == True

primo2 :: Integer -> Bool

primo2 n = divisores2 n == [1, n]

-- 3ª solución

-- ===========

libreDeCuadrados3 :: Integer -> Bool

libreDeCuadrados3 n

| even n = n `mod` 4 /= 0 && libreDeCuadrados3 (n `div` 2)

| otherwise = aux n [3,5..n]

where aux 1 _ = True

aux _ [] = True

aux m (x:xs)

| m `mod` x == 0 = m `mod` (x^2) /= 0 && aux (m `div` x) xs

| otherwise = aux m xs

-- 4ª solución

-- ===========

libreDeCuadrados4 :: Integer -> Bool

libreDeCuadrados4 x =

x == product (divisoresPrimos4 x)

divisoresPrimos4 :: Integer -> [Integer]

divisoresPrimos4 = nub . primeFactors

-- 5ª solución

-- ===========

libreDeCuadrados5 :: Integer -> Bool

libreDeCuadrados5 =

sinRepetidos . primeFactors

-- (sinRepetidos xs) se verifica si xs no tiene elementos repetidos. Por

-- ejemplo,

-- sinRepetidos [3,2,5] == True

-- sinRepetidos [3,2,5,2] == False

sinRepetidos :: [Integer] -> Bool

sinRepetidos xs =

nub xs == xs

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_libreDeCuadrados :: Integer -> Property

prop_libreDeCuadrados x =

x > 1 ==>

all (== libreDeCuadrados1 x)

[libreDeCuadrados2 x,

libreDeCuadrados3 x,

libreDeCuadrados4 x,

libreDeCuadrados5 x]

-- La comprobación es

-- λ> quickCheck prop_libreDeCuadrados

-- +++ OK, passed 100 tests; 165 discarded.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> libreDeCuadrados1 9699690

-- True

-- (8.54 secs, 6,441,144,248 bytes)

-- λ> libreDeCuadrados2 9699690

-- True

-- (4.78 secs, 1,940,781,632 bytes)

-- λ> libreDeCuadrados3 9699690

-- True

-- (0.01 secs, 561,400 bytes)

-- λ> libreDeCuadrados4 9699690

-- True

-- (0.01 secs, 568,160 bytes)

-- λ> libreDeCuadrados5 9699690

-- True

-- (0.01 secs, 567,536 bytes)

-- λ> libreDeCuadrados3 (product (take 30000 primes))

-- True

-- (2.30 secs, 2,369,316,208 bytes)

-- λ> libreDeCuadrados4 (product (take 30000 primes))

-- True

-- (6.68 secs, 4,565,617,408 bytes)

-- λ> libreDeCuadrados5 (product (take 30000 primes))

-- True

-- (5.54 secs, 3,411,701,752 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from timeit import Timer, default_timer
from sys import setrecursionlimit
from sympy import primefactors, primerange
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución
# ===========

def libreDeCuadrados1(n: int) -> bool:
    return [x for x in range(2, n + 2) if n % (x**2) == 0] == []

# 2ª solución
# ===========

# divisores(n) es la lista de los divisores del número n. Por ejemplo,
#    divisores(30)  ==  [1,2,3,5,6,10,15,30]
def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]

# primo(n) se verifica si n es primo. Por ejemplo,
#    primo(30)  == False
#    primo(31)  == True
def primo1(n: int) -> bool:
    return divisores1(n) == [1, n]

# divisoresPrimos(x) es la lista de los divisores primos de x. Por
# ejemplo,
#    divisoresPrimos(40) == [2, 5]
#    divisoresPrimos(70) == [2, 5, 7]
def divisoresPrimos1(x: int) -> list[int]:
    return [n for n in divisores1(x) if primo1(n)]

# producto(xs) es el producto de los elementos de xs. Por ejemplo,
#    producto([3, 2, 5])  ==  30
def producto(xs):
    if xs:
        return xs[0] * producto(xs[1:])
    return 1

def libreDeCuadrados2(x):
    return x == producto(divisoresPrimos1(x))

# 3ª solución
# ===========

def libreDeCuadrados3(n: int) -> bool:
    if n % 2 == 0:
        return n % 4 != 0 and libreDeCuadrados3(n // 2)

    def aux(m, xs):
        if m == 1:
            return True
        if xs == []:
            return True
        if m % xs[0] == 0:
            return m % (xs[0]**2) != 0 and aux(m // xs[0], xs[1:])
        return aux(m, xs[1:])
    return aux(n, range(3, n + 1, 2))

# 4ª solución
# ===========

def libreDeCuadrados4(x):
    return x == producto(primefactors(x))

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_libreDeCuadrados(n):
    assert libreDeCuadrados1(n) ==\
           libreDeCuadrados2(n) ==\
           libreDeCuadrados3(n) ==\
           libreDeCuadrados4(n)

# La comprobación es
#    src> poetry run pytest -q numeros_libres_de_cuadrados.py
#    1 passed in 0.59s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('libreDeCuadrados1(9699690)')
#    2.66 segundos
#    >>> tiempo('libreDeCuadrados2(9699690)')
#    2.58 segundos
#    >>> tiempo('libreDeCuadrados3(9699690)')
#    0.00 segundos
#    >>> tiempo('libreDeCuadrados4(9699690)')
#    0.00 segundos
#
#    >>> n = producto(list(primerange(1, 25000)))
#    >>> tiempo('libreDeCuadrados3(n)')
#    0.42 segundos
#    >>> tiempo('libreDeCuadrados4(n)')
#    0.14 segundos

100

101

102

103

104

105

from timeit import Timer, default_timer

from sys import setrecursionlimit

from sympy import primefactors, primerange

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

def libreDeCuadrados1(n: int) -> bool:

return [x for x in range(2, n + 2) if n % (x**2) == 0] == []

# 2ª solución

# ===========

# divisores(n) es la lista de los divisores del número n. Por ejemplo,

# divisores(30) == [1,2,3,5,6,10,15,30]

def divisores1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if n % x == 0]

# primo(n) se verifica si n es primo. Por ejemplo,

# primo(30) == False

# primo(31) == True

def primo1(n: int) -> bool:

return divisores1(n) == [1, n]

# divisoresPrimos(x) es la lista de los divisores primos de x. Por

# ejemplo,

# divisoresPrimos(40) == [2, 5]

# divisoresPrimos(70) == [2, 5, 7]

def divisoresPrimos1(x: int) -> list[int]:

return [n for n in divisores1(x) if primo1(n)]

# producto(xs) es el producto de los elementos de xs. Por ejemplo,

# producto([3, 2, 5]) == 30

def producto(xs):

if xs:

return xs[0] * producto(xs[1:])

return 1

def libreDeCuadrados2(x):

return x == producto(divisoresPrimos1(x))

# 3ª solución

# ===========

def libreDeCuadrados3(n: int) -> bool:

if n % 2 == 0:

return n % 4 != 0 and libreDeCuadrados3(n // 2)

def aux(m, xs):

if m == 1:

return True

if xs == []:

return True

if m % xs[0] == 0:

return m % (xs[0]**2) != 0 and aux(m // xs[0], xs[1:])

return aux(m, xs[1:])

return aux(n, range(3, n + 1, 2))

# 4ª solución

# ===========

def libreDeCuadrados4(x):

return x == producto(primefactors(x))

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_libreDeCuadrados(n):

assert libreDeCuadrados1(n) ==\

libreDeCuadrados2(n) ==\

libreDeCuadrados3(n) ==\

libreDeCuadrados4(n)

# La comprobación es

# src> poetry run pytest -q numeros_libres_de_cuadrados.py

# 1 passed in 0.59s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('libreDeCuadrados1(9699690)')

# 2.66 segundos

# >>> tiempo('libreDeCuadrados2(9699690)')

# 2.58 segundos

# >>> tiempo('libreDeCuadrados3(9699690)')

# 0.00 segundos

# >>> tiempo('libreDeCuadrados4(9699690)')

# 0.00 segundos

# >>> n = producto(list(primerange(1, 25000)))

# >>> tiempo('libreDeCuadrados3(n)')

# 0.42 segundos

# >>> tiempo('libreDeCuadrados4(n)')

# 0.14 segundos

El código se encuentra en GitHub.

Divisores primos

PorJosé A. Alonso 23-septiembre-202214-diciembre-2022

Definir la función

   divisoresPrimos :: Integer -> [Integer]

1	divisoresPrimos :: Integer -> [Integer]

tal que divisoresPrimos x es la lista de los divisores primos de x. Por ejemplo,

   divisoresPrimos 40 == [2,5]
   divisoresPrimos 70 == [2,5,7]
   length (divisoresPrimos (product [1..20000])) == 2262

divisoresPrimos 40 == [2,5]

divisoresPrimos 70 == [2,5,7]

length (divisoresPrimos (product [1..20000])) == 2262

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (nub)
import Data.Set (toList)
import Data.Numbers.Primes (isPrime, primeFactors)
import Math.NumberTheory.ArithmeticFunctions (divisors)
import Test.QuickCheck

-- 1ª solución
-- ===========

divisoresPrimos1 :: Integer -> [Integer]
divisoresPrimos1 x = [n | n <- divisores1 x, primo1 n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,
--    divisores 25  ==  [1,5,25]
--    divisores 30  ==  [1,2,3,5,6,10,15,30]
divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,
--    primo 30  == False
--    primo 31  == True
primo1 :: Integer -> Bool
primo1 n = divisores1 n == [1, n]

-- 2ª solución
-- ===========

divisoresPrimos2 :: Integer -> [Integer]
divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]

divisores2 :: Integer -> [Integer]
divisores2 n = xs ++ [n `div` y | y <- ys]
  where xs = primerosDivisores2 n
        (z:zs) = reverse xs
        ys | z^2 == n  = zs
           | otherwise = z:zs

-- (primerosDivisores n) es la lista de los divisores del número n cuyo
-- cuadrado es menor o gual que n. Por ejemplo,
--    primerosDivisores 25  ==  [1,5]
--    primerosDivisores 30  ==  [1,2,3,5]
primerosDivisores2 :: Integer -> [Integer]
primerosDivisores2 n =
   [x | x <- [1..round (sqrt (fromIntegral n))],
        n `mod` x == 0]

primo2 :: Integer -> Bool
primo2 1 = False
primo2 n = primerosDivisores2 n == [1]

-- 3ª solución
-- ===========

divisoresPrimos3 :: Integer -> [Integer]
divisoresPrimos3 x = [n | n <- divisores3 x, primo3 n]

divisores3 :: Integer -> [Integer]
divisores3 n = xs ++ [n `div` y | y <- ys]
  where xs = primerosDivisores3 n
        (z:zs) = reverse xs
        ys | z^2 == n  = zs
           | otherwise = z:zs

primerosDivisores3 :: Integer -> [Integer]
primerosDivisores3 n =
   filter ((== 0) . mod n) [1..round (sqrt (fromIntegral n))]

primo3 :: Integer -> Bool
primo3 1 = False
primo3 n = primerosDivisores3 n == [1]

-- 4ª solución
-- ===========

divisoresPrimos4 :: Integer -> [Integer]
divisoresPrimos4 n
  | even n = 2 : divisoresPrimos4 (reducido n 2)
  | otherwise = aux n [3,5..n]
  where aux 1 _  = []
        aux _ [] = []
        aux m (x:xs) | m `mod` x == 0 = x : aux (reducido m x) xs
                     | otherwise      = aux m xs

-- (reducido m x) es el resultado de dividir repetidamente m por x,
-- mientras sea divisible. Por ejemplo,
--    reducido 36 2  ==  9
reducido :: Integer -> Integer -> Integer
reducido m x | m `mod` x == 0 = reducido (m `div` x) x
             | otherwise      = m

-- 5ª solución
-- ===========

divisoresPrimos5 :: Integer -> [Integer]
divisoresPrimos5 = nub . primeFactors

-- 6ª solución
-- ===========

divisoresPrimos6 :: Integer -> [Integer]
divisoresPrimos6 = filter isPrime . toList . divisors

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_divisoresPrimos :: Integer -> Property
prop_divisoresPrimos n =
  n > 1 ==>
  all (== divisoresPrimos1 n)
      [divisoresPrimos2 n,
       divisoresPrimos3 n,
       divisoresPrimos4 n,
       divisoresPrimos5 n,
       divisoresPrimos6 n]

-- La comprobación es
--    λ> quickCheck prop_divisoresPrimos
--    +++ OK, passed 100 tests; 108 discarded.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> divisoresPrimos1 (product [1..11])
--    [2,3,5,7,11]
--    (18.34 secs, 7,984,382,104 bytes)
--    λ> divisoresPrimos2 (product [1..11])
--    [2,3,5,7,11]
--    (0.02 secs, 2,610,976 bytes)
--    λ> divisoresPrimos3 (product [1..11])
--    [2,3,5,7,11]
--    (0.02 secs, 2,078,288 bytes)
--    λ> divisoresPrimos4 (product [1..11])
--    [2,3,5,7,11]
--    (0.02 secs, 565,992 bytes)
--    λ> divisoresPrimos5 (product [1..11])
--    [2,3,5,7,11]
--    (0.01 secs, 568,000 bytes)
--    λ> divisoresPrimos6 (product [1..11])
--    [2,3,5,7,11]
--    (0.00 secs, 2,343,392 bytes)
--
--    λ> divisoresPrimos2 (product [1..16])
--    [2,3,5,7,11,13]
--    (2.32 secs, 923,142,480 bytes)
--    λ> divisoresPrimos3 (product [1..16])
--    [2,3,5,7,11,13]
--    (0.80 secs, 556,961,088 bytes)
--    λ> divisoresPrimos4 (product [1..16])
--    [2,3,5,7,11,13]
--    (0.01 secs, 572,368 bytes)
--    λ> divisoresPrimos5 (product [1..16])
--    [2,3,5,7,11,13]
--    (0.01 secs, 31,665,896 bytes)
--    λ> divisoresPrimos6 (product [1..16])
--    [2,3,5,7,11,13]
--    (0.01 secs, 18,580,584 bytes)
--
--    λ> length (divisoresPrimos4 (product [1..30]))
--    10
--    (0.01 secs, 579,168 bytes)
--    λ> length (divisoresPrimos5 (product [1..30]))
--    10
--    (0.01 secs, 594,976 bytes)
--    λ> length (divisoresPrimos6 (product [1..30]))
--    10
--    (3.38 secs, 8,068,783,408 bytes)
--
--    λ> length (divisoresPrimos4 (product [1..20000]))
--    2262
--    (1.20 secs, 1,940,069,976 bytes)
--    λ> length (divisoresPrimos5 (product [1..20000]))
--    2262
--    (1.12 secs, 1,955,921,736 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

import Data.List (nub)

import Data.Set (toList)

import Data.Numbers.Primes (isPrime, primeFactors)

import Math.NumberTheory.ArithmeticFunctions (divisors)

import Test.QuickCheck

-- 1ª solución

-- ===========

divisoresPrimos1 :: Integer -> [Integer]

divisoresPrimos1 x = [n | n <- divisores1 x, primo1 n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,

-- divisores 25 == [1,5,25]

-- divisores 30 == [1,2,3,5,6,10,15,30]

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,

-- primo 30 == False

-- primo 31 == True

primo1 :: Integer -> Bool

primo1 n = divisores1 n == [1, n]

-- 2ª solución

-- ===========

divisoresPrimos2 :: Integer -> [Integer]

divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]

divisores2 :: Integer -> [Integer]

divisores2 n = xs ++ [n `div` y | y <- ys]

where xs = primerosDivisores2 n

(z:zs) = reverse xs

ys | z^2 == n = zs

| otherwise = z:zs

-- (primerosDivisores n) es la lista de los divisores del número n cuyo

-- cuadrado es menor o gual que n. Por ejemplo,

-- primerosDivisores 25 == [1,5]

-- primerosDivisores 30 == [1,2,3,5]

primerosDivisores2 :: Integer -> [Integer]

primerosDivisores2 n =

[x | x <- [1..round (sqrt (fromIntegral n))],

n `mod` x == 0]

primo2 :: Integer -> Bool

primo2 1 = False

primo2 n = primerosDivisores2 n == [1]

-- 3ª solución

-- ===========

divisoresPrimos3 :: Integer -> [Integer]

divisoresPrimos3 x = [n | n <- divisores3 x, primo3 n]

divisores3 :: Integer -> [Integer]

divisores3 n = xs ++ [n `div` y | y <- ys]

where xs = primerosDivisores3 n

(z:zs) = reverse xs

ys | z^2 == n = zs

| otherwise = z:zs

primerosDivisores3 :: Integer -> [Integer]

primerosDivisores3 n =

filter ((== 0) . mod n) [1..round (sqrt (fromIntegral n))]

primo3 :: Integer -> Bool

primo3 1 = False

primo3 n = primerosDivisores3 n == [1]

-- 4ª solución

-- ===========

divisoresPrimos4 :: Integer -> [Integer]

divisoresPrimos4 n

| even n = 2 : divisoresPrimos4 (reducido n 2)

| otherwise = aux n [3,5..n]

where aux 1 _ = []

aux _ [] = []

aux m (x:xs) | m `mod` x == 0 = x : aux (reducido m x) xs

| otherwise = aux m xs

-- (reducido m x) es el resultado de dividir repetidamente m por x,

-- mientras sea divisible. Por ejemplo,

-- reducido 36 2 == 9

reducido :: Integer -> Integer -> Integer

reducido m x | m `mod` x == 0 = reducido (m `div` x) x

| otherwise = m

-- 5ª solución

-- ===========

divisoresPrimos5 :: Integer -> [Integer]

divisoresPrimos5 = nub . primeFactors

-- 6ª solución

-- ===========

divisoresPrimos6 :: Integer -> [Integer]

divisoresPrimos6 = filter isPrime . toList . divisors

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_divisoresPrimos :: Integer -> Property

prop_divisoresPrimos n =

n > 1 ==>

all (== divisoresPrimos1 n)

[divisoresPrimos2 n,

divisoresPrimos3 n,

divisoresPrimos4 n,

divisoresPrimos5 n,

divisoresPrimos6 n]

-- La comprobación es

-- λ> quickCheck prop_divisoresPrimos

-- +++ OK, passed 100 tests; 108 discarded.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> divisoresPrimos1 (product [1..11])

-- [2,3,5,7,11]

-- (18.34 secs, 7,984,382,104 bytes)

-- λ> divisoresPrimos2 (product [1..11])

-- [2,3,5,7,11]

-- (0.02 secs, 2,610,976 bytes)

-- λ> divisoresPrimos3 (product [1..11])

-- [2,3,5,7,11]

-- (0.02 secs, 2,078,288 bytes)

-- λ> divisoresPrimos4 (product [1..11])

-- [2,3,5,7,11]

-- (0.02 secs, 565,992 bytes)

-- λ> divisoresPrimos5 (product [1..11])

-- [2,3,5,7,11]

-- (0.01 secs, 568,000 bytes)

-- λ> divisoresPrimos6 (product [1..11])

-- [2,3,5,7,11]

-- (0.00 secs, 2,343,392 bytes)

-- λ> divisoresPrimos2 (product [1..16])

-- [2,3,5,7,11,13]

-- (2.32 secs, 923,142,480 bytes)

-- λ> divisoresPrimos3 (product [1..16])

-- [2,3,5,7,11,13]

-- (0.80 secs, 556,961,088 bytes)

-- λ> divisoresPrimos4 (product [1..16])

-- [2,3,5,7,11,13]

-- (0.01 secs, 572,368 bytes)

-- λ> divisoresPrimos5 (product [1..16])

-- [2,3,5,7,11,13]

-- (0.01 secs, 31,665,896 bytes)

-- λ> divisoresPrimos6 (product [1..16])

-- [2,3,5,7,11,13]

-- (0.01 secs, 18,580,584 bytes)

-- λ> length (divisoresPrimos4 (product [1..30]))

-- 10

-- (0.01 secs, 579,168 bytes)

-- λ> length (divisoresPrimos5 (product [1..30]))

-- 10

-- (0.01 secs, 594,976 bytes)

-- λ> length (divisoresPrimos6 (product [1..30]))

-- 10

-- (3.38 secs, 8,068,783,408 bytes)

-- λ> length (divisoresPrimos4 (product [1..20000]))

-- 2262

-- (1.20 secs, 1,940,069,976 bytes)

-- λ> length (divisoresPrimos5 (product [1..20000]))

-- 2262

-- (1.12 secs, 1,955,921,736 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import sqrt
from operator import mul
from functools import reduce
from timeit import Timer, default_timer
from sys import setrecursionlimit
from sympy import divisors, isprime, primefactors
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución
# ===========

# divisores(n) es la lista de los divisores del número n. Por ejemplo,
#    divisores(30)  ==  [1,2,3,5,6,10,15,30]
def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]

# primo(n) se verifica si n es primo. Por ejemplo,
#    primo(30)  == False
#    primo(31)  == True
def primo1(n: int) -> bool:
    return divisores1(n) == [1, n]

def divisoresPrimos1(x: int) -> list[int]:
    return [n for n in divisores1(x) if primo1(n)]

# 2ª solución
# ===========

# primerosDivisores(n) es la lista de los divisores del número n cuyo
# cuadrado es menor o gual que n. Por ejemplo,
#    primerosDivisores(25)  ==  [1,5]
#    primerosDivisores(30)  ==  [1,2,3,5]
def primerosDivisores2(n: int) -> list[int]:
    return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0]

def divisores2(n: int) -> list[int]:
    xs = primerosDivisores2(n)
    zs = list(reversed(xs))
    if zs[0]**2 == n:
        return xs + [n // a for a in zs[1:]]
    return xs + [n // a for a in zs]

def primo2(n: int) -> bool:
    return divisores2(n) == [1, n]

def divisoresPrimos2(x: int) -> list[int]:
    return [n for n in divisores2(x) if primo2(n)]

# 3ª solución
# ===========

# reducido(m, x) es el resultado de dividir repetidamente m por x,
# mientras sea divisible. Por ejemplo,
#    reducido(36, 2)  ==  9
def reducido(m: int, x: int) -> int:
    if m % x == 0:
        return reducido(m // x, x)
    return m

def divisoresPrimos3(n: int) -> list[int]:
    if n % 2 == 0:
        return [2] + divisoresPrimos3(reducido(n, 2))

    def aux(m, xs):
        if m == 1:
            return []
        if xs == []:
            return []
        if m % xs[0] == 0:
            return [xs[0]] + aux(reducido(m, xs[0]), xs[1:])
        return aux(m, xs[1:])
    return aux(n, range(3, n + 1, 2))

# 4ª solución
# ===========

def divisoresPrimos4(x: int) -> list[int]:
    return [n for n in divisors(x) if isprime(n)]

# 5ª solución
# ===========

def divisoresPrimos5(n):
    return primefactors(n)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_divisoresPrimos(n):
    assert divisoresPrimos1(n) ==\
           divisoresPrimos2(n) ==\
           divisoresPrimos3(n) ==\
           divisoresPrimos4(n) ==\
           divisoresPrimos5(n)

# La comprobación es
#    src> poetry run pytest -q divisores_primos.py
#    1 passed in 0.70s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

def producto(xs: list[int]) -> int:
    return reduce(mul, xs)

# La comparación es
#    >>> tiempo('divisoresPrimos1(producto(list(range(1, 12))))')
#    11.14 segundos
#    >>> tiempo('divisoresPrimos2(producto(list(range(1, 12))))')
#    0.03 segundos
#    >>> tiempo('divisoresPrimos3(producto(list(range(1, 12))))')
#    0.00 segundos
#    >>> tiempo('divisoresPrimos4(producto(list(range(1, 12))))')
#    0.00 segundos
#    >>> tiempo('divisoresPrimos5(producto(list(range(1, 12))))')
#    0.00 segundos
#
#    >>> tiempo('divisoresPrimos2(producto(list(range(1, 17))))')
#    14.21 segundos
#    >>> tiempo('divisoresPrimos3(producto(list(range(1, 17))))')
#    0.00 segundos
#    >>> tiempo('divisoresPrimos4(producto(list(range(1, 17))))')
#    0.01 segundos
#    >>> tiempo('divisoresPrimos5(producto(list(range(1, 17))))')
#    0.00 segundos
#
#    >>> tiempo('divisoresPrimos3(producto(list(range(1, 32))))')
#    0.00 segundos
#    >>> tiempo('divisoresPrimos4(producto(list(range(1, 32))))')
#    4.59 segundos
#    >>> tiempo('divisoresPrimos5(producto(list(range(1, 32))))')
#    0.00 segundos
#
#    >>> tiempo('divisoresPrimos3(producto(list(range(1, 10001))))')
#    3.00 segundos
#    >>> tiempo('divisoresPrimos5(producto(list(range(1, 10001))))')
#    0.24 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

from math import sqrt

from operator import mul

from functools import reduce

from timeit import Timer, default_timer

from sys import setrecursionlimit

from sympy import divisors, isprime, primefactors

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

# divisores(n) es la lista de los divisores del número n. Por ejemplo,

# divisores(30) == [1,2,3,5,6,10,15,30]

def divisores1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if n % x == 0]

# primo(n) se verifica si n es primo. Por ejemplo,

# primo(30) == False

# primo(31) == True

def primo1(n: int) -> bool:

return divisores1(n) == [1, n]

def divisoresPrimos1(x: int) -> list[int]:

return [n for n in divisores1(x) if primo1(n)]

# 2ª solución

# ===========

# primerosDivisores(n) es la lista de los divisores del número n cuyo

# cuadrado es menor o gual que n. Por ejemplo,

# primerosDivisores(25) == [1,5]

# primerosDivisores(30) == [1,2,3,5]

def primerosDivisores2(n: int) -> list[int]:

return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0]

def divisores2(n: int) -> list[int]:

xs = primerosDivisores2(n)

zs = list(reversed(xs))

if zs[0]**2 == n:

return xs + [n // a for a in zs[1:]]

return xs + [n // a for a in zs]

def primo2(n: int) -> bool:

return divisores2(n) == [1, n]

def divisoresPrimos2(x: int) -> list[int]:

return [n for n in divisores2(x) if primo2(n)]

# 3ª solución

# ===========

# reducido(m, x) es el resultado de dividir repetidamente m por x,

# mientras sea divisible. Por ejemplo,

# reducido(36, 2) == 9

def reducido(m: int, x: int) -> int:

if m % x == 0:

return reducido(m // x, x)

return m

def divisoresPrimos3(n: int) -> list[int]:

if n % 2 == 0:

return [2] + divisoresPrimos3(reducido(n, 2))

def aux(m, xs):

if m == 1:

return []

if xs == []:

return []

if m % xs[0] == 0:

return [xs[0]] + aux(reducido(m, xs[0]), xs[1:])

return aux(m, xs[1:])

return aux(n, range(3, n + 1, 2))

# 4ª solución

# ===========

def divisoresPrimos4(x: int) -> list[int]:

return [n for n in divisors(x) if isprime(n)]

# 5ª solución

# ===========

def divisoresPrimos5(n):

return primefactors(n)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_divisoresPrimos(n):

assert divisoresPrimos1(n) ==\

divisoresPrimos2(n) ==\

divisoresPrimos3(n) ==\

divisoresPrimos4(n) ==\

divisoresPrimos5(n)

# La comprobación es

# src> poetry run pytest -q divisores_primos.py

# 1 passed in 0.70s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

def producto(xs: list[int]) -> int:

return reduce(mul, xs)

# La comparación es

# >>> tiempo('divisoresPrimos1(producto(list(range(1, 12))))')

# 11.14 segundos

# >>> tiempo('divisoresPrimos2(producto(list(range(1, 12))))')

# 0.03 segundos

# >>> tiempo('divisoresPrimos3(producto(list(range(1, 12))))')

# 0.00 segundos

# >>> tiempo('divisoresPrimos4(producto(list(range(1, 12))))')

# 0.00 segundos

# >>> tiempo('divisoresPrimos5(producto(list(range(1, 12))))')

# 0.00 segundos

# >>> tiempo('divisoresPrimos2(producto(list(range(1, 17))))')

# 14.21 segundos

# >>> tiempo('divisoresPrimos3(producto(list(range(1, 17))))')

# 0.00 segundos

# >>> tiempo('divisoresPrimos4(producto(list(range(1, 17))))')

# 0.01 segundos

# >>> tiempo('divisoresPrimos5(producto(list(range(1, 17))))')

# 0.00 segundos

# >>> tiempo('divisoresPrimos3(producto(list(range(1, 32))))')

# 0.00 segundos

# >>> tiempo('divisoresPrimos4(producto(list(range(1, 32))))')

# 4.59 segundos

# >>> tiempo('divisoresPrimos5(producto(list(range(1, 32))))')

# 0.00 segundos

# >>> tiempo('divisoresPrimos3(producto(list(range(1, 10001))))')

# 3.00 segundos

# >>> tiempo('divisoresPrimos5(producto(list(range(1, 10001))))')

# 0.24 segundos

El código se encuentra en GitHub.

Divisores de un número

PorJosé A. Alonso 22-septiembre-202214-diciembre-2022

Definir la función

   divisores :: Integer -> [Integer]

1	divisores :: Integer -> [Integer]

tal que divisores n es la lista de los divisores de n. Por ejemplo,

  divisores 30  ==  [1,2,3,5,6,10,15,30]
  length (divisores (product [1..10]))  ==  270
  length (divisores (product [1..25]))  ==  340032

divisores 30 == [1,2,3,5,6,10,15,30]

length (divisores (product [1..10])) == 270

length (divisores (product [1..25])) == 340032

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (group, inits, nub, sort, subsequences)
import Data.Numbers.Primes (primeFactors)
import Data.Set (toList)
import Math.NumberTheory.ArithmeticFunctions (divisors)
import Test.QuickCheck

-- 1ª solución
-- ===========

divisores1 :: Integer -> [Integer]
divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución
-- ===========

divisores2 :: Integer -> [Integer]
divisores2 n = [x | x <- [1..n], x `esDivisorDe` n]

-- (esDivisorDe x n) se verifica si x es un divisor de n. Por ejemplo,
--    esDivisorDe 2 6  ==  True
--    esDivisorDe 4 6  ==  False
esDivisorDe :: Integer -> Integer -> Bool
esDivisorDe x n = n `rem` x == 0

-- 3ª solución
-- ===========

divisores3 :: Integer -> [Integer]
divisores3 n = filter (`esDivisorDe` n) [1..n]

-- 4ª solución
-- ===========

divisores4 :: Integer -> [Integer]
divisores4 = filter <$> flip esDivisorDe <*> enumFromTo 1

-- 5ª solución
-- ===========

divisores5 :: Integer -> [Integer]
divisores5 n = xs ++ [n `div` y | y <- ys]
  where xs = primerosDivisores1 n
        (z:zs) = reverse xs
        ys | z^2 == n  = zs
           | otherwise = z:zs

-- (primerosDivisores n) es la lista de los divisores del número n cuyo
-- cuadrado es menor o gual que n. Por ejemplo,
--    primerosDivisores 25  ==  [1,5]
--    primerosDivisores 30  ==  [1,2,3,5]
primerosDivisores1 :: Integer -> [Integer]
primerosDivisores1 n =
   [x | x <- [1..round (sqrt (fromIntegral n))],
        x `esDivisorDe` n]

-- 6ª solución
-- ===========

divisores6 :: Integer -> [Integer]
divisores6 n = aux [1..n]
  where aux [] = []
        aux (x:xs) | x `esDivisorDe` n = x : aux xs
                   | otherwise         = aux xs

-- 7ª solución
-- ===========

divisores7 :: Integer -> [Integer]
divisores7 n = xs ++ [n `div` y | y <- ys]
  where xs = primerosDivisores2 n
        (z:zs) = reverse xs
        ys | z^2 == n  = zs
           | otherwise = z:zs

primerosDivisores2 :: Integer -> [Integer]
primerosDivisores2 n = aux [1..round (sqrt (fromIntegral n))]
  where aux [] = []
        aux (x:xs) | x `esDivisorDe` n = x : aux xs
                   | otherwise         = aux xs

-- 8ª solución
-- ===========

divisores8 :: Integer -> [Integer]
divisores8 =
  nub . sort . map product . subsequences . primeFactors

-- 9ª solución
-- ===========

divisores9 :: Integer -> [Integer]
divisores9 = sort
           . map (product . concat)
           . productoCartesiano
           . map inits
           . group
           . primeFactors

-- (productoCartesiano xss) es el producto cartesiano de los conjuntos
-- xss. Por ejemplo,
--    λ> productoCartesiano [[1,3],[2,5],[6,4]]
--    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
productoCartesiano :: [[a]] -> [[a]]
productoCartesiano []       = [[]]
productoCartesiano (xs:xss) =
  [x:ys | x <- xs, ys <- productoCartesiano xss]

-- 10ª solución
-- ============

divisores10 :: Integer -> [Integer]
divisores10 = sort
            . map (product . concat)
            . mapM inits
            . group
            . primeFactors

-- 11ª solución
-- ============

divisores11 :: Integer -> [Integer]
divisores11 = toList . divisors

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_divisores :: Positive Integer -> Bool
prop_divisores (Positive n) =
  all (== divisores1 n)
      [ divisores2 n
      , divisores3 n
      , divisores4 n
      , divisores5 n
      , divisores6 n
      , divisores7 n
      , divisores8 n
      , divisores9 n
      , divisores10 n
      , divisores11 n
      ]

-- La comprobación es
--    λ> quickCheck prop_divisores
--    +++ OK, passed 100 tests.

-- Comparación de la eficiencia
-- ============================

-- La comparación es
--    λ> length (divisores1 (product [1..11]))
--    540
--    (18.55 secs, 7,983,950,592 bytes)
--    λ> length (divisores2 (product [1..11]))
--    540
--    (18.81 secs, 7,983,950,592 bytes)
--    λ> length (divisores3 (product [1..11]))
--    540
--    (12.79 secs, 6,067,935,544 bytes)
--    λ> length (divisores4 (product [1..11]))
--    540
--    (12.51 secs, 6,067,935,592 bytes)
--    λ> length (divisores5 (product [1..11]))
--    540
--    (0.03 secs, 1,890,296 bytes)
--    λ> length (divisores6 (product [1..11]))
--    540
--    (21.46 secs, 9,899,961,392 bytes)
--    λ> length (divisores7 (product [1..11]))
--    540
--    (0.02 secs, 2,195,800 bytes)
--    λ> length (divisores8 (product [1..11]))
--    540
--    (0.09 secs, 107,787,272 bytes)
--    λ> length (divisores9 (product [1..11]))
--    540
--    (0.02 secs, 2,150,472 bytes)
--    λ> length (divisores10 (product [1..11]))
--    540
--    (0.01 secs, 1,652,120 bytes)
--    λ> length (divisores11 (product [1..11]))
--    540
--    (0.01 secs, 796,056 bytes)
--
--    λ> length (divisores5 (product [1..17]))
--    10752
--    (10.16 secs, 3,773,953,128 bytes)
--    λ> length (divisores7 (product [1..17]))
--    10752
--    (9.83 secs, 4,679,260,712 bytes)
--    λ> length (divisores9 (product [1..17]))
--    10752
--    (0.06 secs, 46,953,344 bytes)
--    λ> length (divisores10 (product [1..17]))
--    10752
--    (0.02 secs, 33,633,712 bytes)
--    λ> length (divisores11 (product [1..17]))
--    10752
--    (0.03 secs, 6,129,584 bytes)
--
--    λ> length (divisores10 (product [1..27]))
--    677376
--    (2.14 secs, 3,291,277,736 bytes)
--    λ> length (divisores11 (product [1..27]))
--    677376
--    (0.56 secs, 396,042,280 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

import Data.List (group, inits, nub, sort, subsequences)

import Data.Numbers.Primes (primeFactors)

import Data.Set (toList)

import Math.NumberTheory.ArithmeticFunctions (divisors)

import Test.QuickCheck

-- 1ª solución

-- ===========

divisores1 :: Integer -> [Integer]

divisores1 n = [x | x <- [1..n], n `rem` x == 0]

-- 2ª solución

-- ===========

divisores2 :: Integer -> [Integer]

divisores2 n = [x | x <- [1..n], x `esDivisorDe` n]

-- (esDivisorDe x n) se verifica si x es un divisor de n. Por ejemplo,

-- esDivisorDe 2 6 == True

-- esDivisorDe 4 6 == False

esDivisorDe :: Integer -> Integer -> Bool

esDivisorDe x n = n `rem` x == 0

-- 3ª solución

-- ===========

divisores3 :: Integer -> [Integer]

divisores3 n = filter (`esDivisorDe` n) [1..n]

-- 4ª solución

-- ===========

divisores4 :: Integer -> [Integer]

divisores4 = filter <$> flip esDivisorDe <*> enumFromTo 1

-- 5ª solución

-- ===========

divisores5 :: Integer -> [Integer]

divisores5 n = xs ++ [n `div` y | y <- ys]

where xs = primerosDivisores1 n

(z:zs) = reverse xs

ys | z^2 == n = zs

| otherwise = z:zs

-- (primerosDivisores n) es la lista de los divisores del número n cuyo

-- cuadrado es menor o gual que n. Por ejemplo,

-- primerosDivisores 25 == [1,5]

-- primerosDivisores 30 == [1,2,3,5]

primerosDivisores1 :: Integer -> [Integer]

primerosDivisores1 n =

[x | x <- [1..round (sqrt (fromIntegral n))],

x `esDivisorDe` n]

-- 6ª solución

-- ===========

divisores6 :: Integer -> [Integer]

divisores6 n = aux [1..n]

where aux [] = []

aux (x:xs) | x `esDivisorDe` n = x : aux xs

| otherwise = aux xs

-- 7ª solución

-- ===========

divisores7 :: Integer -> [Integer]

divisores7 n = xs ++ [n `div` y | y <- ys]

where xs = primerosDivisores2 n

(z:zs) = reverse xs

ys | z^2 == n = zs

| otherwise = z:zs

primerosDivisores2 :: Integer -> [Integer]

primerosDivisores2 n = aux [1..round (sqrt (fromIntegral n))]

where aux [] = []

aux (x:xs) | x `esDivisorDe` n = x : aux xs

| otherwise = aux xs

-- 8ª solución

-- ===========

divisores8 :: Integer -> [Integer]

divisores8 =

nub . sort . map product . subsequences . primeFactors

-- 9ª solución

-- ===========

divisores9 :: Integer -> [Integer]

divisores9 = sort

. map (product . concat)

. productoCartesiano

. map inits

. group

. primeFactors

-- (productoCartesiano xss) es el producto cartesiano de los conjuntos

-- xss. Por ejemplo,

-- λ> productoCartesiano [[1,3],[2,5],[6,4]]

-- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]

productoCartesiano :: [[a]] -> [[a]]

productoCartesiano [] = [[]]

productoCartesiano (xs:xss) =

[x:ys | x <- xs, ys <- productoCartesiano xss]

-- 10ª solución

-- ============

divisores10 :: Integer -> [Integer]

divisores10 = sort

. map (product . concat)

. mapM inits

. group

. primeFactors

-- 11ª solución

-- ============

divisores11 :: Integer -> [Integer]

divisores11 = toList . divisors

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_divisores :: Positive Integer -> Bool

prop_divisores (Positive n) =

all (== divisores1 n)

[ divisores2 n

, divisores3 n

, divisores4 n

, divisores5 n

, divisores6 n

, divisores7 n

, divisores8 n

, divisores9 n

, divisores10 n

, divisores11 n

]

-- La comprobación es

-- λ> quickCheck prop_divisores

-- +++ OK, passed 100 tests.

-- Comparación de la eficiencia

-- ============================

-- La comparación es

-- λ> length (divisores1 (product [1..11]))

-- 540

-- (18.55 secs, 7,983,950,592 bytes)

-- λ> length (divisores2 (product [1..11]))

-- 540

-- (18.81 secs, 7,983,950,592 bytes)

-- λ> length (divisores3 (product [1..11]))

-- 540

-- (12.79 secs, 6,067,935,544 bytes)

-- λ> length (divisores4 (product [1..11]))

-- 540

-- (12.51 secs, 6,067,935,592 bytes)

-- λ> length (divisores5 (product [1..11]))

-- 540

-- (0.03 secs, 1,890,296 bytes)

-- λ> length (divisores6 (product [1..11]))

-- 540

-- (21.46 secs, 9,899,961,392 bytes)

-- λ> length (divisores7 (product [1..11]))

-- 540

-- (0.02 secs, 2,195,800 bytes)

-- λ> length (divisores8 (product [1..11]))

-- 540

-- (0.09 secs, 107,787,272 bytes)

-- λ> length (divisores9 (product [1..11]))

-- 540

-- (0.02 secs, 2,150,472 bytes)

-- λ> length (divisores10 (product [1..11]))

-- 540

-- (0.01 secs, 1,652,120 bytes)

-- λ> length (divisores11 (product [1..11]))

-- 540

-- (0.01 secs, 796,056 bytes)

-- λ> length (divisores5 (product [1..17]))

-- 10752

-- (10.16 secs, 3,773,953,128 bytes)

-- λ> length (divisores7 (product [1..17]))

-- 10752

-- (9.83 secs, 4,679,260,712 bytes)

-- λ> length (divisores9 (product [1..17]))

-- 10752

-- (0.06 secs, 46,953,344 bytes)

-- λ> length (divisores10 (product [1..17]))

-- 10752

-- (0.02 secs, 33,633,712 bytes)

-- λ> length (divisores11 (product [1..17]))

-- 10752

-- (0.03 secs, 6,129,584 bytes)

-- λ> length (divisores10 (product [1..27]))

-- 677376

-- (2.14 secs, 3,291,277,736 bytes)

-- λ> length (divisores11 (product [1..27]))

-- 677376

-- (0.56 secs, 396,042,280 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import factorial, sqrt
from timeit import Timer, default_timer
from sys import setrecursionlimit
from sympy import divisors
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución
# ===========

def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]

# 2ª solución
# ===========

# esDivisorDe(x, n) se verifica si x es un divisor de n. Por ejemplo,
#    esDivisorDe(2, 6)  ==  True
#    esDivisorDe(4, 6)  ==  False
def esDivisorDe(x: int, n: int) -> bool:
    return n % x == 0

def divisores2(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if esDivisorDe(x, n)]

# 3ª solución
# ===========

def divisores3(n: int) -> list[int]:
    return list(filter(lambda x: esDivisorDe(x, n), range(1, n + 1)))

# 4ª solución
# ===========

# primerosDivisores(n) es la lista de los divisores del número n cuyo
# cuadrado es menor o gual que n. Por ejemplo,
#    primerosDivisores(25)  ==  [1,5]
#    primerosDivisores(30)  ==  [1,2,3,5]
def primerosDivisores(n: int) -> list[int]:
    return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0]

def divisores4(n: int) -> list[int]:
    xs = primerosDivisores(n)
    zs = list(reversed(xs))
    if zs[0]**2 == n:
        return xs + [n // a for a in zs[1:]]
    return xs + [n // a for a in zs]

# 5ª solución
# ===========

def divisores5(n: int) -> list[int]:
    def aux(xs: list[int]) -> list[int]:
        if xs:
            if esDivisorDe(xs[0], n):
                return [xs[0]] + aux(xs[1:])
            return aux(xs[1:])
        return xs

    return aux(list(range(1, n + 1)))

# 6ª solución
# ============

def divisores6(n: int) -> list[int]:
    xs = []
    for x in range(1, n+1):
        if n % x == 0:
            xs.append(x)
    return xs

# 7ª solución
# ===========

def divisores7(n: int) -> list[int]:
    x = 1
    xs = []
    ys = []
    while x * x < n:
        if n % x == 0:
            xs.append(x)
            ys.append(n // x)
        x = x + 1
    if x * x == n:
        xs.append(x)
    return xs + list(reversed(ys))

# 8ª solución
# ============

def divisores8(n: int) -> list[int]:
    return divisors(n)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_divisores(n):
    assert divisores1(n) ==\
           divisores2(n) ==\
           divisores3(n) ==\
           divisores4(n) ==\
           divisores5(n) ==\
           divisores6(n) ==\
           divisores7(n) ==\
           divisores8(n)

# La comprobación es
#    src> poetry run pytest -q divisores_de_un_numero.py
#    1 passed in 0.84s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('divisores5(4*factorial(7))')
#    1.40 segundos
#
#    >>> tiempo('divisores1(factorial(11))')
#    1.79 segundos
#    >>> tiempo('divisores2(factorial(11))')
#    3.80 segundos
#    >>> tiempo('divisores3(factorial(11))')
#    5.22 segundos
#    >>> tiempo('divisores4(factorial(11))')
#    0.00 segundos
#    >>> tiempo('divisores6(factorial(11))')
#    3.51 segundos
#    >>> tiempo('divisores7(factorial(11))')
#    0.00 segundos
#    >>> tiempo('divisores8(factorial(11))')
#    0.00 segundos
#
#    >>> tiempo('divisores4(factorial(17))')
#    2.23 segundos
#    >>> tiempo('divisores7(factorial(17))')
#    3.22 segundos
#    >>> tiempo('divisores8(factorial(17))')
#    0.00 segundos
#
#    >>> tiempo('divisores8(factorial(27))')
#    0.28 segundos

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

from math import factorial, sqrt

from timeit import Timer, default_timer

from sys import setrecursionlimit

from sympy import divisors

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

# 1ª solución

# ===========

def divisores1(n: int) -> list[int]:

return [x for x in range(1, n + 1) if n % x == 0]

# 2ª solución

# ===========

# esDivisorDe(x, n) se verifica si x es un divisor de n. Por ejemplo,

# esDivisorDe(2, 6) == True

# esDivisorDe(4, 6) == False

def esDivisorDe(x: int, n: int) -> bool:

return n % x == 0

def divisores2(n: int) -> list[int]:

return [x for x in range(1, n + 1) if esDivisorDe(x, n)]

# 3ª solución

# ===========

def divisores3(n: int) -> list[int]:

return list(filter(lambda x: esDivisorDe(x, n), range(1, n + 1)))

# 4ª solución

# ===========

# primerosDivisores(n) es la lista de los divisores del número n cuyo

# cuadrado es menor o gual que n. Por ejemplo,

# primerosDivisores(25) == [1,5]

# primerosDivisores(30) == [1,2,3,5]

def primerosDivisores(n: int) -> list[int]:

return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0]

def divisores4(n: int) -> list[int]:

xs = primerosDivisores(n)

zs = list(reversed(xs))

if zs[0]**2 == n:

return xs + [n // a for a in zs[1:]]

return xs + [n // a for a in zs]

# 5ª solución

# ===========

def divisores5(n: int) -> list[int]:

def aux(xs: list[int]) -> list[int]:

if xs:

if esDivisorDe(xs[0], n):

return [xs[0]] + aux(xs[1:])

return aux(xs[1:])

return xs

return aux(list(range(1, n + 1)))

# 6ª solución

# ============

def divisores6(n: int) -> list[int]:

xs = []

for x in range(1, n+1):

if n % x == 0:

xs.append(x)

return xs

# 7ª solución

# ===========

def divisores7(n: int) -> list[int]:

x = 1

xs = []

ys = []

while x * x < n:

if n % x == 0:

xs.append(x)

ys.append(n // x)

x = x + 1

if x * x == n:

xs.append(x)

return xs + list(reversed(ys))

# 8ª solución

# ============

def divisores8(n: int) -> list[int]:

return divisors(n)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=2, max_value=1000))

def test_divisores(n):

assert divisores1(n) ==\

divisores2(n) ==\

divisores3(n) ==\

divisores4(n) ==\

divisores5(n) ==\

divisores6(n) ==\

divisores7(n) ==\

divisores8(n)

# La comprobación es

# src> poetry run pytest -q divisores_de_un_numero.py

# 1 passed in 0.84s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('divisores5(4*factorial(7))')

# 1.40 segundos

# >>> tiempo('divisores1(factorial(11))')

# 1.79 segundos

# >>> tiempo('divisores2(factorial(11))')

# 3.80 segundos

# >>> tiempo('divisores3(factorial(11))')

# 5.22 segundos

# >>> tiempo('divisores4(factorial(11))')

# 0.00 segundos

# >>> tiempo('divisores6(factorial(11))')

# 3.51 segundos

# >>> tiempo('divisores7(factorial(11))')

# 0.00 segundos

# >>> tiempo('divisores8(factorial(11))')

# 0.00 segundos

# >>> tiempo('divisores4(factorial(17))')

# 2.23 segundos

# >>> tiempo('divisores7(factorial(17))')

# 3.22 segundos

# >>> tiempo('divisores8(factorial(17))')

# 0.00 segundos

# >>> tiempo('divisores8(factorial(27))')

# 0.28 segundos

El código se encuentra en GitHub.

Diferencia conjuntista de listas

PorJosé A. Alonso 22-septiembre-202214-diciembre-2022

Definir la función

   diferencia :: Eq a => [a] -> [a] -> [a]

1	diferencia :: Eq a => [a] -> [a] -> [a]

tal que diferencia xs ys es la diferencia de las listas sin elementos repetidos xs e ys. Por ejemplo,

   diferencia [3,2,5,6] [5,7,3,4]  ==  [2,6]
   diferencia [3,2,5] [5,7,3,2]    ==  []

1 2	diferencia [3,2,5,6] [5,7,3,4] == [2,6] diferencia [3,2,5] [5,7,3,2] == []

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (nub, sort, (\\))
import qualified Data.Set as S (fromList, toList, (\\) )
import Test.QuickCheck

-- 1ª solución
-- ===========

diferencia1 :: Eq a => [a] -> [a] -> [a]
diferencia1 xs ys =
  [x | x <- xs, x `notElem` ys]

-- 2ª solución
-- ===========

diferencia2 :: Ord a => [a] -> [a] -> [a]
diferencia2 [] _ = []
diferencia2 (x:xs) ys
  | x `elem` ys = xs `diferencia2` ys
  | otherwise   = x : xs `diferencia2` ys

-- 3ª solución
-- ===========

diferencia3 :: Ord a => [a] -> [a] -> [a]
diferencia3 = (\\)

-- 4ª solución
-- ===========

diferencia4 :: Ord a => [a] -> [a] -> [a]
diferencia4 xs ys =
  S.toList (S.fromList xs S.\\ S.fromList ys)

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_diferencia :: [Int] -> [Int] -> Bool
prop_diferencia xs ys =
  all (== sort (xs' `diferencia1` ys'))
      [sort (xs' `diferencia2` ys'),
       sort (xs' `diferencia3` ys'),
       xs' `diferencia4` ys']
  where xs' = nub xs
        ys' = nub ys

-- La comprobación es
--    λ> quickCheck prop_diferencia
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (diferencia1 [0..3*10^4] [1,3..3*10^4])
--    15001
--    (3.39 secs, 9,553,528 bytes)
--    λ> length (diferencia2 [0..3*10^4] [1,3..3*10^4])
--    15001
--    (2.98 secs, 9,793,528 bytes)
--    λ> length (diferencia3 [0..3*10^4] [1,3..3*10^4])
--    15001
--    (3.61 secs, 11,622,502,792 bytes)
--    λ> length (diferencia4 [0..3*10^4] [1,3..3*10^4])
--    15001
--    (0.02 secs, 10,092,832 bytes)

import Data.List (nub, sort, (\\))

import qualified Data.Set as S (fromList, toList, (\\) )

import Test.QuickCheck

-- 1ª solución

-- ===========

diferencia1 :: Eq a => [a] -> [a] -> [a]

diferencia1 xs ys =

[x | x <- xs, x `notElem` ys]

-- 2ª solución

-- ===========

diferencia2 :: Ord a => [a] -> [a] -> [a]

diferencia2 [] _ = []

diferencia2 (x:xs) ys

| x `elem` ys = xs `diferencia2` ys

| otherwise = x : xs `diferencia2` ys

-- 3ª solución

-- ===========

diferencia3 :: Ord a => [a] -> [a] -> [a]

diferencia3 = (\\)

-- 4ª solución

-- ===========

diferencia4 :: Ord a => [a] -> [a] -> [a]

diferencia4 xs ys =

S.toList (S.fromList xs S.\\ S.fromList ys)

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_diferencia :: [Int] -> [Int] -> Bool

prop_diferencia xs ys =

all (== sort (xs' `diferencia1` ys'))

[sort (xs' `diferencia2` ys'),

sort (xs' `diferencia3` ys'),

xs' `diferencia4` ys']

where xs' = nub xs

ys' = nub ys

-- La comprobación es

-- λ> quickCheck prop_diferencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (diferencia1 [0..3*10^4] [1,3..3*10^4])

-- 15001

-- (3.39 secs, 9,553,528 bytes)

-- λ> length (diferencia2 [0..3*10^4] [1,3..3*10^4])

-- 15001

-- (2.98 secs, 9,793,528 bytes)

-- λ> length (diferencia3 [0..3*10^4] [1,3..3*10^4])

-- 15001

-- (3.61 secs, 11,622,502,792 bytes)

-- λ> length (diferencia4 [0..3*10^4] [1,3..3*10^4])

-- 15001

-- (0.02 secs, 10,092,832 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from timeit import Timer, default_timer
from sys import setrecursionlimit
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución
# ===========

def diferencia1(xs: list[A], ys: list[A]) -> list[A]:
    return [x for x in xs if x not in ys]

# 2ª solución
# ===========

def diferencia2(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return []
    if xs[0] in ys:
        return diferencia2(xs[1:], ys)
    return [xs[0]] + diferencia2(xs[1:], ys)

# 3ª solución
# ===========

def diferencia3(xs: list[A], ys: list[A]) -> list[A]:
    zs = []
    for x in xs:
        if x not in ys:
            zs.append(x)
    return zs

# 4ª solución
# ===========

def diferencia4(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) - set(ys))

# Comprobación de equivalencia
# ============================
#
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_diferencia(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert sorted(diferencia1(xs1, ys1)) ==\
           sorted(diferencia2(xs1, ys1)) ==\
           sorted(diferencia3(xs1, ys1)) ==\
           sorted(diferencia4(xs1, ys1))

# La comprobación es
#    src> poetry run pytest -q diferencia_conjuntista_de_listas.py
#    1 passed in 0.39s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('diferencia1(list(range(0,20000)), list(range(1,20000,2)))')
#    0.89 segundos
#    >>> tiempo('diferencia2(list(range(0,20000)), list(range(1,20000,2)))')
#    2.11 segundos
#    >>> tiempo('diferencia3(list(range(0,20000)), list(range(1,20000,2)))')
#    1.06 segundos
#    >>> tiempo('diferencia4(list(range(0,20000)), list(range(1,20000,2)))')
#    0.01 segundos

from typing import TypeVar

from timeit import Timer, default_timer

from sys import setrecursionlimit

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

# ===========

def diferencia1(xs: list[A], ys: list[A]) -> list[A]:

return [x for x in xs if x not in ys]

# 2ª solución

# ===========

def diferencia2(xs: list[A], ys: list[A]) -> list[A]:

if not xs:

return []

if xs[0] in ys:

return diferencia2(xs[1:], ys)

return [xs[0]] + diferencia2(xs[1:], ys)

# 3ª solución

# ===========

def diferencia3(xs: list[A], ys: list[A]) -> list[A]:

zs = []

for x in xs:

if x not in ys:

zs.append(x)

return zs

# 4ª solución

# ===========

def diferencia4(xs: list[A], ys: list[A]) -> list[A]:

return list(set(xs) - set(ys))

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_diferencia(xs, ys):

xs1 = list(set(xs))

ys1 = list(set(ys))

assert sorted(diferencia1(xs1, ys1)) ==\

sorted(diferencia2(xs1, ys1)) ==\

sorted(diferencia3(xs1, ys1)) ==\

sorted(diferencia4(xs1, ys1))

# La comprobación es

# src> poetry run pytest -q diferencia_conjuntista_de_listas.py

# 1 passed in 0.39s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('diferencia1(list(range(0,20000)), list(range(1,20000,2)))')

# 0.89 segundos

# >>> tiempo('diferencia2(list(range(0,20000)), list(range(1,20000,2)))')

# 2.11 segundos

# >>> tiempo('diferencia3(list(range(0,20000)), list(range(1,20000,2)))')

# 1.06 segundos

# >>> tiempo('diferencia4(list(range(0,20000)), list(range(1,20000,2)))')

# 0.01 segundos

El código se encuentra en GitHub.

Intersección conjuntista de listas

PorJosé A. Alonso 21-septiembre-20222-septiembre-2022

Definir la función

   interseccion :: Eq a => [a] -> [a] -> [a]

1	interseccion :: Eq a => [a] -> [a] -> [a]

tal que interseccion xs ys es la intersección de las listas sin elementos repetidos xs e ys. Por ejemplo,

   interseccion [3,2,5] [5,7,3,4]  ==  [3,5]
   interseccion [3,2,5] [9,7,6,4]  ==  []

1 2	interseccion [3,2,5] [5,7,3,4] == [3,5] interseccion [3,2,5] [9,7,6,4] == []

Soluciones en Haskell

import Data.List (nub, sort, intersect)
import qualified Data.Set as S (fromList, toList, intersection )
import Test.QuickCheck

-- 1ª solución
-- ===========

interseccion1 :: Eq a => [a] -> [a] -> [a]
interseccion1 xs ys =
  [x | x <- xs, x `elem` ys]

-- 2ª solución
-- ===========

interseccion2 :: Ord a => [a] -> [a] -> [a]
interseccion2 [] _ = []
interseccion2 (x:xs) ys
  | x `elem` ys = x : xs `interseccion2` ys
  | otherwise   = xs `interseccion2` ys

-- 3ª solución
-- ===========

interseccion3 :: Ord a => [a] -> [a] -> [a]
interseccion3 = intersect

-- 4ª solución
-- ===========

interseccion4 :: Ord a => [a] -> [a] -> [a]
interseccion4 xs ys =
  S.toList (S.fromList xs `S.intersection` S.fromList ys)

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_interseccion :: [Int] -> [Int] -> Bool
prop_interseccion xs ys =
  all (== sort (xs' `interseccion1` ys'))
      [sort (xs' `interseccion2` ys'),
       sort (xs' `interseccion3` ys'),
       xs' `interseccion4` ys']
  where xs' = nub xs
        ys' = nub ys

-- La comprobación es
--    λ> quickCheck prop_interseccion
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (interseccion1 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (2.94 secs, 6,673,360 bytes)
--    λ> length (interseccion2 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (3.04 secs, 9,793,440 bytes)
--    λ> length (interseccion3 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (5.39 secs, 6,673,472 bytes)
--    λ> length (interseccion4 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (0.04 secs, 8,593,176 bytes)

import Data.List (nub, sort, intersect)

import qualified Data.Set as S (fromList, toList, intersection )

import Test.QuickCheck

-- 1ª solución

-- ===========

interseccion1 :: Eq a => [a] -> [a] -> [a]

interseccion1 xs ys =

[x | x <- xs, x `elem` ys]

-- 2ª solución

-- ===========

interseccion2 :: Ord a => [a] -> [a] -> [a]

interseccion2 [] _ = []

interseccion2 (x:xs) ys

| x `elem` ys = x : xs `interseccion2` ys

| otherwise = xs `interseccion2` ys

-- 3ª solución

-- ===========

interseccion3 :: Ord a => [a] -> [a] -> [a]

interseccion3 = intersect

-- 4ª solución

-- ===========

interseccion4 :: Ord a => [a] -> [a] -> [a]

interseccion4 xs ys =

S.toList (S.fromList xs `S.intersection` S.fromList ys)

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_interseccion :: [Int] -> [Int] -> Bool

prop_interseccion xs ys =

all (== sort (xs' `interseccion1` ys'))

[sort (xs' `interseccion2` ys'),

sort (xs' `interseccion3` ys'),

xs' `interseccion4` ys']

where xs' = nub xs

ys' = nub ys

-- La comprobación es

-- λ> quickCheck prop_interseccion

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (interseccion1 [0..3*10^4] [1,3..3*10^4])

-- 15000

-- (2.94 secs, 6,673,360 bytes)

-- λ> length (interseccion2 [0..3*10^4] [1,3..3*10^4])

-- 15000

-- (3.04 secs, 9,793,440 bytes)

-- λ> length (interseccion3 [0..3*10^4] [1,3..3*10^4])

-- 15000

-- (5.39 secs, 6,673,472 bytes)

-- λ> length (interseccion4 [0..3*10^4] [1,3..3*10^4])

-- 15000

-- (0.04 secs, 8,593,176 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from timeit import Timer, default_timer
from sys import setrecursionlimit
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución
# ===========

def interseccion1(xs: list[A], ys: list[A]) -> list[A]:
    return [x for x in xs if x in ys]

# 2ª solución
# ===========

def interseccion2(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return []
    if xs[0] in ys:
        return [xs[0]] + interseccion2(xs[1:], ys)
    return interseccion2(xs[1:], ys)

# 3ª solución
# ===========

def interseccion3(xs: list[A], ys: list[A]) -> list[A]:
    zs = []
    for x in xs:
        if x in ys:
            zs.append(x)
    return zs

# 4ª solución
# ===========

def interseccion4(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) & set(ys))

# Comprobación de equivalencia
# ============================
#
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_interseccion(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert sorted(interseccion1(xs1, ys1)) ==\
           sorted(interseccion2(xs1, ys1)) ==\
           sorted(interseccion3(xs1, ys1)) ==\
           sorted(interseccion4(xs1, ys1))

# La comprobación es
#    src> poetry run pytest -q interseccion_conjuntista_de_listas.py
#    1 passed in 0.33s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('interseccion1(list(range(0,20000)), list(range(1,20000,2)))')
#    0.98 segundos
#    >>> tiempo('interseccion2(list(range(0,20000)), list(range(1,20000,2)))')
#    2.13 segundos
#    >>> tiempo('interseccion3(list(range(0,20000)), list(range(1,20000,2)))')
#    0.87 segundos
#    >>> tiempo('interseccion4(list(range(0,20000)), list(range(1,20000,2)))')
#    0.00 segundos

from typing import TypeVar

from timeit import Timer, default_timer

from sys import setrecursionlimit

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

# ===========

def interseccion1(xs: list[A], ys: list[A]) -> list[A]:

return [x for x in xs if x in ys]

# 2ª solución

# ===========

def interseccion2(xs: list[A], ys: list[A]) -> list[A]:

if not xs:

return []

if xs[0] in ys:

return [xs[0]] + interseccion2(xs[1:], ys)

return interseccion2(xs[1:], ys)

# 3ª solución

# ===========

def interseccion3(xs: list[A], ys: list[A]) -> list[A]:

zs = []

for x in xs:

if x in ys:

zs.append(x)

return zs

# 4ª solución

# ===========

def interseccion4(xs: list[A], ys: list[A]) -> list[A]:

return list(set(xs) & set(ys))

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_interseccion(xs, ys):

xs1 = list(set(xs))

ys1 = list(set(ys))

assert sorted(interseccion1(xs1, ys1)) ==\

sorted(interseccion2(xs1, ys1)) ==\

sorted(interseccion3(xs1, ys1)) ==\

sorted(interseccion4(xs1, ys1))

# La comprobación es

# src> poetry run pytest -q interseccion_conjuntista_de_listas.py

# 1 passed in 0.33s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('interseccion1(list(range(0,20000)), list(range(1,20000,2)))')

# 0.98 segundos

# >>> tiempo('interseccion2(list(range(0,20000)), list(range(1,20000,2)))')

# 2.13 segundos

# >>> tiempo('interseccion3(list(range(0,20000)), list(range(1,20000,2)))')

# 0.87 segundos

# >>> tiempo('interseccion4(list(range(0,20000)), list(range(1,20000,2)))')

# 0.00 segundos

El código se encuentra en GitHub.

Unión conjuntista de listas

PorJosé A. Alonso 20-septiembre-202214-diciembre-2022

Definir la función

   union :: Ord a => [a] -> [a] -> [a]

1	union :: Ord a => [a] -> [a] -> [a]

tal que union xs ys es la unión de las listas, sin elementos repetidos, xs e ys. Por ejemplo,

   union [3,2,5] [5,7,3,4]  ==  [3,2,5,7,4]

1	union [3,2,5] [5,7,3,4] == [3,2,5,7,4]

Comprobar con QuickCheck que la unión es conmutativa.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (nub, sort, union)
import qualified Data.Set as S (fromList, toList, union)
import Test.QuickCheck

-- 1ª solución
-- ===========

union1 :: Ord a => [a] -> [a] -> [a]
union1 xs ys = xs ++ [y | y <- ys, y `notElem` xs]

-- 2ª solución
-- ===========

union2 :: Ord a => [a] -> [a] -> [a]
union2 [] ys = ys
union2 (x:xs) ys
  | x `elem` ys = xs `union2` ys
  | otherwise   = x : xs `union2` ys

-- 3ª solución
-- ===========

union3 :: Ord a => [a] -> [a] -> [a]
union3 = union

-- 4ª solución
-- ===========

union4 :: Ord a => [a] -> [a] -> [a]
union4 xs ys =
  S.toList (S.fromList xs `S.union` S.fromList ys)

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_union :: [Int] -> [Int] -> Bool
prop_union xs ys =
  all (== sort (xs' `union1` ys'))
      [sort (xs' `union2` ys'),
       sort (xs' `union3` ys'),
       xs' `union4` ys']
  where xs' = nub xs
        ys' = nub ys

-- La comprobación es
--    λ> quickCheck prop_union
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (union1 [0,2..3*10^4] [1,3..3*10^4])
--    30001
--    (2.37 secs, 7,153,536 bytes)
--    λ> length (union2 [0,2..3*10^4] [1,3..3*10^4])
--    30001
--    (2.38 secs, 6,553,752 bytes)
--    λ> length (union3 [0,2..3*10^4] [1,3..3*10^4])
--    30001
--    (11.56 secs, 23,253,553,472 bytes)
--    λ> length (union4 [0,2..3*10^4] [1,3..3*10^4])
--    30001
--    (0.04 secs, 10,992,056 bytes)

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_union_conmutativa :: [Int] -> [Int] -> Bool
prop_union_conmutativa xs ys =
  iguales (xs `union1` ys) (ys `union1` xs)

-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,
--    iguales [3,2,3] [2,3]    ==  True
--    iguales [3,2,3] [2,3,2]  ==  True
--    iguales [3,2,3] [2,3,4]  ==  False
--    iguales [2,3] [4,5]      ==  False
iguales :: Ord a => [a] -> [a] -> Bool
iguales xs ys =
  S.fromList xs == S.fromList ys

-- La comprobación es
--    λ> quickCheck prop_union_conmutativa
--    +++ OK, passed 100 tests.

import Data.List (nub, sort, union)

import qualified Data.Set as S (fromList, toList, union)

import Test.QuickCheck

-- 1ª solución

-- ===========

union1 :: Ord a => [a] -> [a] -> [a]

union1 xs ys = xs ++ [y | y <- ys, y `notElem` xs]

-- 2ª solución

-- ===========

union2 :: Ord a => [a] -> [a] -> [a]

union2 [] ys = ys

union2 (x:xs) ys

| x `elem` ys = xs `union2` ys

| otherwise = x : xs `union2` ys

-- 3ª solución

-- ===========

union3 :: Ord a => [a] -> [a] -> [a]

union3 = union

-- 4ª solución

-- ===========

union4 :: Ord a => [a] -> [a] -> [a]

union4 xs ys =

S.toList (S.fromList xs `S.union` S.fromList ys)

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_union :: [Int] -> [Int] -> Bool

prop_union xs ys =

all (== sort (xs' `union1` ys'))

[sort (xs' `union2` ys'),

sort (xs' `union3` ys'),

xs' `union4` ys']

where xs' = nub xs

ys' = nub ys

-- La comprobación es

-- λ> quickCheck prop_union

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (union1 [0,2..3*10^4] [1,3..3*10^4])

-- 30001

-- (2.37 secs, 7,153,536 bytes)

-- λ> length (union2 [0,2..3*10^4] [1,3..3*10^4])

-- 30001

-- (2.38 secs, 6,553,752 bytes)

-- λ> length (union3 [0,2..3*10^4] [1,3..3*10^4])

-- 30001

-- (11.56 secs, 23,253,553,472 bytes)

-- λ> length (union4 [0,2..3*10^4] [1,3..3*10^4])

-- 30001

-- (0.04 secs, 10,992,056 bytes)

-- Comprobación de la propiedad

-- ============================

-- La propiedad es

prop_union_conmutativa :: [Int] -> [Int] -> Bool

prop_union_conmutativa xs ys =

iguales (xs `union1` ys) (ys `union1` xs)

-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,

-- iguales [3,2,3] [2,3] == True

-- iguales [3,2,3] [2,3,2] == True

-- iguales [3,2,3] [2,3,4] == False

-- iguales [2,3] [4,5] == False

iguales :: Ord a => [a] -> [a] -> Bool

iguales xs ys =

S.fromList xs == S.fromList ys

-- La comprobación es

-- λ> quickCheck prop_union_conmutativa

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from timeit import Timer, default_timer
from sys import setrecursionlimit
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución
# ===========

def union1(xs: list[A], ys: list[A]) -> list[A]:
    return xs + [y for y in ys if y not in xs]

# 2ª solución
# ===========

def union2(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return ys
    if xs[0] in ys:
        return union2(xs[1:], ys)
    return [xs[0]] + union2(xs[1:], ys)

# 3ª solución
# ===========

def union3(xs: list[A], ys: list[A]) -> list[A]:
    zs = ys[:]
    for x in xs:
        if x not in ys:
            zs.append(x)
    return zs

# 4ª solución
# ===========

def union4(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) | set(ys))

# Comprobación de equivalencia
# ============================
#
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_union(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert sorted(union1(xs1, ys1)) ==\
           sorted(union2(xs1, ys1)) ==\
           sorted(union3(xs1, ys1)) ==\
           sorted(union4(xs1, ys1))

# La comprobación es
#    src> poetry run pytest -q union_conjuntista_de_listas.py
#    1 passed in 0.36s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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('union1(list(range(0,30000,2)), list(range(1,30000,2)))')
#    1.30 segundos
#    >>> tiempo('union2(list(range(0,30000,2)), list(range(1,30000,2)))')
#    2.84 segundos
#    >>> tiempo('union3(list(range(0,30000,2)), list(range(1,30000,2)))')
#    1.45 segundos
#    >>> tiempo('union4(list(range(0,30000,2)), list(range(1,30000,2)))')
#    0.00 segundos

# Comprobación de la propiedad
# ============================

# iguales(xs, ys) se verifica si xs e ys son iguales como conjuntos. Por
# ejemplo,
#    iguales([3,2,3], [2,3])    ==  True
#    iguales([3,2,3], [2,3,2])  ==  True
#    iguales([3,2,3], [2,3,4])  ==  False
#    iguales([2,3], [4,5])      ==  False
def iguales(xs: list[A], ys: list[A]) -> bool:
    return set(xs) == set(ys)

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_union_conmutativa(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert iguales(union1(xs1, ys1), union1(ys1, xs1))

# La comprobación es
#    src> poetry run pytest -q union_conjuntista_de_listas.py
#    2 passed in 0.49s

100

from typing import TypeVar

from timeit import Timer, default_timer

from sys import setrecursionlimit

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

# ===========

def union1(xs: list[A], ys: list[A]) -> list[A]:

return xs + [y for y in ys if y not in xs]

# 2ª solución

# ===========

def union2(xs: list[A], ys: list[A]) -> list[A]:

if not xs:

return ys

if xs[0] in ys:

return union2(xs[1:], ys)

return [xs[0]] + union2(xs[1:], ys)

# 3ª solución

# ===========

def union3(xs: list[A], ys: list[A]) -> list[A]:

zs = ys[:]

for x in xs:

if x not in ys:

zs.append(x)

return zs

# 4ª solución

# ===========

def union4(xs: list[A], ys: list[A]) -> list[A]:

return list(set(xs) | set(ys))

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_union(xs, ys):

xs1 = list(set(xs))

ys1 = list(set(ys))

assert sorted(union1(xs1, ys1)) ==\

sorted(union2(xs1, ys1)) ==\

sorted(union3(xs1, ys1)) ==\

sorted(union4(xs1, ys1))

# La comprobación es

# src> poetry run pytest -q union_conjuntista_de_listas.py

# 1 passed in 0.36s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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('union1(list(range(0,30000,2)), list(range(1,30000,2)))')

# 1.30 segundos

# >>> tiempo('union2(list(range(0,30000,2)), list(range(1,30000,2)))')

# 2.84 segundos

# >>> tiempo('union3(list(range(0,30000,2)), list(range(1,30000,2)))')

# 1.45 segundos

# >>> tiempo('union4(list(range(0,30000,2)), list(range(1,30000,2)))')

# 0.00 segundos

# Comprobación de la propiedad

# ============================

# iguales(xs, ys) se verifica si xs e ys son iguales como conjuntos. Por

# ejemplo,

# iguales([3,2,3], [2,3]) == True

# iguales([3,2,3], [2,3,2]) == True

# iguales([3,2,3], [2,3,4]) == False

# iguales([2,3], [4,5]) == False

def iguales(xs: list[A], ys: list[A]) -> bool:

return set(xs) == set(ys)

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_union_conmutativa(xs, ys):

xs1 = list(set(xs))

ys1 = list(set(ys))

assert iguales(union1(xs1, ys1), union1(ys1, xs1))

# La comprobación es

# src> poetry run pytest -q union_conjuntista_de_listas.py

# 2 passed in 0.49s

El código se encuentra en GitHub

Igualdad de conjuntos

PorJosé A. Alonso 19-septiembre-202214-diciembre-2022

Definir la función

   iguales :: Ord a => [a] -> [a] -> Bool

1	iguales :: Ord a => [a] -> [a] -> Bool

tal que iguales xs ys se verifica si xs e ys son iguales como conjuntos. Por ejemplo,

   iguales [3,2,3] [2,3]    ==  True
   iguales [3,2,3] [2,3,2]  ==  True
   iguales [3,2,3] [2,3,4]  ==  False
   iguales [2,3] [4,5]      ==  False

iguales [3,2,3] [2,3] == True

iguales [3,2,3] [2,3,2] == True

iguales [3,2,3] [2,3,4] == False

iguales [2,3] [4,5] == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Data.List (nub, sort)
import Data.Set (fromList)
import Test.QuickCheck

-- 1ª solución
-- ===========

iguales1 :: Ord a => [a] -> [a] -> Bool
iguales1 xs ys =
  subconjunto xs ys && subconjunto ys xs

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. Por
-- ejemplo,
--    subconjunto [3,2,3] [2,5,3,5]  ==  True
--    subconjunto [3,2,3] [2,5,6,5]  ==  False
subconjunto :: Ord a => [a] -> [a] -> Bool
subconjunto xs ys =
  [x | x <- xs, x `elem` ys] == xs

-- 2ª solución
-- ===========

iguales2 :: Ord a => [a] -> [a] -> Bool
iguales2 xs ys =
  nub (sort xs) == nub (sort ys)

-- 3ª solución
-- ===========

iguales3 :: Ord a => [a] -> [a] -> Bool
iguales3 xs ys =
  fromList xs == fromList ys

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_iguales :: [Int] -> [Int] -> Bool
prop_iguales xs ys =
  all (== iguales1 xs ys)
      [iguales2 xs ys,
       iguales3 xs ys]

-- La comprobación es
--    λ> quickCheck prop_iguales
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> iguales1 [1..2*10^4] [1..2*10^4]
--    True
--    (4.05 secs, 8,553,104 bytes)
--    λ> iguales2 [1..2*10^4] [1..2*10^4]
--    True
--    (4.14 secs, 9,192,768 bytes)
--    λ> iguales3 [1..2*10^4] [1..2*10^4]
--    True
--    (0.01 secs, 8,552,232 bytes)

import Data.List (nub, sort)

import Data.Set (fromList)

import Test.QuickCheck

-- 1ª solución

-- ===========

iguales1 :: Ord a => [a] -> [a] -> Bool

iguales1 xs ys =

subconjunto xs ys && subconjunto ys xs

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. Por

-- ejemplo,

-- subconjunto [3,2,3] [2,5,3,5] == True

-- subconjunto [3,2,3] [2,5,6,5] == False

subconjunto :: Ord a => [a] -> [a] -> Bool

subconjunto xs ys =

[x | x <- xs, x `elem` ys] == xs

-- 2ª solución

-- ===========

iguales2 :: Ord a => [a] -> [a] -> Bool

iguales2 xs ys =

nub (sort xs) == nub (sort ys)

-- 3ª solución

-- ===========

iguales3 :: Ord a => [a] -> [a] -> Bool

iguales3 xs ys =

fromList xs == fromList ys

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_iguales :: [Int] -> [Int] -> Bool

prop_iguales xs ys =

all (== iguales1 xs ys)

[iguales2 xs ys,

iguales3 xs ys]

-- La comprobación es

-- λ> quickCheck prop_iguales

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> iguales1 [1..2*10^4] [1..2*10^4]

-- True

-- (4.05 secs, 8,553,104 bytes)

-- λ> iguales2 [1..2*10^4] [1..2*10^4]

-- True

-- (4.14 secs, 9,192,768 bytes)

-- λ> iguales3 [1..2*10^4] [1..2*10^4]

-- True

-- (0.01 secs, 8,552,232 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from typing import Any
from timeit import Timer, default_timer
from hypothesis import given, strategies as st

# 1ª solución
# ===========

def subconjunto(xs: list[Any],
                ys: list[Any]) -> bool:
    return [x for x in xs if x in ys] == xs

def iguales1(xs: list[Any],
             ys: list[Any]) -> bool:
    return subconjunto(xs, ys) and subconjunto(ys, xs)

# 2ª solución
# ===========

def iguales2(xs: list[Any],
             ys: list[Any]) -> bool:
    return set(xs) == set(ys)

# Equivalencia de las definiciones
# ================================

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_iguales(xs, ys):
    assert iguales1(xs, ys) == iguales2(xs, ys)

# La comprobación es
#    src> poetry run pytest -q igualdad_de_conjuntos.py
#    1 passed in 0.28s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """Tiempo medio (en segundos) de 10 evaluaciones de la expresión e.
    """
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> xs = list(range(20000))
#    >>> tiempo('iguales1(xs, xs)')
#    2.71 segundos
#    >>> tiempo('iguales2(xs, xs)')
#    0.01 segundos

from typing import Any

from timeit import Timer, default_timer

from hypothesis import given, strategies as st

# 1ª solución

# ===========

def subconjunto(xs: list[Any],

ys: list[Any]) -> bool:

return [x for x in xs if x in ys] == xs

def iguales1(xs: list[Any],

ys: list[Any]) -> bool:

return subconjunto(xs, ys) and subconjunto(ys, xs)

# 2ª solución

# ===========

def iguales2(xs: list[Any],

ys: list[Any]) -> bool:

return set(xs) == set(ys)

# Equivalencia de las definiciones

# ================================

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_iguales(xs, ys):

assert iguales1(xs, ys) == iguales2(xs, ys)

# La comprobación es

# src> poetry run pytest -q igualdad_de_conjuntos.py

# 1 passed in 0.28s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""Tiempo medio (en segundos) de 10 evaluaciones de la expresión e.

"""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> xs = list(range(20000))

# >>> tiempo('iguales1(xs, xs)')

# 2.71 segundos

# >>> tiempo('iguales2(xs, xs)')

# 0.01 segundos

El código se encuentra en GitHub

Reconocimiento de subconjunto

PorJosé A. Alonso 16-septiembre-202214-diciembre-2022

Definir la función

   subconjunto :: Ord a => [a] -> [a] -> Bool

1	subconjunto :: Ord a => [a] -> [a] -> Bool

tal que subconjunto xs ys se verifica si xs es un subconjunto de ys. por ejemplo,

   subconjunto [3,2,3] [2,5,3,5]  ==  True
   subconjunto [3,2,3] [2,5,6,5]  ==  False

1 2	subconjunto [3,2,3] [2,5,3,5] == True subconjunto [3,2,3] [2,5,6,5] == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Reconocimiento_de_subconjunto where

import Data.List (nub, sort)
import Data.Set (fromList, isSubsetOf)
import Test.QuickCheck

-- 1ª solución
subconjunto1 :: Ord a => [a] -> [a] -> Bool
subconjunto1 xs ys =
  [x | x <- xs, x `elem` ys] == xs

-- 2ª solución
subconjunto2 :: Ord a => [a] -> [a] -> Bool
subconjunto2 []     _  = True
subconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys

-- 3ª solución
subconjunto3 :: Ord a => [a] -> [a] -> Bool
subconjunto3 xs ys =
  all (`elem` ys) xs

-- 4ª solución
subconjunto4 :: Ord a => [a] -> [a] -> Bool
subconjunto4 xs ys =
  fromList xs `isSubsetOf` fromList ys

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_subconjunto :: [Int] -> [Int] -> Bool
prop_subconjunto xs ys =
  all (== subconjunto1 xs ys)
      [subconjunto2 xs ys,
       subconjunto3 xs ys,
       subconjunto4 xs ys]

-- La comprobación es
--    λ> quickCheck prop_subconjunto
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> subconjunto1 [1..2*10^4] [1..2*10^4]
--    True
--    (1.81 secs, 5,992,448 bytes)
--    λ> subconjunto2 [1..2*10^4] [1..2*10^4]
--    True
--    (1.83 secs, 6,952,200 bytes)
--    λ> subconjunto3 [1..2*10^4] [1..2*10^4]
--    True
--    (1.75 secs, 4,712,304 bytes)
--    λ> subconjunto4 [1..2*10^4] [1..2*10^4]
--    True
--    (0.04 secs, 6,312,056 bytes)

module Reconocimiento_de_subconjunto where

import Data.List (nub, sort)

import Data.Set (fromList, isSubsetOf)

import Test.QuickCheck

-- 1ª solución

subconjunto1 :: Ord a => [a] -> [a] -> Bool

subconjunto1 xs ys =

[x | x <- xs, x `elem` ys] == xs

-- 2ª solución

subconjunto2 :: Ord a => [a] -> [a] -> Bool

subconjunto2 [] _ = True

subconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys

-- 3ª solución

subconjunto3 :: Ord a => [a] -> [a] -> Bool

subconjunto3 xs ys =

all (`elem` ys) xs

-- 4ª solución

subconjunto4 :: Ord a => [a] -> [a] -> Bool

subconjunto4 xs ys =

fromList xs `isSubsetOf` fromList ys

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_subconjunto :: [Int] -> [Int] -> Bool

prop_subconjunto xs ys =

all (== subconjunto1 xs ys)

[subconjunto2 xs ys,

subconjunto3 xs ys,

subconjunto4 xs ys]

-- La comprobación es

-- λ> quickCheck prop_subconjunto

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> subconjunto1 [1..2*10^4] [1..2*10^4]

-- True

-- (1.81 secs, 5,992,448 bytes)

-- λ> subconjunto2 [1..2*10^4] [1..2*10^4]

-- True

-- (1.83 secs, 6,952,200 bytes)

-- λ> subconjunto3 [1..2*10^4] [1..2*10^4]

-- True

-- (1.75 secs, 4,712,304 bytes)

-- λ> subconjunto4 [1..2*10^4] [1..2*10^4]

-- True

-- (0.04 secs, 6,312,056 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from timeit import Timer, default_timer
from sys import setrecursionlimit
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución
def subconjunto1(xs: list[A],
                 ys: list[A]) -> bool:
    return [x for x in xs if x in ys] == xs

# 2ª solución
def subconjunto2(xs: list[A],
                 ys: list[A]) -> bool:
    if xs:
        return xs[0] in ys and subconjunto2(xs[1:], ys)
    return True

# 3ª solución
def subconjunto3(xs: list[A],
                 ys: list[A]) -> bool:
    return all(x in ys for x in xs)

# 4ª solución
def subconjunto4(xs: list[A],
                 ys: list[A]) -> bool:
    return set(xs) <= set(ys)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_subconjunto(xs, ys):
    assert subconjunto1(xs, ys)\
           == subconjunto2(xs, ys)\
           == subconjunto3(xs, ys)\
           == subconjunto4(xs, ys)

# La comprobación es
#    src> poetry run pytest -q reconocimiento_de_subconjunto.py
#    1 passed in 0.34s

# Comparación de eficiencia
# =========================

def tiempo(e):
    """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
#    >>> xs = list(range(20000))
#    >>> tiempo('subconjunto1(xs, xs)')
#    1.27 segundos
#    >>> tiempo('subconjunto2(xs, xs)')
#    1.84 segundos
#    >>> tiempo('subconjunto3(xs, xs)')
#    1.19 segundos
#    >>> tiempo('subconjunto4(xs, xs)')
#    0.01 segundos

from typing import TypeVar

from timeit import Timer, default_timer

from sys import setrecursionlimit

from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

def subconjunto1(xs: list[A],

ys: list[A]) -> bool:

return [x for x in xs if x in ys] == xs

# 2ª solución

def subconjunto2(xs: list[A],

ys: list[A]) -> bool:

if xs:

return xs[0] in ys and subconjunto2(xs[1:], ys)

return True

# 3ª solución

def subconjunto3(xs: list[A],

ys: list[A]) -> bool:

return all(x in ys for x in xs)

# 4ª solución

def subconjunto4(xs: list[A],

ys: list[A]) -> bool:

return set(xs) <= set(ys)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_subconjunto(xs, ys):

assert subconjunto1(xs, ys)\

== subconjunto2(xs, ys)\

== subconjunto3(xs, ys)\

== subconjunto4(xs, ys)

# La comprobación es

# src> poetry run pytest -q reconocimiento_de_subconjunto.py

# 1 passed in 0.34s

# Comparación de eficiencia

# =========================

def tiempo(e):

"""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

# >>> xs = list(range(20000))

# >>> tiempo('subconjunto1(xs, xs)')

# 1.27 segundos

# >>> tiempo('subconjunto2(xs, xs)')

# 1.84 segundos

# >>> tiempo('subconjunto3(xs, xs)')

# 1.19 segundos

# >>> tiempo('subconjunto4(xs, xs)')

# 0.01 segundos

El código se encuentra en GitHub.

Comentarios

La expresión «x pertenece a ys» se escribe
- en Haskell, como x `elem` ys
- en Python, como x in ys
La expresión «todos los elementos de xs verifican la propiedad p» se escribe
- en Haskell, como all p xs
- en Python, como all(p(x) for x in xs)
Si xs e ys son conjuntos, la expresión «xs es subconjunto de ys» se escribe
- en Haskell, como xs `isSubsetOf` ys
- en Python, como xs <= ys

Números racionales

PorJosé A. Alonso 15-septiembre-202214-diciembre-2022

Los números racionales pueden representarse mediante pares de números enteros. Por ejemplo, el número 2/5 puede representarse mediante el par (2,5).

Definir las funciones

   formaReducida    :: (Int,Int) -> (Int,Int)
   sumaRacional     :: (Int,Int) -> (Int,Int) -> (Int,Int)
   productoRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)
   igualdadRacional :: (Int,Int) -> (Int,Int) -> Bool

formaReducida :: (Int,Int) -> (Int,Int)

sumaRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)

productoRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)

igualdadRacional :: (Int,Int) -> (Int,Int) -> Bool

tales que

formaReducida x es la forma reducida del número racional x. Por ejemplo,

     formaReducida (4,10)  ==  (2,5)
     formaReducida (0,5)   ==  (0,1)

1 2	formaReducida (4,10) == (2,5) formaReducida (0,5) == (0,1)

sumaRacional x y es la suma de los números racionales x e y, expresada en forma reducida. Por ejemplo,

     sumaRacional (2,3) (5,6)  ==  (3,2)
     sumaRacional (3,5) (-3,5) ==  (0,1)

1 2	sumaRacional (2,3) (5,6) == (3,2) sumaRacional (3,5) (-3,5) == (0,1)

productoRacional x y es el producto de los números racionales x e y, expresada en forma reducida. Por ejemplo,

     productoRacional (2,3) (5,6)  ==  (5,9)

1	productoRacional (2,3) (5,6) == (5,9)

igualdadRacional x y se verifica si los números racionales x e y son iguales. Por ejemplo,

     igualdadRacional (6,9) (10,15)  ==  True
     igualdadRacional (6,9) (11,15)  ==  False
     igualdadRacional (0,2) (0,-5)   ==  True

igualdadRacional (6,9) (10,15) == True

igualdadRacional (6,9) (11,15) == False

igualdadRacional (0,2) (0,-5) == True

Comprobar con QuickCheck la propiedad distributiva del producto racional respecto de la suma.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

formaReducida :: (Int,Int) -> (Int,Int)
formaReducida (0,_) = (0,1)
formaReducida (a,b) = (a `div` c, b  `div` c)
    where c = gcd a b

sumaRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)
sumaRacional (a,b) (c,d) = formaReducida (a*d+b*c, b*d)

productoRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)
productoRacional (a,b) (c,d) = formaReducida (a*c, b*d)

igualdadRacional :: (Int,Int) -> (Int,Int) -> Bool
igualdadRacional (a,b) (c,d) =
    a*d == b*c

-- La propiedad es
prop_distributiva :: (Int,Int) -> (Int,Int) -> (Int,Int) -> Property
prop_distributiva x y z =
  snd x /= 0 && snd y /= 0 && snd z /= 0 ==>
  igualdadRacional (productoRacional x (sumaRacional y z))
                   (sumaRacional (productoRacional x y)
                                 (productoRacional x z))

-- La comprobación es
--    λ> quickCheck prop_distributiva
--    +++ OK, passed 100 tests; 21 discarded.

import Test.QuickCheck

formaReducida :: (Int,Int) -> (Int,Int)

formaReducida (0,_) = (0,1)

formaReducida (a,b) = (a `div` c, b `div` c)

where c = gcd a b

sumaRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)

sumaRacional (a,b) (c,d) = formaReducida (a*d+b*c, b*d)

productoRacional :: (Int,Int) -> (Int,Int) -> (Int,Int)

productoRacional (a,b) (c,d) = formaReducida (a*c, b*d)

igualdadRacional :: (Int,Int) -> (Int,Int) -> Bool

igualdadRacional (a,b) (c,d) =

a*d == b*c

-- La propiedad es

prop_distributiva :: (Int,Int) -> (Int,Int) -> (Int,Int) -> Property

prop_distributiva x y z =

snd x /= 0 && snd y /= 0 && snd z /= 0 ==>

igualdadRacional (productoRacional x (sumaRacional y z))

(sumaRacional (productoRacional x y)

(productoRacional x z))

-- La comprobación es

-- λ> quickCheck prop_distributiva

-- +++ OK, passed 100 tests; 21 discarded.

El código se encuentra en GitHub.

Soluciones en Python

from math import gcd
from hypothesis import given, assume, strategies as st

Racional = tuple[int, int]

def formaReducida(x: Racional) -> Racional:
    (a, b) = x
    if a == 0:
        return (0, 1)
    c = gcd(a, b)
    return (a // c, b // c)

def sumaRacional(x: Racional,
                 y: Racional) -> Racional:
    (a, b) = x
    (c, d) = y
    return formaReducida((a*d+b*c, b*d))

def productoRacional(x: Racional,
                     y: Racional) -> Racional:
    (a, b) = x
    (c, d) = y
    return formaReducida((a*c, b*d))

def igualdadRacional(x: Racional,
                     y: Racional) -> bool:
    (a, b) = x
    (c, d) = y
    return a*d == b*c

# La propiedad es
@given(st.tuples(st.integers(), st.integers()),
       st.tuples(st.integers(), st.integers()),
       st.tuples(st.integers(), st.integers()))
def test_prop_distributiva(x, y, z):
    (_, x2) = x
    (_, y2) = y
    (_, z2) = z
    assume(x2 != 0 and y2 != 0 and z2 != 0)
    assert igualdadRacional(productoRacional(x, sumaRacional(y, z)),
                            sumaRacional(productoRacional(x, y),
                                         productoRacional(x, z)))

# La comprobación es
#    src> poetry run pytest -q numeros_racionales.py
#    1 passed in 0.37s

from math import gcd

from hypothesis import given, assume, strategies as st

Racional = tuple[int, int]

def formaReducida(x: Racional) -> Racional:

(a, b) = x

if a == 0:

return (0, 1)

c = gcd(a, b)

return (a // c, b // c)

def sumaRacional(x: Racional,

y: Racional) -> Racional:

(a, b) = x

(c, d) = y

return formaReducida((a*d+b*c, b*d))

def productoRacional(x: Racional,

y: Racional) -> Racional:

(a, b) = x

(c, d) = y

return formaReducida((a*c, b*d))

def igualdadRacional(x: Racional,

y: Racional) -> bool:

(a, b) = x

(c, d) = y

return a*d == b*c

# La propiedad es

@given(st.tuples(st.integers(), st.integers()),

st.tuples(st.integers(), st.integers()),

st.tuples(st.integers(), st.integers()))

def test_prop_distributiva(x, y, z):

(_, x2) = x

(_, y2) = y

(_, z2) = z

assume(x2 != 0 and y2 != 0 and z2 != 0)

assert igualdadRacional(productoRacional(x, sumaRacional(y, z)),

sumaRacional(productoRacional(x, y),

productoRacional(x, z)))

# La comprobación es

# src> poetry run pytest -q numeros_racionales.py

# 1 passed in 0.37s

El código se encuentra en GitHub.

Intersección de intervalos cerrados

PorJosé A. Alonso 14-septiembre-202214-diciembre-2022

Los intervalos cerrados se pueden representar mediante una lista de dos números (el primero es el extremo inferior del intervalo y el segundo el superior).

Definir la función

   interseccion :: Ord a => [a] -> [a] -> [a]

1	interseccion :: Ord a => [a] -> [a] -> [a]

tal que (interseccion i1 i2) es la intersección de los intervalos i1 e i2. Por ejemplo,

   interseccion [] [3,5]     ==  []
   interseccion [3,5] []     ==  []
   interseccion [2,4] [6,9]  ==  []
   interseccion [2,6] [6,9]  ==  [6,6]
   interseccion [2,6] [0,9]  ==  [2,6]
   interseccion [2,6] [0,4]  ==  [2,4]
   interseccion [4,6] [0,4]  ==  [4,4]
   interseccion [5,6] [0,4]  ==  []

interseccion [] [3,5] == []

interseccion [3,5] [] == []

interseccion [2,4] [6,9] == []

interseccion [2,6] [6,9] == [6,6]

interseccion [2,6] [0,9] == [2,6]

interseccion [2,6] [0,4] == [2,4]

interseccion [4,6] [0,4] == [4,4]

interseccion [5,6] [0,4] == []

Comprobar con QuickCheck que la intersección de intervalos es conmutativa.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

interseccion :: Ord a => [a] -> [a] -> [a]
interseccion [] _ = []
interseccion _ [] = []
interseccion [a1,b1] [a2,b2]
    | a <= b    = [a,b]
    | otherwise = []
    where a = max a1 a2
          b = min b1 b2

-- La propiedad es
prop_interseccion :: Int -> Int -> Int -> Int -> Property
prop_interseccion a1 b1 a2 b2 =
  a1 <= b1 && a2 <= b2 ==>
  interseccion [a1,b1] [a2,b2] == interseccion [a2,b2] [a1,b1]

-- La comprobación es
--    λ> quickCheck prop_interseccion
--    +++ OK, passed 100 tests; 263 discarded.

import Test.QuickCheck

interseccion :: Ord a => [a] -> [a] -> [a]

interseccion [] _ = []

interseccion _ [] = []

interseccion [a1,b1] [a2,b2]

| a <= b = [a,b]

| otherwise = []

where a = max a1 a2

b = min b1 b2

-- La propiedad es

prop_interseccion :: Int -> Int -> Int -> Int -> Property

prop_interseccion a1 b1 a2 b2 =

a1 <= b1 && a2 <= b2 ==>

interseccion [a1,b1] [a2,b2] == interseccion [a2,b2] [a1,b1]

-- La comprobación es

-- λ> quickCheck prop_interseccion

-- +++ OK, passed 100 tests; 263 discarded.

El código se encuentra en GitHub.

Soluciones en Python

from hypothesis import given, assume, strategies as st

Rectangulo = list[float]

def interseccion(i1: Rectangulo,
                 i2: Rectangulo) -> Rectangulo:
    if i1 and i2:
        [a1, b1] = i1
        [a2, b2] = i2
        a = max(a1, a2)
        b = min(b1, b2)
        if a <= b:
            return [a, b]
        return []
    return []

# La propiedad es
@given(st.floats(), st.floats(), st.floats(), st.floats())
def test_prop_raices(a1, b1, a2, b2):
    assume(a1 <= b1 and a2 <= b2)
    assert interseccion([a1, b1], [a2, b2]) == interseccion([a2, b2], [a1, b1])

# La comprobación es
#    src> poetry run pytest -q interseccion_de_intervalos_cerrados.py
#    1 passed in 0.64s

from hypothesis import given, assume, strategies as st

Rectangulo = list[float]

def interseccion(i1: Rectangulo,

i2: Rectangulo) -> Rectangulo:

if i1 and i2:

[a1, b1] = i1

[a2, b2] = i2

a = max(a1, a2)

b = min(b1, b2)

if a <= b:

return [a, b]

return []

# La propiedad es

@given(st.floats(), st.floats(), st.floats(), st.floats())

def test_prop_raices(a1, b1, a2, b2):

assume(a1 <= b1 and a2 <= b2)

assert interseccion([a1, b1], [a2, b2]) == interseccion([a2, b2], [a1, b1])

# La comprobación es

# src> poetry run pytest -q interseccion_de_intervalos_cerrados.py

# 1 passed in 0.64s

El código se encuentra en GitHub.

Fórmula de Herón para el área de un triángulo

PorJosé A. Alonso 13-septiembre-202214-diciembre-2022

La fórmula de Herón, descubierta por Herón de Alejandría, dice que el área de un triángulo cuyo lados miden a, b y c es la raíz cuadrada de s(s-a)(s-b)(s-c) donde s es el semiperímetro

   s = (a+b+c)/2

1	s = (a+b+c)/2

Definir la función

   area :: Double -> Double -> Double -> Double

1	area :: Double -> Double -> Double -> Double

tal que (area a b c) es el área del triángulo de lados a, b y c. Por ejemplo,

   area 3 4 5  ==  6.0

1	area 3 4 5 == 6.0

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

area :: Double -> Double -> Double -> Double
area a b c = sqrt (s*(s-a)*(s-b)*(s-c))
  where s = (a+b+c)/2

area :: Double -> Double -> Double -> Double

area a b c = sqrt (s*(s-a)*(s-b)*(s-c))

where s = (a+b+c)/2

El código se encuentra en GitHub.

Soluciones en Python

from math import sqrt

def area(a: float, b: float, c: float) -> float:
    s = (a+b+c)/2
    return sqrt(s*(s-a)*(s-b)*(s-c))

from math import sqrt

def area(a: float, b: float, c: float) -> float:

s = (a+b+c)/2

return sqrt(s*(s-a)*(s-b)*(s-c))

El código se encuentra en GitHub.

Raíces de la ecuación de segundo grado

PorJosé A. Alonso 12-septiembre-202214-diciembre-2022

Definir la función

   raices :: Double -> Double -> Double -> [Double]

1	raices :: Double -> Double -> Double -> [Double]

tal que (raices a b c) es la lista de las raíces reales de la ecuación $ax^2 + bx + c = 0$ . Por ejemplo,

   raices 1 3 2    ==  [-1.0,-2.0]
   raices 1 (-2) 1 ==  [1.0,1.0]
   raices 1 0 1    ==  []

raices 1 3 2 == [-1.0,-2.0]

raices 1 (-2) 1 == [1.0,1.0]

raices 1 0 1 == []

Comprobar con QuickCheck que la suma de las raíces de la ecuación $ax^2 + bx + c = 0$ (con $a$ no nulo) es $\dfrac{-b}{a}$ y su producto es $\dfrac{c}{a}$ .

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

raices :: Double -> Double -> Double -> [Double]
raices a b c
    | d >= 0    = [(-b+e)/t,(-b-e)/t]
    | otherwise = []
    where d = b^2 - 4*a*c
          e = sqrt d
          t = 2*a

-- Para comprobar la propiedad se usará el operador
--    (~=) :: (Fractional a, Ord a) => a -> a -> Bool
-- tal que (x ~= y) se verifica si x e y son casi iguales; es decir si
-- el valor absoluto de su diferencia es menor que una milésima. Por
-- ejemplo,
--    12.3457 ~= 12.3459  ==  True
--    12.3457 ~= 12.3479  ==  False
(~=) :: (Fractional a, Ord a) => a -> a -> Bool
x ~= y  = abs (x-y) < 0.001

-- La propiedad es
prop_raices :: Double -> Double -> Double -> Property
prop_raices a b c =
    a /= 0 && not (null xs) ==> sum xs ~= (-b/a) && product xs ~= (c/a)
    where xs = raices a b c

-- La comprobación es
--    λ> quickCheck prop_raices
--    +++ OK, passed 100 tests.

import Test.QuickCheck

raices :: Double -> Double -> Double -> [Double]

raices a b c

| d >= 0 = [(-b+e)/t,(-b-e)/t]

| otherwise = []

where d = b^2 - 4*a*c

e = sqrt d

t = 2*a

-- Para comprobar la propiedad se usará el operador

-- (~=) :: (Fractional a, Ord a) => a -> a -> Bool

-- tal que (x ~= y) se verifica si x e y son casi iguales; es decir si

-- el valor absoluto de su diferencia es menor que una milésima. Por

-- ejemplo,

-- 12.3457 ~= 12.3459 == True

-- 12.3457 ~= 12.3479 == False

(~=) :: (Fractional a, Ord a) => a -> a -> Bool

x ~= y = abs (x-y) < 0.001

-- La propiedad es

prop_raices :: Double -> Double -> Double -> Property

prop_raices a b c =

a /= 0 && not (null xs) ==> sum xs ~= (-b/a) && product xs ~= (c/a)

where xs = raices a b c

-- La comprobación es

-- λ> quickCheck prop_raices

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Soluciones en Python

from math import sqrt
from hypothesis import given, assume, strategies as st

def raices(a: float, b: float, c: float) -> list[float]:
    d = b**2 - 4*a*c
    if d >= 0:
        e = sqrt(d)
        t = 2*a
        return [(-b+e)/t, (-b-e)/t]
    return []

# Para comprobar la propiedad se usará la función
#    casiIguales : (float, float) -> bool
# tal que casiIguales(x, y) se verifica si x e y son casi iguales; es
# decir si el valor absoluto de su diferencia es menor que una
# milésima. Por  ejemplo,
#    casiIguales(12.3457, 12.3459)  ==  True
#    casiIguales(12.3457, 12.3479)  ==  False
def casiIguales(x: float, y: float) -> bool:
    return abs(x - y) < 0.001

# La propiedad es
@given(st.floats(min_value=-100, max_value=100),
       st.floats(min_value=-100, max_value=100),
       st.floats(min_value=-100, max_value=100))
def test_prop_raices(a, b, c):
    assume(abs(a) > 0.1)
    xs = raices(a, b, c)
    assume(xs)
    [x1, x2] = xs
    assert casiIguales(x1 + x2, -b / a)
    assert casiIguales(x1 * x2, c / a)

# La comprobación es
#    src> poetry run pytest -q raices_de_la_ecuacion_de_segundo_grado.py
#    1 passed in 0.35s

from math import sqrt

from hypothesis import given, assume, strategies as st

def raices(a: float, b: float, c: float) -> list[float]:

d = b**2 - 4*a*c

if d >= 0:

e = sqrt(d)

t = 2*a

return [(-b+e)/t, (-b-e)/t]

return []

# Para comprobar la propiedad se usará la función

# casiIguales : (float, float) -> bool

# tal que casiIguales(x, y) se verifica si x e y son casi iguales; es

# decir si el valor absoluto de su diferencia es menor que una

# milésima. Por ejemplo,

# casiIguales(12.3457, 12.3459) == True

# casiIguales(12.3457, 12.3479) == False

def casiIguales(x: float, y: float) -> bool:

return abs(x - y) < 0.001

# La propiedad es

@given(st.floats(min_value=-100, max_value=100),

st.floats(min_value=-100, max_value=100),

st.floats(min_value=-100, max_value=100))

def test_prop_raices(a, b, c):

assume(abs(a) > 0.1)

xs = raices(a, b, c)

assume(xs)

[x1, x2] = xs

assert casiIguales(x1 + x2, -b / a)

assert casiIguales(x1 * x2, c / a)

# La comprobación es

# src> poetry run pytest -q raices_de_la_ecuacion_de_segundo_grado.py

# 1 passed in 0.35s

El código se encuentra en GitHub.

Número de raíces de la ecuación de segundo grado

PorJosé A. Alonso 9-septiembre-202214-diciembre-2022

Definir la función

   numeroDeRaices :: (Num t, Ord t) => t -> t -> t -> Int

1	numeroDeRaices :: (Num t, Ord t) => t -> t -> t -> Int

tal que (numeroDeRaices a b c) es el número de raíces reales de la ecuación $ax^2 + bx + c = 0$ . Por ejemplo,

   numeroDeRaices 2 0 3    ==  0
   numeroDeRaices 4 4 1    ==  1
   numeroDeRaices 5 23 12  ==  2

numeroDeRaices 2 0 3 == 0

numeroDeRaices 4 4 1 == 1

numeroDeRaices 5 23 12 == 2

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

numeroDeRaices :: (Num t, Ord t) => t -> t -> t -> Int
numeroDeRaices a b c | d < 0     = 0
                     | d == 0    = 1
                     | otherwise = 2
  where d = b^2-4*a*c

numeroDeRaices :: (Num t, Ord t) => t -> t -> t -> Int

numeroDeRaices a b c | d < 0 = 0

| d == 0 = 1

| otherwise = 2

where d = b^2-4*a*c

El código se encuentra en GitHub.

Soluciones en Python

def numeroDeRaices(a: float, b: float, c: float) -> float:
    d = b ** 2 - 4 * a * c
    if d < 0:
        return 0
    if d == 0:
        return 1
    return 2

def numeroDeRaices(a: float, b: float, c: float) -> float:

d = b ** 2 - 4 * a * c

if d < 0:

return 0

if d == 0:

return 1

return 2

El código se encuentra en GitHub.

Comentarios

En Haskell se usa un entorno local con where d = b^2-4*a*c y en Python se usa la asignación d = b ** 2 - 4 * a * c.

Mayor número con dos dígitos dados

PorJosé A. Alonso 8-septiembre-202214-diciembre-2022

Definir la función

   numeroMayor :: Int -> Int -> Int

1	numeroMayor :: Int -> Int -> Int

tal que (numeroMayor x y) es el mayor número de dos cifras que puede construirse con los dígitos x e y. Por ejemplo,

   numeroMayor 2 5 ==  52
   numeroMayor 5 2 ==  52

1 2	numeroMayor 2 5 == 52 numeroMayor 5 2 == 52

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

-- 1ª definición:
numeroMayor1 :: Int -> Int -> Int
numeroMayor1 x y = 10 * max x y + min x y

-- 2ª definición:
numeroMayor2 :: Int -> Int -> Int
numeroMayor2 x y | x > y     = 10*x+y
                 | otherwise = 10*y+x

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_numeroMayor :: Bool
prop_numeroMayor =
  and [numeroMayor1 x y == numeroMayor2 x y | x <- [0..9], y <- [0..9]]

-- La comprobación es
--    λ> prop_numeroMayor
--    True

-- 1ª definición:

numeroMayor1 :: Int -> Int -> Int

numeroMayor1 x y = 10 * max x y + min x y

-- 2ª definición:

numeroMayor2 :: Int -> Int -> Int

numeroMayor2 x y | x > y = 10*x+y

| otherwise = 10*y+x

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_numeroMayor :: Bool

prop_numeroMayor =

and [numeroMayor1 x y == numeroMayor2 x y | x <- [0..9], y <- [0..9]]

-- La comprobación es

-- λ> prop_numeroMayor

-- True

El código se encuentra en GitHub.

Soluciones en Python

# 1ª definición
def numeroMayor1(x: int, y: int) -> int:
    return 10 * max(x, y) + min(x, y)

# 2ª definición
def numeroMayor2(x: int, y: int) -> int:
    if x > y:
        return 10 * x + y
    return 10 * y + x

# La propiedad de equivalencia de las definiciones es
def test_equiv_numeroMayor():
    # type: () -> bool
    return all(numeroMayor1(x, y) == numeroMayor2(x, y)
               for x in range(10) for y in range(10))

# La comprobación es
#    >>> test_equiv_numeroMayor()
#    True

# 1ª definición

def numeroMayor1(x: int, y: int) -> int:

return 10 * max(x, y) + min(x, y)

# 2ª definición

def numeroMayor2(x: int, y: int) -> int:

if x > y:

return 10 * x + y

return 10 * y + x

# La propiedad de equivalencia de las definiciones es

def test_equiv_numeroMayor():

# type: () -> bool

return all(numeroMayor1(x, y) == numeroMayor2(x, y)

for x in range(10) for y in range(10))

# La comprobación es

# >>> test_equiv_numeroMayor()

# True

El código se encuentra en GitHub.

Permutación cíclica

PorJosé A. Alonso 7-septiembre-202214-diciembre-2022

Definir la función

   ciclo :: [a] -> [a]

1	ciclo :: [a] -> [a]

tal que (ciclo xs) es la lista obtenida permutando cíclicamente los elementos de la lista xs, pasando el último elemento al principio de la lista. Por ejemplo,

   ciclo [2,5,7,9]  == [9,2,5,7]
   ciclo []         == []
   ciclo [2]        == [2]

ciclo [2,5,7,9] == [9,2,5,7]

ciclo [] == []

ciclo [2] == [2]

Comprobar que la longitud es un invariante de la función ciclo; es decir, la longitud de (ciclo xs) es la misma que la de xs.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

ciclo :: [a] -> [a]
ciclo [] = []
ciclo xs = last xs : init xs

-- La propiedad es
prop_ciclo :: [Int] -> Bool
prop_ciclo xs = length (ciclo xs) == length xs

-- La comprobación es
--    λ> quickCheck prop_ciclo
--    +++ OK, passed 100 tests.

import Test.QuickCheck

ciclo :: [a] -> [a]

ciclo [] = []

ciclo xs = last xs : init xs

-- La propiedad es

prop_ciclo :: [Int] -> Bool

prop_ciclo xs = length (ciclo xs) == length xs

-- La comprobación es

-- λ> quickCheck prop_ciclo

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub

Soluciones en Python

from typing import TypeVar
from hypothesis import given, strategies as st

A = TypeVar('A')

def ciclo(xs: list[A]) -> list[A]:
    if xs:
        return [xs[-1]] + xs[:-1]
    return []

# La propiedad de es
@given(st.lists(st.integers()))
def test_equiv_ciclo(xs):
    assert len(ciclo(xs)) == len(xs)

# La comprobación es
#    src> poetry run pytest -q permutacion_ciclica.py
#    1 passed in 0.39s

from typing import TypeVar

from hypothesis import given, strategies as st

A = TypeVar('A')

def ciclo(xs: list[A]) -> list[A]:

if xs:

return [xs[-1]] + xs[:-1]

return []

# La propiedad de es

@given(st.lists(st.integers()))

def test_equiv_ciclo(xs):

assert len(ciclo(xs)) == len(xs)

# La comprobación es

# src> poetry run pytest -q permutacion_ciclica.py

# 1 passed in 0.39s

El código se encuentra en GitHub.

Distancia entre dos puntos

PorJosé A. Alonso 6-septiembre-202214-diciembre-2022

Definir la función

   distancia :: (Double,Double) -> (Double,Double) -> Double

1	distancia :: (Double,Double) -> (Double,Double) -> Double

tal que (distancia p1 p2) es la distancia entre los puntos p1 y p2. Por ejemplo,

   distancia (1,2) (4,6)  ==  5.0

1	distancia (1,2) (4,6) == 5.0

Comprobar con QuickCheck que se verifica la propiedad triangular de la distancia; es decir, dados tres puntos p1, p2 y p3, la distancia de p1 a p3 es menor o igual que la suma de la distancia de p1 a p2 y la de p2 a p3.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

distancia :: (Double,Double) -> (Double,Double) -> Double
distancia (x1,y1) (x2,y2) = sqrt((x1-x2)^2+(y1-y2)^2)

-- La propiedad es
prop_triangular :: (Double,Double) -> (Double,Double) -> (Double,Double)
                -> Property
prop_triangular p1 p2 p3 =
    all acotado [p1, p2, p3] ==>
    distancia p1 p3 <= distancia p1 p2 + distancia p2 p3
    where acotado (x, y) = abs x < cota && abs y < cota
          cota = 2^30

-- La comprobación es
--    ghci> quickCheck prop_triangular
--    +++ OK, passed 100 tests.

-- Nota: Por problemas de redondeo, la propiedad no se cumple en
-- general. Por ejemplo,
--    λ> p1 = (0, 9147936743096483)
--    λ> p2 = (0, 3)
--    λ> p3 = (0, 2)
--    λ> distancia p1 p3 <= distancia p1 p2 + distancia p2 p3
--    False
--    λ> distancia p1 p3
--    9.147936743096482e15
--    λ> distancia p1 p2 + distancia p2 p3
--    9.14793674309648e15

import Test.QuickCheck

distancia :: (Double,Double) -> (Double,Double) -> Double

distancia (x1,y1) (x2,y2) = sqrt((x1-x2)^2+(y1-y2)^2)

-- La propiedad es

prop_triangular :: (Double,Double) -> (Double,Double) -> (Double,Double)

-> Property

prop_triangular p1 p2 p3 =

all acotado [p1, p2, p3] ==>

distancia p1 p3 <= distancia p1 p2 + distancia p2 p3

where acotado (x, y) = abs x < cota && abs y < cota

cota = 2^30

-- La comprobación es

-- ghci> quickCheck prop_triangular

-- +++ OK, passed 100 tests.

-- Nota: Por problemas de redondeo, la propiedad no se cumple en

-- general. Por ejemplo,

-- λ> p1 = (0, 9147936743096483)

-- λ> p2 = (0, 3)

-- λ> p3 = (0, 2)

-- λ> distancia p1 p3 <= distancia p1 p2 + distancia p2 p3

-- False

-- λ> distancia p1 p3

-- 9.147936743096482e15

-- λ> distancia p1 p2 + distancia p2 p3

-- 9.14793674309648e15

El código se encuentra en GitHub.

Soluciones en Python

from math import sqrt
from hypothesis import given, strategies as st

def distancia(p1: tuple[float, float],
              p2: tuple[float, float]) -> float:
    (x1, y1) = p1
    (x2, y2) = p2
    return sqrt((x1-x2)**2+(y1-y2)**2)

# La propiedad es
cota = 2 ** 30

@given(st.tuples(st.integers(min_value=0, max_value=cota),
                 st.integers(min_value=0, max_value=cota)),
       st.tuples(st.integers(min_value=0, max_value=cota),
                 st.integers(min_value=0, max_value=cota)),
       st.tuples(st.integers(min_value=0, max_value=cota),
                 st.integers(min_value=0, max_value=cota)))
def test_triangular(p1, p2, p3):
    assert distancia(p1, p3) <= distancia(p1, p2) + distancia(p2, p3)

# La comprobación es
#    src> poetry run pytest -q distancia_entre_dos_puntos.py
#    1 passed in 0.38s

# Nota: Por problemas de redondeo, la propiedad no se cumple en
# general. Por ejemplo,
#    λ> p1 = (0, 9147936743096483)
#    λ> p2 = (0, 3)
#    λ> p3 = (0, 2)
#    λ> distancia(p1, p3) <= distancia(p1, p2) + distancia (p2. p3)
#    False
#    λ> distancia(p1, p3)
#    9147936743096482.0
#    λ> distancia(p1, p2) + distancia(p2, p3)
#    9147936743096480.05

from math import sqrt

from hypothesis import given, strategies as st

def distancia(p1: tuple[float, float],

p2: tuple[float, float]) -> float:

(x1, y1) = p1

(x2, y2) = p2

return sqrt((x1-x2)**2+(y1-y2)**2)

# La propiedad es

cota = 2 ** 30

@given(st.tuples(st.integers(min_value=0, max_value=cota),

st.integers(min_value=0, max_value=cota)),

st.tuples(st.integers(min_value=0, max_value=cota),

st.integers(min_value=0, max_value=cota)),

st.tuples(st.integers(min_value=0, max_value=cota),

st.integers(min_value=0, max_value=cota)))

def test_triangular(p1, p2, p3):

assert distancia(p1, p3) <= distancia(p1, p2) + distancia(p2, p3)

# La comprobación es

# src> poetry run pytest -q distancia_entre_dos_puntos.py

# 1 passed in 0.38s

# Nota: Por problemas de redondeo, la propiedad no se cumple en

# general. Por ejemplo,

# λ> p1 = (0, 9147936743096483)

# λ> p2 = (0, 3)

# λ> p3 = (0, 2)

# λ> distancia(p1, p3) <= distancia(p1, p2) + distancia (p2. p3)

# False

# λ> distancia(p1, p3)

# 9147936743096482.0

# λ> distancia(p1, p2) + distancia(p2, p3)

# 9147936743096480.05

El código se encuentra en GitHub.

Comentarios

La raíz cuadrada de x se escribe
- en Haskell, como sqrt x y
- en Python, como sqrt(x) y hay que importarla del módulo math.

Intercambio de componentes de un par

PorJosé A. Alonso 5-septiembre-202214-diciembre-2022

Definir la función

   intercambia :: (a,b) -> (b,a)

1	intercambia :: (a,b) -> (b,a)

tal que (intercambia p) es el punto obtenido intercambiando las coordenadas del punto p. Por ejemplo,

   intercambia (2,5)  ==  (5,2)
   intercambia (5,2)  ==  (2,5)

1 2	intercambia (2,5) == (5,2) intercambia (5,2) == (2,5)

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

intercambia :: (a,b) -> (b,a)
intercambia (x,y) = (y,x)

1 2	intercambia :: (a,b) -> (b,a) intercambia (x,y) = (y,x)

El código se encuentra en GitHub.

Soluciones en Python

from typing import TypeVar
from hypothesis import given, strategies as st

A = TypeVar('A')
B = TypeVar('B')

def intercambia(p: tuple[A, B]) -> tuple[B, A]:
    (x, y) = p
    return (y, x)

# La propiedad de es
@given(st.tuples(st.integers(), st.integers()))
def test_equiv_intercambia(p):
    assert intercambia(intercambia(p)) == p

# La comprobación es
#    src> poetry run pytest -q intercambio_de_componentes_de_un_par.py
#    1 passed in 0.15s

from typing import TypeVar

from hypothesis import given, strategies as st

A = TypeVar('A')

B = TypeVar('B')

def intercambia(p: tuple[A, B]) -> tuple[B, A]:

(x, y) = p

return (y, x)

# La propiedad de es

@given(st.tuples(st.integers(), st.integers()))

def test_equiv_intercambia(p):

assert intercambia(intercambia(p)) == p

# La comprobación es

# src> poetry run pytest -q intercambio_de_componentes_de_un_par.py

# 1 passed in 0.15s

El código se encuentra en GitHub.

Comentarios

En Haskell se pone el patrón en los argumentos y en Python hay que extraerlos mediante un asignación.

Mayor rectángulo

PorJosé A. Alonso 2-septiembre-202214-diciembre-2022

Las dimensiones de los rectángulos puede representarse por pares; por ejemplo, (5,3) representa a un rectángulo de base 5 y altura 3.

Definir la función

   mayorRectangulo :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a)

1	mayorRectangulo :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a)

tal que (mayorRectangulo r1 r2) es el rectángulo de mayor área entre r1 y r2. Por ejemplo,

   mayorRectangulo (4,6) (3,7)  ==  (4,6)
   mayorRectangulo (4,6) (3,8)  ==  (4,6)
   mayorRectangulo (4,6) (3,9)  ==  (3,9)

mayorRectangulo (4,6) (3,7) == (4,6)

mayorRectangulo (4,6) (3,8) == (4,6)

mayorRectangulo (4,6) (3,9) == (3,9)

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

mayorRectangulo :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a)
mayorRectangulo (a,b) (c,d)
  | a*b >= c*d = (a,b)
  | otherwise  = (c,d)

mayorRectangulo :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a)

mayorRectangulo (a,b) (c,d)

| a*b >= c*d = (a,b)

| otherwise = (c,d)

El código se encuentra en GitHub.

Soluciones en Python

def mayorRectangulo(r1: tuple[float, float],
                    r2: tuple[float, float]) -> tuple[float, float]:
    (a, b) = r1
    (c, d) = r2
    if a*b >= c*d:
        return (a, b)
    return (c, d)

def mayorRectangulo(r1: tuple[float, float],

r2: tuple[float, float]) -> tuple[float, float]:

(a, b) = r1

(c, d) = r2

if a*b >= c*d:

return (a, b)

return (c, d)

El código se encuentra en GitHub.

Disyunción excluyente

PorJosé A. Alonso 1-septiembre-202214-diciembre-2022

La disyunción excluyente de dos fórmulas se verifica si una es verdadera y la otra es falsa. Su tabla de verdad es

   x     | y     | xor x y
   ------+-------+---------
   True  | True  | False
   True  | False | True
   False | True  | True
   False | False | False

x | y | xor x y

------+-------+---------

True | True | False

True | False | True

False | True | True

False | False | False

Definir la función

   xor :: Bool -> Bool -> Bool

1	xor :: Bool -> Bool -> Bool

tal que (xor x y) es la disyunción excluyente de x e y. Por ejemplo,

   xor True  True  == False
   xor True  False == True
   xor False True  == True
   xor False False == False

xor True True == False

xor True False == True

xor False True == True

xor False False == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import Test.QuickCheck

-- 1ª solución
xor1 :: Bool -> Bool -> Bool
xor1 True  True  = False
xor1 True  False = True
xor1 False True  = True
xor1 False False = False

-- 2ª solución
xor2 :: Bool -> Bool -> Bool
xor2 True  y = not y
xor2 False y = y

-- 3ª solución:
xor3 :: Bool -> Bool -> Bool
xor3 x y = (x || y) && not (x && y)

-- 4ª solución:
xor4 :: Bool -> Bool -> Bool
xor4 x y = (x && not y) || (y && not x)

-- 5ª solución:
xor5 :: Bool -> Bool -> Bool
xor5 x y = x /= y

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_xor :: Bool -> Bool -> Bool
prop_xor x y =
  all (== xor1 x y)
      [xor2 x y,
       xor3 x y,
       xor4 x y,
       xor5 x y]

-- La comprobación es
--    λ> quickCheck prop_xor
--    +++ OK, passed 100 tests.

import Test.QuickCheck

-- 1ª solución

xor1 :: Bool -> Bool -> Bool

xor1 True True = False

xor1 True False = True

xor1 False True = True

xor1 False False = False

-- 2ª solución

xor2 :: Bool -> Bool -> Bool

xor2 True y = not y

xor2 False y = y

-- 3ª solución:

xor3 :: Bool -> Bool -> Bool

xor3 x y = (x || y) && not (x && y)

-- 4ª solución:

xor4 :: Bool -> Bool -> Bool

xor4 x y = (x && not y) || (y && not x)

-- 5ª solución:

xor5 :: Bool -> Bool -> Bool

xor5 x y = x /= y

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_xor :: Bool -> Bool -> Bool

prop_xor x y =

all (== xor1 x y)

[xor2 x y,

xor3 x y,

xor4 x y,

xor5 x y]

-- La comprobación es

-- λ> quickCheck prop_xor

-- +++ OK, passed 100 tests.

El código se encuentra en GitHub.

Soluciones en Python

from hypothesis import given, strategies as st

# 1ª solución
def xor1(x, y):
    match x, y:
        case True,  True: return False
        case True,  False: return True
        case False, True: return True
        case False, False: return False

# 2ª solución
def xor2(x: bool, y: bool) -> bool:
    if x:
        return not y
    return y

# 3ª solución
def xor3(x: bool, y: bool) -> bool:
    return (x or y) and not(x and y)

# 4ª solución
def xor4(x: bool, y: bool) -> bool:
    return (x and not y) or (y and not x)

# 5ª solución
def xor5(x: bool, y: bool) -> bool:
    return x != y

# La propiedad de equivalencia es
@given(st.booleans(), st.booleans())
def test_equiv_xor(x, y):
    assert xor1(x, y) == xor2(x, y) == xor3(x, y) == xor4(x, y) == xor5(x, y)

# La comprobación es
#    src> poetry run pytest -q disyuncion_excluyente.py
#    1 passed in 0.11s

from hypothesis import given, strategies as st

# 1ª solución

def xor1(x, y):

match x, y:

case True, True: return False

case True, False: return True

case False, True: return True

case False, False: return False

# 2ª solución

def xor2(x: bool, y: bool) -> bool:

if x:

return not y

return y

# 3ª solución

def xor3(x: bool, y: bool) -> bool:

return (x or y) and not(x and y)

# 4ª solución

def xor4(x: bool, y: bool) -> bool:

return (x and not y) or (y and not x)

# 5ª solución

def xor5(x: bool, y: bool) -> bool:

return x != y

# La propiedad de equivalencia es

@given(st.booleans(), st.booleans())

def test_equiv_xor(x, y):

assert xor1(x, y) == xor2(x, y) == xor3(x, y) == xor4(x, y) == xor5(x, y)

# La comprobación es

# src> poetry run pytest -q disyuncion_excluyente.py

# 1 passed in 0.11s

El código se encuentra en GitHub.

Comentarios

La negación de x se escribe igual en Haskell y Python; not x
La disyunción de x e y se escribe
- en Haskell, como x || y y
- en Python, como x or y.

Meses: septiembre 2022

Triángulo aritmético

Suma de cuadrados menos cuadrado de la suma

Suma de los cuadrados de los primeros números naturales

Suma de los primeros números naturales

Números libres de cuadrados

Divisores primos

Divisores de un número

Diferencia conjuntista de listas

Intersección conjuntista de listas

Unión conjuntista de listas

Igualdad de conjuntos

Reconocimiento de subconjunto

Números racionales

Intersección de intervalos cerrados

Fórmula de Herón para el área de un triángulo

Raíces de la ecuación de segundo grado

Número de raíces de la ecuación de segundo grado

Mayor número con dos dígitos dados

Permutación cíclica

Distancia entre dos puntos

Intercambio de componentes de un par

Mayor rectángulo

Disyunción excluyente

Entradas recientes

Buscar

Correo electrónico