Menu Close

PFH: La semana en Exercitium (16 de septiembre de 2022)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

A continuación se muestran las soluciones.

1. Raíces de la ecuación de segundo grado

Definir la función

   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    ==  []

Comprobar con QuickCheck que la suma de las raíces de la ecuación ax^2 + bx + c = 0 (con a no nulo) es \frac{-b}{a} y su producto es \frac{c}{a}.

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.

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

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

   s = (a+b+c)/2

Definir la función

   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

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

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))

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

   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]  ==  []

Comprobar con QuickCheck que la intersección de intervalos es conmutativa.

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.

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

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

   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)
  • 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)
  • 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)
  • 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

Comprobar con QuickCheck la propiedad distributiva del producto racional respecto de la suma.

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.

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

El código se encuentra en GitHub.

5. Reconocimiento de subconjunto

Definir la función

   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

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)

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

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
PFH