octubre 2022 – Página 2

Base de datos de actividades

PorJosé A. Alonso 24-octubre-202214-diciembre-2022

Las bases de datos sobre actividades de personas pueden representarse mediante listas de elementos de la forma (a,b,c,d), donde a es el nombre de la persona, b su actividad, c su fecha de nacimiento y d la de su fallecimiento. Un ejemplo es la siguiente que usaremos a lo largo de este ejercicio,

   personas :: [(String,String,Int,Int)]
   personas = [("Cervantes","Literatura",1547,1616),
               ("Velazquez","Pintura",1599,1660),
               ("Picasso","Pintura",1881,1973),
               ("Beethoven","Musica",1770,1823),
               ("Poincare","Ciencia",1854,1912),
               ("Quevedo","Literatura",1580,1654),
               ("Goya","Pintura",1746,1828),
               ("Einstein","Ciencia",1879,1955),
               ("Mozart","Musica",1756,1791),
               ("Botticelli","Pintura",1445,1510),
               ("Borromini","Arquitectura",1599,1667),
               ("Bach","Musica",1685,1750)]

personas :: [(String,String,Int,Int)]

personas = [("Cervantes","Literatura",1547,1616),

("Velazquez","Pintura",1599,1660),

("Picasso","Pintura",1881,1973),

("Beethoven","Musica",1770,1823),

("Poincare","Ciencia",1854,1912),

("Quevedo","Literatura",1580,1654),

("Goya","Pintura",1746,1828),

("Einstein","Ciencia",1879,1955),

("Mozart","Musica",1756,1791),

("Botticelli","Pintura",1445,1510),

("Borromini","Arquitectura",1599,1667),

("Bach","Musica",1685,1750)]

Definir las funciones

   nombres   :: [(String,String,Int,Int)] -> [String]
   musicos   :: [(String,String,Int,Int)] -> [String]
   seleccion :: [(String,String,Int,Int)] -> String -> [String]
   musicos'  :: [(String,String,Int,Int)] -> [String]
   vivas     :: [(String,String,Int,Int)] -> Int -> [String]

nombres :: [(String,String,Int,Int)] -> [String]

musicos :: [(String,String,Int,Int)] -> [String]

seleccion :: [(String,String,Int,Int)] -> String -> [String]

musicos' :: [(String,String,Int,Int)] -> [String]

vivas :: [(String,String,Int,Int)] -> Int -> [String]

tales que

nombres bd es la lista de los nombres de las personas de la base de datos bd. Por ejemplo,

     λ> nombres personas
     ["Cervantes","Velazquez","Picasso","Beethoven","Poincare",
      "Quevedo","Goya","Einstein","Mozart","Botticelli","Borromini",
      "Bach"]

λ> nombres personas

["Cervantes","Velazquez","Picasso","Beethoven","Poincare",

"Quevedo","Goya","Einstein","Mozart","Botticelli","Borromini",

"Bach"]

musicos bd es la lista de los nombres de los músicos de la base de datos bd. Por ejemplo,

     musicos personas  ==  ["Beethoven","Mozart","Bach"]

1	musicos personas == ["Beethoven","Mozart","Bach"]

seleccion bd m es la lista de los nombres de las personas de la base de datos bd cuya actividad es m. Por ejemplo,

     λ> seleccion personas "Pintura"
     ["Velazquez","Picasso","Goya","Botticelli"]
     λ> seleccion personas "Musica"
     ["Beethoven","Mozart","Bach"]

λ> seleccion personas "Pintura"

["Velazquez","Picasso","Goya","Botticelli"]

λ> seleccion personas "Musica"

["Beethoven","Mozart","Bach"]

musicos' bd es la lista de los nombres de los músicos de la base de datos bd. Por ejemplo,

     musicos' personas  ==  ["Beethoven","Mozart","Bach"]

1	musicos' personas == ["Beethoven","Mozart","Bach"]

vivas bd a es la lista de los nombres de las personas de la base de datos bd que estaban vivas en el año a. Por ejemplo,

     λ> vivas personas 1600
     ["Cervantes","Velazquez","Quevedo","Borromini"]

1 2	λ> vivas personas 1600 ["Cervantes","Velazquez","Quevedo","Borromini"]

Soluciones

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

Soluciones en Haskell

personas :: [(String,String,Int,Int)]
personas = [("Cervantes","Literatura",1547,1616),
            ("Velazquez","Pintura",1599,1660),
            ("Picasso","Pintura",1881,1973),
            ("Beethoven","Musica",1770,1823),
            ("Poincare","Ciencia",1854,1912),
            ("Quevedo","Literatura",1580,1654),
            ("Goya","Pintura",1746,1828),
            ("Einstein","Ciencia",1879,1955),
            ("Mozart","Musica",1756,1791),
            ("Botticelli","Pintura",1445,1510),
            ("Borromini","Arquitectura",1599,1667),
            ("Bach","Musica",1685,1750)]

nombres :: [(String,String,Int,Int)] -> [String]
nombres bd = [x | (x,_,_,_) <- bd]

musicos :: [(String,String,Int,Int)] -> [String]
musicos bd = [x | (x,"Musica",_,_) <- bd]

