PFH: La semana en Exercitium (16 de septiembre de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Raíces de la ecuación de segundo grado
- 2. Fórmula de Herón para el área de un triángulo
- 3. Intersección de intervalos cerrados
- 4. Números racionales
- 5. Reconocimiento de subconjunto
A continuación se muestran las soluciones.
1. Raíces de la ecuación de segundo grado
Definir la función
1 |
raices :: Double -> Double -> Double -> [Double] |
tal que (raices a b c)
es la lista de las raíces reales de la ecuación . Por ejemplo,
1 2 3 |
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 (con no nulo) es y su producto es .
Soluciones en Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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.
2. Fórmula de Herón para el área de un triángulo
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
1 |
s = (a+b+c)/2 |
Definir la función
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,
1 |
area 3 4 5 == 6.0 |
Soluciones en Haskell
1 2 3 |
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
1 2 3 4 5 |
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.
3. Intersección de intervalos cerrados
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
1 |
interseccion :: Ord a => [a] -> [a] -> [a] |
tal que (interseccion i1 i2)
es la intersección de los intervalos i1
e i2
. Por ejemplo,
1 2 3 4 5 6 7 8 |
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 en Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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 |
El código se encuentra en GitHub.
4. Números racionales
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
1 2 3 4 |
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 racionalx
. Por ejemplo,
1 2 |
formaReducida (4,10) == (2,5) formaReducida (0,5) == (0,1) |
sumaRacional x y
es la suma de los números racionalesx
ey
, expresada en forma reducida. Por ejemplo,
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 racionalesx
ey
, expresada en forma reducida. Por ejemplo,
1 |
productoRacional (2,3) (5,6) == (5,9) |
igualdadRacional x y
se verifica si los números racionalesx
ey
son iguales. Por ejemplo,
1 2 3 |
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 en Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
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.
5. Reconocimiento de subconjunto
Definir la función
1 |
subconjunto :: Ord a => [a] -> [a] -> Bool |
tal que subconjunto xs ys
se verifica si xs
es un subconjunto de ys
. por ejemplo,
1 2 |
subconjunto [3,2,3] [2,5,3,5] == True subconjunto [3,2,3] [2,5,6,5] == False |
Soluciones en Haskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
from 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