Ir al contenido principal

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

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.

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.