seleccion :: [(String,String,Int,Int)] -> String -> [String]
seleccion bd m = [ x | (x,m',_,_) <- bd, m == m' ]

musicos' :: [(String,String,Int,Int)] -> [String]
musicos' bd = seleccion bd "Musica"

vivas :: [(String,String,Int,Int)] -> Int -> [String]
vivas bd a = [x | (x,_,a1,a2) <- bd, a1 <= a, a <= a2]

personas :: [(String,String,Int,Int)]

personas = [("Cervantes","Literatura",1547,1616),

("Velazquez","Pintura",1599,1660),

("Picasso","Pintura",1881,1973),

("Beethoven","Musica",1770,1823),

("Poincare","Ciencia",1854,1912),

("Quevedo","Literatura",1580,1654),

("Goya","Pintura",1746,1828),

("Einstein","Ciencia",1879,1955),

("Mozart","Musica",1756,1791),

("Botticelli","Pintura",1445,1510),

("Borromini","Arquitectura",1599,1667),

("Bach","Musica",1685,1750)]

nombres :: [(String,String,Int,Int)] -> [String]

nombres bd = [x | (x,_,_,_) <- bd]

musicos :: [(String,String,Int,Int)] -> [String]

musicos bd = [x | (x,"Musica",_,_) <- bd]

seleccion :: [(String,String,Int,Int)] -> String -> [String]

seleccion bd m = [ x | (x,m',_,_) <- bd, m == m' ]

musicos' :: [(String,String,Int,Int)] -> [String]

musicos' bd = seleccion bd "Musica"

vivas :: [(String,String,Int,Int)] -> Int -> [String]

vivas bd a = [x | (x,_,a1,a2) <- bd, a1 <= a, a <= a2]

El código se encuentra en GitHub.

Soluciones en Python

BD = list[tuple[str, str, int, int]]

personas: BD = [
    ("Cervantes", "Literatura", 1547, 1616),
    ("Velazquez", "Pintura", 1599, 1660),
    ("Picasso", "Pintura", 1881, 1973),
    ("Beethoven", "Musica", 1770, 1823),
    ("Poincare", "Ciencia", 1854, 1912),
    ("Quevedo", "Literatura", 1580, 1654),
    ("Goya", "Pintura", 1746, 1828),
    ("Einstein", "Ciencia", 1879, 1955),
    ("Mozart", "Musica", 1756, 1791),
    ("Botticelli", "Pintura", 1445, 1510),
    ("Borromini", "Arquitectura", 1599, 1667),
    ("Bach", "Musica", 1685, 1750)]

def nombres(bd: BD) -> list[str]:
    return [p[0] for p in bd]

def musicos(bd: BD) -> list[str]:
    return [p[0] for p in bd if p[1] == "Musica"]

def seleccion(bd: BD, m: str) -> list[str]:
    return [p[0] for p in bd if p[1] == m]

def musicos2(bd: BD) -> list[str]:
    return seleccion(bd, "Musica")

def vivas(bd: BD, a: int) -> list[str]:
    return [p[0] for p in bd if p[2] <= a <= p[3]]

BD = list[tuple[str, str, int, int]]

personas: BD = [

("Cervantes", "Literatura", 1547, 1616),

("Velazquez", "Pintura", 1599, 1660),

("Picasso", "Pintura", 1881, 1973),

("Beethoven", "Musica", 1770, 1823),

("Poincare", "Ciencia", 1854, 1912),

("Quevedo", "Literatura", 1580, 1654),

("Goya", "Pintura", 1746, 1828),

("Einstein", "Ciencia", 1879, 1955),

("Mozart", "Musica", 1756, 1791),

("Botticelli", "Pintura", 1445, 1510),

("Borromini", "Arquitectura", 1599, 1667),

("Bach", "Musica", 1685, 1750)]

def nombres(bd: BD) -> list[str]:

return [p[0] for p in bd]

def musicos(bd: BD) -> list[str]:

return [p[0] for p in bd if p[1] == "Musica"]

def seleccion(bd: BD, m: str) -> list[str]:

return [p[0] for p in bd if p[1] == m]

def musicos2(bd: BD) -> list[str]:

return seleccion(bd, "Musica")

def vivas(bd: BD, a: int) -> list[str]:

return [p[0] for p in bd if p[2] <= a <= p[3]]

El código se encuentra en GitHub.

Representación densa de polinomios

PorJosé A. Alonso 21-octubre-202214-diciembre-2022

Los polinomios pueden representarse de forma dispersa o densa. Por ejemplo, el polinomio 6x^4-5x^2+4x-7 se puede representar de forma dispersa por [6,0,-5,4,-7] y de forma densa por [(4,6),(2,-5),(1,4),(0,-7)].

Definir la función

   densa :: [Int] -> [(Int,Int)]

1	densa :: [Int] -> [(Int,Int)]

tal que densa xs es la representación densa del polinomio cuya representación dispersa es xs. Por ejemplo,

   densa [6,0,-5,4,-7]  ==  [(4,6),(2,-5),(1,4),(0,-7)]
   densa [6,0,0,3,0,4]  ==  [(5,6),(2,3),(0,4)]
   densa [0]            ==  [(0,0)]

densa [6,0,-5,4,-7] == [(4,6),(2,-5),(1,4),(0,-7)]

densa [6,0,0,3,0,4] == [(5,6),(2,3),(0,4)]

densa [0] == [(0,0)]

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

densa1 :: [Int] -> [(Int,Int)]
densa1 xs =
  [(x,y) | (x,y) <- zip [n-1,n-2..1] xs, y /= 0]
  ++ [(0, last xs)]
  where n = length xs

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

densa2 :: [Int] -> [(Int,Int)]
densa2 xs =
  filter (\ (_,y) -> y /= 0) (zip [n-1,n-2..1] xs)
  ++ [(0, last xs)]
  where n = length xs

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

densa3 :: [Int] -> [(Int,Int)]
densa3 xs = filter ((/= 0) . snd) (zip [n-1,n-2..1] xs)
  ++ [(0, last xs)]
  where n = length xs

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

densa4 :: [Int] -> [(Int,Int)]
densa4 xs = aux xs (length xs - 1)
  where aux [y] 0 = [(0, y)]
        aux (y:ys) n | y == 0    = aux ys (n-1)
                     | otherwise = (n,y) : aux ys (n-1)

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

-- La propiedad es
prop_densa :: NonEmptyList Int -> Bool
prop_densa (NonEmpty xs) =
  all (== densa1 xs)
      [densa2 xs,
       densa3 xs,
       densa4 xs]

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

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

-- La comparación es
--    λ> last (densa1 [1..2*10^6])
--    (0,2000000)
--    (0.95 secs, 880,569,400 bytes)
--    λ> last (densa2 [1..2*10^6])
--    (0,2000000)
--    (0.52 secs, 800,569,432 bytes)
--    λ> last (densa3 [1..2*10^6])
--    (0,2000000)
--    (0.53 secs, 752,569,552 bytes)
--    λ> last (densa4 [1..2*10^6])
--    (0,2000000)
--    (3.05 secs, 1,267,842,032 bytes)
--
--    λ> last (densa1 [1..10^7])
--    (0,10000000)
--    (5.43 secs, 4,400,570,128 bytes)
--    λ> last (densa2 [1..10^7])
--    (0,10000000)
--    (3.03 secs, 4,000,570,160 bytes)
--    λ> last (densa3 [1..10^7])
--    (0,10000000)
--    (2.34 secs, 3,760,570,280 bytes)

import Test.QuickCheck

-- 1ª solución

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

densa1 :: [Int] -> [(Int,Int)]

densa1 xs =

[(x,y) | (x,y) <- zip [n-1,n-2..1] xs, y /= 0]

++ [(0, last xs)]

where n = length xs

-- 2ª solución

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

densa2 :: [Int] -> [(Int,Int)]

densa2 xs =

filter (\ (_,y) -> y /= 0) (zip [n-1,n-2..1] xs)

++ [(0, last xs)]

where n = length xs

-- 3ª solución

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

densa3 :: [Int] -> [(Int,Int)]

densa3 xs = filter ((/= 0) . snd) (zip [n-1,n-2..1] xs)

++ [(0, last xs)]

where n = length xs

-- 4ª solución

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

densa4 :: [Int] -> [(Int,Int)]

densa4 xs = aux xs (length xs - 1)

where aux [y] 0 = [(0, y)]

aux (y:ys) n | y == 0 = aux ys (n-1)

| otherwise = (n,y) : aux ys (n-1)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_densa :: NonEmptyList Int -> Bool

prop_densa (NonEmpty xs) =

all (== densa1 xs)

[densa2 xs,

densa3 xs,

densa4 xs]

-- La comprobación es

-- λ> quickCheck prop_densa

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> last (densa1 [1..2*10^6])

-- (0,2000000)

-- (0.95 secs, 880,569,400 bytes)

-- λ> last (densa2 [1..2*10^6])

-- (0,2000000)

-- (0.52 secs, 800,569,432 bytes)

-- λ> last (densa3 [1..2*10^6])

-- (0,2000000)

-- (0.53 secs, 752,569,552 bytes)

-- λ> last (densa4 [1..2*10^6])

-- (0,2000000)

-- (3.05 secs, 1,267,842,032 bytes)

-- λ> last (densa1 [1..10^7])

-- (0,10000000)

-- (5.43 secs, 4,400,570,128 bytes)

-- λ> last (densa2 [1..10^7])

-- (0,10000000)

-- (3.03 secs, 4,000,570,160 bytes)

-- λ> last (densa3 [1..10^7])

-- (0,10000000)

-- (2.34 secs, 3,760,570,280 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

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

def densa1(xs: list[int]) -> list[tuple[int, int]]:
    n = len(xs)
    return [(x, y)
            for (x, y) in zip(range(n-1, 0, -1), xs)
            if y != 0] + [(0, xs[-1])]

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

def densa2(xs: list[int]) -> list[tuple[int, int]]:
    n = len(xs)
    return list(filter(lambda p: p[1] != 0,
                       zip(range(n-1, 0, -1), xs))) + [(0, xs[-1])]

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

def densa3(xs: list[int]) -> list[tuple[int, int]]:
    def aux(ys: list[int], n: int) -> list[tuple[int, int]]:
        if n == 0:
            return [(0, ys[0])]
        if ys[0] == 0:
            return aux(ys[1:], n-1)
        return [(n, ys[0])] + aux(ys[1:], n-1)

    return aux(xs, len(xs) - 1)

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

# La propiedad es
@given(st.lists(st.integers(), min_size=1))
def test_densa(xs: list[int]) -> None:
    r = densa1(xs)
    assert densa2(xs) == r
    assert densa3(xs) == r

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

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

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

# La comparación es
#    >>> tiempo('densa1(range(1, 10**4))')
#    0.00 segundos
#    >>> tiempo('densa2(range(1, 10**4))')
#    0.00 segundos
#    >>> tiempo('densa3(range(1, 10**4))')
#    0.25 segundos
#
#    >>> tiempo('densa1(range(1, 10**7))')
#    1.87 segundos
#    >>> tiempo('densa2(range(1, 10**7))')
#    2.15 segundos

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución

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

def densa1(xs: list[int]) -> list[tuple[int, int]]:

n = len(xs)

return [(x, y)

for (x, y) in zip(range(n-1, 0, -1), xs)

if y != 0] + [(0, xs[-1])]

# 2ª solución

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

def densa2(xs: list[int]) -> list[tuple[int, int]]:

n = len(xs)

return list(filter(lambda p: p[1] != 0,

zip(range(n-1, 0, -1), xs))) + [(0, xs[-1])]

# 3ª solución

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

def densa3(xs: list[int]) -> list[tuple[int, int]]:

def aux(ys: list[int], n: int) -> list[tuple[int, int]]:

if n == 0:

return [(0, ys[0])]

if ys[0] == 0:

return aux(ys[1:], n-1)

return [(n, ys[0])] + aux(ys[1:], n-1)

return aux(xs, len(xs) - 1)

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.integers(), min_size=1))

def test_densa(xs: list[int]) -> None:

r = densa1(xs)

assert densa2(xs) == r

assert densa3(xs) == r

# La comprobación es

# src> poetry run pytest -q representacion_densa_de_polinomios.py

# 1 passed in 0.27s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

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

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

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

# La comparación es

# >>> tiempo('densa1(range(1, 10**4))')

# 0.00 segundos

# >>> tiempo('densa2(range(1, 10**4))')

# 0.00 segundos

# >>> tiempo('densa3(range(1, 10**4))')

# 0.25 segundos

# >>> tiempo('densa1(range(1, 10**7))')

# 1.87 segundos

# >>> tiempo('densa2(range(1, 10**7))')

# 2.15 segundos

El código se encuentra en GitHub

Suma de elementos consecutivos

PorJosé A. Alonso 20-octubre-202214-diciembre-2022

Definir la función

   sumaConsecutivos :: [Integer] -> [Integer]

1	sumaConsecutivos :: [Integer] -> [Integer]

tal que sumaConsecutivos xs es la suma de los pares de elementos consecutivos de la lista xs. Por ejemplo,

   sumaConsecutivos [3,1,5,2]  ==  [4,6,7]
   sumaConsecutivos [3]        ==  []
   last (sumaConsecutivos [1..10^8])  ==  199999999

sumaConsecutivos [3,1,5,2] == [4,6,7]

sumaConsecutivos [3] == []

last (sumaConsecutivos [1..10^8]) == 199999999

Soluciones

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

Soluciones en Haskell

import Test.QuickCheck

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

sumaConsecutivos1 :: [Integer] -> [Integer]
sumaConsecutivos1 xs = [x+y | (x,y) <- zip xs (tail xs)]

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

sumaConsecutivos2 :: [Integer] -> [Integer]
sumaConsecutivos2 xs = zipWith (+) xs (tail xs)

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

sumaConsecutivos3 :: [Integer] -> [Integer]
sumaConsecutivos3 = zipWith (+) <*> tail

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

sumaConsecutivos4 :: [Integer] -> [Integer]
sumaConsecutivos4 (x:y:zs) = x+y : sumaConsecutivos4 (y:zs)
sumaConsecutivos4 _        = []

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

-- La propiedad es
prop_sumaConsecutivos :: [Integer] -> Bool
prop_sumaConsecutivos xs =
  all (== sumaConsecutivos1 xs)
      [sumaConsecutivos2 xs,
       sumaConsecutivos3 xs,
       sumaConsecutivos4 xs]

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

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

-- La comparación es
--    λ> last (sumaConsecutivos1 [1..8*10^6])
--    15999999
--    (1.98 secs, 2,176,566,784 bytes)
--    λ> last (sumaConsecutivos2 [1..8*10^6])
--    15999999
--    (0.19 secs, 1,408,566,840 bytes)
--    λ> last (sumaConsecutivos3 [1..8*10^6])
--    15999999
--    (0.19 secs, 1,408,566,936 bytes)
--    λ> last (sumaConsecutivos4 [1..8*10^6])
--    15999999
--    (2.78 secs, 2,560,566,832 bytes)

import Test.QuickCheck

-- 1ª solución

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

sumaConsecutivos1 :: [Integer] -> [Integer]

sumaConsecutivos1 xs = [x+y | (x,y) <- zip xs (tail xs)]

-- 2ª solución

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

sumaConsecutivos2 :: [Integer] -> [Integer]

sumaConsecutivos2 xs = zipWith (+) xs (tail xs)

-- 3ª solución

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

sumaConsecutivos3 :: [Integer] -> [Integer]

sumaConsecutivos3 = zipWith (+) <*> tail

-- 4ª solución

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

sumaConsecutivos4 :: [Integer] -> [Integer]

sumaConsecutivos4 (x:y:zs) = x+y : sumaConsecutivos4 (y:zs)

sumaConsecutivos4 _ = []

-- Comprobación de equivalencia

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

-- La propiedad es

prop_sumaConsecutivos :: [Integer] -> Bool

prop_sumaConsecutivos xs =

all (== sumaConsecutivos1 xs)

[sumaConsecutivos2 xs,

sumaConsecutivos3 xs,

sumaConsecutivos4 xs]

-- La comprobación es

-- λ> quickCheck prop_sumaConsecutivos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> last (sumaConsecutivos1 [1..8*10^6])

-- 15999999

-- (1.98 secs, 2,176,566,784 bytes)

-- λ> last (sumaConsecutivos2 [1..8*10^6])

-- 15999999

-- (0.19 secs, 1,408,566,840 bytes)

-- λ> last (sumaConsecutivos3 [1..8*10^6])

-- 15999999

-- (0.19 secs, 1,408,566,936 bytes)

-- λ> last (sumaConsecutivos4 [1..8*10^6])

-- 15999999

-- (2.78 secs, 2,560,566,832 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from operator import add
from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

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

def sumaConsecutivos1(xs: list[int]) -> list[int]:
    return [x + y for (x, y) in zip(xs, xs[1:])]

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

def sumaConsecutivos2(xs: list[int]) -> list[int]:
    return list(map(add, xs, xs[1:]))

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

def sumaConsecutivos3(xs: list[int]) -> list[int]:
    if len(xs) >= 2:
        return [xs[0] + xs[1]] + sumaConsecutivos3(xs[1:])
    return []

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

# La propiedad es
@given(st.lists(st.integers(min_value=1, max_value=100)))
def test_sumaConsecutivos(xs: list[int]) -> None:
    r = sumaConsecutivos1(xs)
    assert sumaConsecutivos2(xs) == r
    assert sumaConsecutivos3(xs) == r

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

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

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

# La comparación es
#    >>> tiempo('sumaConsecutivos1(range(1, 10**4))')
#    0.00 segundos
#    >>> tiempo('sumaConsecutivos2(range(1, 10**4))')
#    0.00 segundos
#    >>> tiempo('sumaConsecutivos3(range(1, 10**4))')
#    0.18 segundos
#
#    >>> tiempo('sumaConsecutivos1(range(1, 10**8))')
#    8.34 segundos
#    >>> tiempo('sumaConsecutivos2(range(1, 10**8))')
#    6.28 segundos

from operator import add

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

# 1ª solución

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

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

return [x + y for (x, y) in zip(xs, xs[1:])]

# 2ª solución

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

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

return list(map(add, xs, xs[1:]))

# 3ª solución

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

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

if len(xs) >= 2:

return [xs[0] + xs[1]] + sumaConsecutivos3(xs[1:])

return []

# Comprobación de equivalencia

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

# La propiedad es

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

def test_sumaConsecutivos(xs: list[int]) -> None:

r = sumaConsecutivos1(xs)

assert sumaConsecutivos2(xs) == r

assert sumaConsecutivos3(xs) == r

# La comprobación es

# src> poetry run pytest -q suma_elementos_consecutivos.py

# 1 passed in 0.26s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

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

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

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

# La comparación es

# >>> tiempo('sumaConsecutivos1(range(1, 10**4))')

# 0.00 segundos

# >>> tiempo('sumaConsecutivos2(range(1, 10**4))')

# 0.00 segundos

# >>> tiempo('sumaConsecutivos3(range(1, 10**4))')

# 0.18 segundos

# >>> tiempo('sumaConsecutivos1(range(1, 10**8))')

# 8.34 segundos

# >>> tiempo('sumaConsecutivos2(range(1, 10**8))')

# 6.28 segundos

El código se encuentra en GitHub.

Producto escalar

PorJosé A. Alonso 19-octubre-202214-diciembre-2022

El producto escalar de dos listas de enteros xs y ys de longitud n viene dado por la suma de los productos de los elementos correspondientes.

Definir la función

   productoEscalar :: [Integer] -> [Integer] -> Integer

1	productoEscalar :: [Integer] -> [Integer] -> Integer

tal que productoEscalar xs ys es el producto escalar de las listas xs e ys. Por ejemplo,

   productoEscalar [1,2,3] [4,5,6]  ==  32

1	productoEscalar [1,2,3] [4,5,6] == 32

Soluciones

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

Soluciones en Haskell

import Numeric.LinearAlgebra ((<.>), vector)
import Test.QuickCheck (quickCheck)

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

productoEscalar1 :: [Integer] -> [Integer] -> Integer
productoEscalar1 xs ys = sum [x*y | (x,y) <- zip xs ys]

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

productoEscalar2 :: [Integer] -> [Integer] -> Integer
productoEscalar2 xs ys = sum (zipWith (*) xs ys)

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

productoEscalar3 :: [Integer] -> [Integer] -> Integer
productoEscalar3 = (sum .) . zipWith (*)

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

productoEscalar4 :: [Integer] -> [Integer] -> Integer
productoEscalar4 [] _          = 0
productoEscalar4 _ []          = 0
productoEscalar4 (x:xs) (y:ys) = x*y + productoEscalar4 xs ys

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

productoEscalar5 :: [Integer] -> [Integer] -> Integer
productoEscalar5 (x:xs) (y:ys) = x*y + productoEscalar5 xs ys
productoEscalar5 _ _           = 0

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

productoEscalar6 :: [Integer] -> [Integer] -> Integer
productoEscalar6 xs ys =
  round (vector xs' <.> vector ys')
  where xs' = map fromIntegral xs
        ys' = map fromIntegral ys

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

-- La propiedad es
prop_productoEscalar :: [Integer] -> [Integer] -> Bool
prop_productoEscalar xs ys =
  all (== productoEscalar1 xs ys)
      [productoEscalar2 xs ys,
       productoEscalar3 xs ys,
       productoEscalar4 xs ys,
       productoEscalar5 xs ys,
       productoEscalar6 xs' ys']
  where n = min (length xs) (length ys)
        xs' = take n xs
        ys' = take n ys

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

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

-- La comparación es
--    λ> productoEscalar1 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.37 secs, 803,827,520 bytes)
--    λ> productoEscalar2 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.69 secs, 611,008,272 bytes)
--    λ> productoEscalar3 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.69 secs, 611,008,536 bytes)
--    λ> productoEscalar4 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.64 secs, 742,290,272 bytes)
--    λ> productoEscalar5 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (1.63 secs, 742,290,064 bytes)
--    λ> productoEscalar6 (replicate (2*10^6) 1) (replicate (2*10^6) 1)
--    2000000
--    (0.32 secs, 835,679,200 bytes)
--
--    λ> productoEscalar2 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (1.90 secs, 1,831,960,336 bytes)
--    λ> productoEscalar3 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (1.87 secs, 1,831,960,600 bytes)
--    λ> productoEscalar6 (replicate (6*10^6) 1) (replicate (6*10^6) 1)
--    6000000
--    (0.78 secs, 2,573,005,952 bytes)

import Numeric.LinearAlgebra ((<.>), vector)

import Test.QuickCheck (quickCheck)

-- 1ª solución

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

productoEscalar1 :: [Integer] -> [Integer] -> Integer

productoEscalar1 xs ys = sum [x*y | (x,y) <- zip xs ys]

-- 2ª solución

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

productoEscalar2 :: [Integer] -> [Integer] -> Integer

productoEscalar2 xs ys = sum (zipWith (*) xs ys)

-- 3ª solución

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

productoEscalar3 :: [Integer] -> [Integer] -> Integer

productoEscalar3 = (sum .) . zipWith (*)

-- 4ª solución

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

productoEscalar4 :: [Integer] -> [Integer] -> Integer

productoEscalar4 [] _ = 0

productoEscalar4 _ [] = 0

productoEscalar4 (x:xs) (y:ys) = x*y + productoEscalar4 xs ys

-- 5ª solución

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

productoEscalar5 :: [Integer] -> [Integer] -> Integer

productoEscalar5 (x:xs) (y:ys) = x*y + productoEscalar5 xs ys

productoEscalar5 _ _ = 0

-- 6ª solución

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

productoEscalar6 :: [Integer] -> [Integer] -> Integer

productoEscalar6 xs ys =

round (vector xs' <.> vector ys')

where xs' = map fromIntegral xs

ys' = map fromIntegral ys

-- Comprobación de equivalencia

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

-- La propiedad es

prop_productoEscalar :: [Integer] -> [Integer] -> Bool

prop_productoEscalar xs ys =

all (== productoEscalar1 xs ys)

[productoEscalar2 xs ys,

productoEscalar3 xs ys,

productoEscalar4 xs ys,

productoEscalar5 xs ys,

productoEscalar6 xs' ys']

where n = min (length xs) (length ys)

xs' = take n xs

ys' = take n ys

-- La comprobación es

-- λ> quickCheck prop_productoEscalar

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> productoEscalar1 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (1.37 secs, 803,827,520 bytes)

-- λ> productoEscalar2 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (0.69 secs, 611,008,272 bytes)

-- λ> productoEscalar3 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (0.69 secs, 611,008,536 bytes)

-- λ> productoEscalar4 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (1.64 secs, 742,290,272 bytes)

-- λ> productoEscalar5 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (1.63 secs, 742,290,064 bytes)

-- λ> productoEscalar6 (replicate (2*10^6) 1) (replicate (2*10^6) 1)

-- 2000000

-- (0.32 secs, 835,679,200 bytes)

-- λ> productoEscalar2 (replicate (6*10^6) 1) (replicate (6*10^6) 1)

-- 6000000

-- (1.90 secs, 1,831,960,336 bytes)

-- λ> productoEscalar3 (replicate (6*10^6) 1) (replicate (6*10^6) 1)

-- 6000000

-- (1.87 secs, 1,831,960,600 bytes)

-- λ> productoEscalar6 (replicate (6*10^6) 1) (replicate (6*10^6) 1)

-- 6000000

-- (0.78 secs, 2,573,005,952 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from operator import mul
from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from numpy import dot

setrecursionlimit(10**6)

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

def productoEscalar1(xs: list[int], ys: list[int]) -> int:
    return sum(x * y for (x, y) in zip(xs, ys))

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

def productoEscalar2(xs: list[int], ys: list[int]) -> int:
    return sum(map(mul, xs, ys))

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

def productoEscalar3(xs: list[int], ys: list[int]) -> int:
    if xs and ys:
        return xs[0] * ys[0] + productoEscalar3(xs[1:], ys[1:])
    return 0

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

def productoEscalar4(xs: list[int], ys: list[int]) -> int:
    return dot(xs, ys)

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

# La propiedad es
@given(st.lists(st.integers(min_value=1, max_value=100)),
       st.lists(st.integers(min_value=1, max_value=100)))
def test_productoEscalar(xs: list[int], ys: list[int]) -> None:
    r = productoEscalar1(xs, ys)
    assert productoEscalar2(xs, ys) == r
    assert productoEscalar3(xs, ys) == r
    n = min(len(xs), len(ys))
    xs1 = xs[:n]
    ys1 = ys[:n]
    assert productoEscalar4(xs1, ys1) == r

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

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

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

# La comparación es
#    >>> tiempo('productoEscalar1([1]*(10**4), [1]*(10**4))')
#    0.00 segundos
#    >>> tiempo('productoEscalar3([1]*(10**4), [1]*(10**4))')
#    0.55 segundos
#
#    >>> tiempo('productoEscalar1([1]*(10**7), [1]*(10**7))')
#    0.60 segundos
#    >>> tiempo('productoEscalar2([1]*(10**7), [1]*(10**7))')
#    0.26 segundos
#    >>> tiempo('productoEscalar4([1]*(10**7), [1]*(10**7))')
#    1.73 segundos

from operator import mul

from sys import setrecursionlimit

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

from numpy import dot

setrecursionlimit(10**6)

# 1ª solución

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

def productoEscalar1(xs: list[int], ys: list[int]) -> int:

return sum(x * y for (x, y) in zip(xs, ys))

# 2ª solución

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

def productoEscalar2(xs: list[int], ys: list[int]) -> int:

return sum(map(mul, xs, ys))

# 3ª solución

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

def productoEscalar3(xs: list[int], ys: list[int]) -> int:

if xs and ys:

return xs[0] * ys[0] + productoEscalar3(xs[1:], ys[1:])

return 0

# 4ª solución

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

def productoEscalar4(xs: list[int], ys: list[int]) -> int:

return dot(xs, ys)

# Comprobación de equivalencia

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

# La propiedad es

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

st.lists(st.integers(min_value=1, max_value=100)))

def test_productoEscalar(xs: list[int], ys: list[int]) -> None:

r = productoEscalar1(xs, ys)

assert productoEscalar2(xs, ys) == r

assert productoEscalar3(xs, ys) == r

n = min(len(xs), len(ys))

xs1 = xs[:n]

ys1 = ys[:n]

assert productoEscalar4(xs1, ys1) == r

# La comprobación es

# src> poetry run pytest -q producto_escalar.py

# 1 passed in 0.37s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

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

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

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

# La comparación es

# >>> tiempo('productoEscalar1([1]*(10**4), [1]*(10**4))')

# 0.00 segundos

# >>> tiempo('productoEscalar3([1]*(10**4), [1]*(10**4))')

# 0.55 segundos

# >>> tiempo('productoEscalar1([1]*(10**7), [1]*(10**7))')

# 0.60 segundos

# >>> tiempo('productoEscalar2([1]*(10**7), [1]*(10**7))')

# 0.26 segundos

# >>> tiempo('productoEscalar4([1]*(10**7), [1]*(10**7))')

# 1.73 segundos

El código se encuentra en GitHub.

Ternas pitagóricas con suma dada

PorJosé A. Alonso 18-octubre-202214-diciembre-2022

Una terna pitagórica es una terna de números naturales (a,b,c) tal que a<b<c y a²+b²=c². Por ejemplo (3,4,5) es una terna pitagórica.

Definir la función

   ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]

1	ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]

tal que ternasPitagoricas x es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,

   ternasPitagoricas 12     == [(3,4,5)]
   ternasPitagoricas 60     == [(10,24,26),(15,20,25)]
   ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

ternasPitagoricas 12 == [(3,4,5)]

ternasPitagoricas 60 == [(10,24,26),(15,20,25)]

ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

Soluciones

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

Soluciones en Haskell

import Data.List (nub,sort)
import Test.QuickCheck

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

ternasPitagoricas1 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas1 x =
  [(a,b,c) | a <- [0..x],
             b <- [a+1..x],
             c <- [b+1..x],
             a^2 + b^2 == c^2,
             a+b+c == x]

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

ternasPitagoricas2 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas2 x =
  [(a,b,c) | a <- [1..x],
             b <- [a+1..x-a],
             let c = x-a-b,
             a^2+b^2 == c^2]

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

-- Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse
-- por
--    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,
-- con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

ternasPitagoricas3 :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas3 x =
  nub [(d*a,d*b,d*c) | d <- [1..x],
                       x `mod` d == 0,
                       (a,b,c) <- aux (x `div` d)]
  where
    aux y = [(a,b,c) | m <- [2..limite],
                       n <- [1..m-1],
                       let [a,b] = sort [m^2 - n^2, 2*m*n],
                       let c = m^2 + n^2,
                       a+b+c == y]
      where limite = ceiling (sqrt (fromIntegral y))

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_ternasPitagoricas :: Positive Integer -> Bool
prop_ternasPitagoricas (Positive x) =
  all (== (ternasPitagoricas1 x))
      [ternasPitagoricas2 x,
       ternasPitagoricas3 x]

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

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

-- La comparación es
--    λ> ternasPitagoricas1 200
--    [(40,75,85)]
--    (1.90 secs, 2,404,800,856 bytes)
--    λ> ternasPitagoricas2 200
--    [(40,75,85)]
--    (0.06 secs, 19,334,232 bytes)
--    λ> ternasPitagoricas3 200
--    [(40,75,85)]
--    (0.01 secs, 994,224 bytes)
--
--    λ> ternasPitagoricas2 3000
--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]
--    (4.41 secs, 4,354,148,136 bytes)
--    λ> ternasPitagoricas3 3000
--    [(500,1200,1300),(600,1125,1275),(750,1000,1250)]
--    (0.05 secs, 17,110,360 bytes)

import Data.List (nub,sort)

import Test.QuickCheck

-- 1ª solución --

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

ternasPitagoricas1 :: Integer -> [(Integer,Integer,Integer)]

ternasPitagoricas1 x =

[(a,b,c) | a <- [0..x],

b <- [a+1..x],

c <- [b+1..x],

a^2 + b^2 == c^2,

a+b+c == x]

-- 2ª solución --

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

ternasPitagoricas2 :: Integer -> [(Integer,Integer,Integer)]

ternasPitagoricas2 x =

[(a,b,c) | a <- [1..x],

b <- [a+1..x-a],

let c = x-a-b,

a^2+b^2 == c^2]

-- 3ª solución --

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

-- Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse

-- por

-- a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,

-- con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

ternasPitagoricas3 :: Integer -> [(Integer,Integer,Integer)]

ternasPitagoricas3 x =

nub [(d*a,d*b,d*c) | d <- [1..x],

x `mod` d == 0,

(a,b,c) <- aux (x `div` d)]

where

aux y = [(a,b,c) | m <- [2..limite],

n <- [1..m-1],

let [a,b] = sort [m^2 - n^2, 2*m*n],

let c = m^2 + n^2,

a+b+c == y]

where limite = ceiling (sqrt (fromIntegral y))

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_ternasPitagoricas :: Positive Integer -> Bool

prop_ternasPitagoricas (Positive x) =

all (== (ternasPitagoricas1 x))

[ternasPitagoricas2 x,

ternasPitagoricas3 x]

-- La comprobación es

-- λ> quickCheck prop_ternasPitagoricas

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> ternasPitagoricas1 200

-- [(40,75,85)]

-- (1.90 secs, 2,404,800,856 bytes)

-- λ> ternasPitagoricas2 200

-- [(40,75,85)]

-- (0.06 secs, 19,334,232 bytes)

-- λ> ternasPitagoricas3 200

-- [(40,75,85)]

-- (0.01 secs, 994,224 bytes)

-- λ> ternasPitagoricas2 3000

-- [(500,1200,1300),(600,1125,1275),(750,1000,1250)]

-- (4.41 secs, 4,354,148,136 bytes)

-- λ> ternasPitagoricas3 3000

-- [(500,1200,1300),(600,1125,1275),(750,1000,1250)]

-- (0.05 secs, 17,110,360 bytes)

El código se encuentra en GitHub.

Soluciones en Python

from math import ceil, sqrt
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

def ternasPitagoricas1(x: int) -> list[tuple[int, int, int]]:
    return [(a, b, c)
            for a in range(0, x+1)
            for b in range(a+1, x+1)
            for c in range(b+1, x+1)
            if a**2 + b**2 == c**2 and a + b + c == x]

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

def ternasPitagoricas2(x: int) -> list[tuple[int, int, int]]:
    return [(a, b, c)
            for a in range(1, x+1)
            for b in range(a+1, x-a+1)
            for c in [x - a - b]
            if a**2 + b**2 == c**2]

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

# Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse
# por
#    a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,
# con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

def ternasPitagoricas3(x: int) -> list[tuple[int, int, int]]:
    def aux(y: int) -> list[tuple[int, int, int]]:
        return [(a, b, c)
                for m in range(2, 1 + ceil(sqrt(y)))
                for n in range(1, m)
                for a in [min(m**2 - n**2, 2*m*n)]
                for b in [max(m**2 - n**2, 2*m*n)]
                for c in [m**2 + n**2]
                if a+b+c == y]

    return list(set(((d*a, d*b, d*c)
                     for d in range(1, x+1)
                     for (a, b, c) in aux(x // d)
                     if x % d == 0)))

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

# La propiedad es
@given(st.integers(min_value=1, max_value=50))
def test_ternasPitagoricas(n: int) -> None:
    r = set(ternasPitagoricas1(n))
    assert set(ternasPitagoricas2(n)) == r
    assert set(ternasPitagoricas3(n)) == r

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

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

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

# La comparación es
#    >>> tiempo('ternasPitagoricas1(300)')
#    2.83 segundos
#    >>> tiempo('ternasPitagoricas2(300)')
#    0.01 segundos
#    >>> tiempo('ternasPitagoricas3(300)')
#    0.00 segundos
#
#    >>> tiempo('ternasPitagoricas2(3000)')
#    1.48 segundos
#    >>> tiempo('ternasPitagoricas3(3000)')
#    0.02 segundos

from math import ceil, sqrt

from timeit import Timer, default_timer

from hypothesis import given

from hypothesis import strategies as st

# 1ª solución --

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

def ternasPitagoricas1(x: int) -> list[tuple[int, int, int]]:

return [(a, b, c)

for a in range(0, x+1)

for b in range(a+1, x+1)

for c in range(b+1, x+1)

if a**2 + b**2 == c**2 and a + b + c == x]

# 2ª solución --

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

def ternasPitagoricas2(x: int) -> list[tuple[int, int, int]]:

return [(a, b, c)

for a in range(1, x+1)

for b in range(a+1, x-a+1)

for c in [x - a - b]

if a**2 + b**2 == c**2]

# 3ª solución --

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

# Todas las ternas pitagóricas primitivas (a,b,c) pueden representarse

# por

# a = m^2 - n^2, b = 2*m*n, c = m^2 + n^2,

# con 1 <= n < m. (Ver en https://bit.ly/35UNY6L ).

def ternasPitagoricas3(x: int) -> list[tuple[int, int, int]]:

def aux(y: int) -> list[tuple[int, int, int]]:

return [(a, b, c)

for m in range(2, 1 + ceil(sqrt(y)))

for n in range(1, m)

for a in [min(m**2 - n**2, 2*m*n)]

for b in [max(m**2 - n**2, 2*m*n)]

for c in [m**2 + n**2]

if a+b+c == y]

return list(set(((d*a, d*b, d*c)

for d in range(1, x+1)

for (a, b, c) in aux(x // d)

if x % d == 0)))

# Comprobación de equivalencia

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

# La propiedad es

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

def test_ternasPitagoricas(n: int) -> None:

r = set(ternasPitagoricas1(n))

assert set(ternasPitagoricas2(n)) == r

assert set(ternasPitagoricas3(n)) == r

# La comprobación es

# src> poetry run pytest -q ternas_pitagoricas_con_suma_dada.py

# 1 passed in 0.35s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

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

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

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

# La comparación es

# >>> tiempo('ternasPitagoricas1(300)')

# 2.83 segundos

# >>> tiempo('ternasPitagoricas2(300)')

# 0.01 segundos

# >>> tiempo('ternasPitagoricas3(300)')

# 0.00 segundos

# >>> tiempo('ternasPitagoricas2(3000)')

# 1.48 segundos

# >>> tiempo('ternasPitagoricas3(3000)')

# 0.02 segundos

El código se encuentra en GitHub.

Meses: octubre 2022

Base de datos de actividades

Representación densa de polinomios

Suma de elementos consecutivos

Producto escalar

Ternas pitagóricas con suma dada

Entradas recientes

Buscar

Correo electrónico