Menu Close

La semana en Exercitium (18 de marzo de 2023)

José A. Alonso-

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

A continuación se muestran las soluciones.

1. TAD de los conjuntos: Intersección de varios conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   interseccionG :: Ord a => [Conj a] -> Conj a

tal que interseccionG cs es la intersección de la lista de conjuntos cs. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 3 (inserta 5 vacio))
   λ> ej2 = inserta 5 (inserta 2 (inserta 7 vacio))
   λ> ej3 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> interseccionG [ej1, ej2, ej3]
   {2, 5}

Soluciones

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


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_Interseccion_de_dos_conjuntos (interseccion)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
interseccionG :: Ord a => [Conj a] -> Conj a
interseccionG [c]      = c
interseccionG (cs:css) = interseccion cs (interseccionG css)
 
-- 2ª solución
-- ===========
 
interseccionG2 :: Ord a => [Conj a] -> Conj a
interseccionG2 = foldr1 interseccion
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_interseccionG :: NonEmptyList (Conj Int) -> Bool
prop_interseccionG (NonEmpty cs) =
  interseccionG cs == interseccionG2 cs
 
-- La comprobación es
--    λ> quickCheck prop_interseccionG1
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from functools import reduce
from typing import Protocol, TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.TAD.conjunto import Conj, conjuntoAleatorio, inserta, vacio
from src.TAD_Interseccion_de_dos_conjuntos import interseccion
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
# 1ª solución
# ===========
 
def interseccionG(cs: list[Conj[A]]) -> Conj[A]:
    if len(cs) == 1:
        return cs[0]
    return interseccion(cs[0], interseccionG(cs[1:]))
 
# 2ª solución
# ===========
 
def interseccionG2(cs: list[Conj[A]]) -> Conj[A]:
    return reduce(interseccion, cs[1:], cs[0])
 
# 3ª solución
# ===========
 
def interseccionG3(cs: list[Conj[A]]) -> Conj[A]:
    r = cs[0]
    for c in cs[1:]:
        r = interseccion(c, r)
    return r
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(conjuntoAleatorio(), min_size=1, max_size=10))
def test_interseccionG(cs: list[Conj[int]]) -> None:
    r = interseccionG(cs)
    assert interseccionG2(cs) == r
    assert interseccionG3(cs) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Interseccion_de_varios_conjuntos.py
#    1 passed in 0.60s

2. TAD de los conjuntos: Conjuntos disjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   disjuntos :: Ord a => Conj a -> Conj a -> Bool

tal que disjuntos c1 c2 se verifica si los conjuntos c1 y c2 son disjuntos. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 5 vacio)
   λ> ej2 = inserta 4 (inserta 3 vacio)
   λ> ej3 = inserta 5 (inserta 3 vacio)
   λ> disjuntos ej1 ej2
   True
   λ> disjuntos ej1 ej3
   False

Soluciones

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


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina, pertenece)
import TAD_Interseccion_de_dos_conjuntos (interseccion)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
disjuntos :: Ord a => Conj a -> Conj a -> Bool
disjuntos c1 c2 = esVacio (interseccion c1 c2)
 
-- La función interseccion está definida en el ejercicio
-- "Intersección de dos conjuntos" que se encuentra en
-- https://bit.ly/3jDL9xZ
 
-- 2ª solución
-- ===========
 
disjuntos2 :: Ord a => Conj a -> Conj a -> Bool
disjuntos2 c1 c2
  | esVacio c1 = True
  | pertenece mc1 c2 = False
  | otherwise        = disjuntos2 rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1
 
-- 3ª solución
-- ===========
 
disjuntos3 :: Ord a => Conj a -> Conj a -> Bool
disjuntos3 c1 c2 =
  all (`notElem` ys) xs
  where xs = conjuntoAlista c1
        ys = conjuntoAlista c2
 
-- La función conjuntoAlista está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra en
-- https://bit.ly/3RexzxH
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_disjuntos :: Conj Int -> Conj Int -> Bool
prop_disjuntos c1 c2 =
  all (== disjuntos c1 c2)
      [disjuntos2 c1 c2,
       disjuntos3 c1 c2]
 
-- La comprobación es
--    λ> quickCheck prop_disjuntos
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar
 
from hypothesis import given
 
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Interseccion_de_dos_conjuntos import interseccion
from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
# 1ª solución
# ===========
 
def disjuntos(c1: Conj[A], c2: Conj[A]) -> bool:
    return esVacio(interseccion(c1, c2))
 
# 2ª solución
# ===========
 
def disjuntos2(c1: Conj[A], c2: Conj[A]) -> bool:
    if esVacio(c1):
        return True
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    if pertenece(mc1, c2):
        return False
    return disjuntos2(rc1, c2)
 
# 3ª solución
# ===========
 
def disjuntos3(c1: Conj[A], c2: Conj[A]) -> bool:
    xs = conjuntoAlista(c1)
    ys = conjuntoAlista(c2)
    return all((x not in ys for x in xs))
 
# La función conjuntoAlista está definida en el ejercicio
# "Transformaciones entre conjuntos y listas" que se encuentra en
# https://bit.ly/3RexzxH
 
# 4ª solución
# ===========
 
def disjuntos4Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not esVacio(c1):
        mc1 = menor(c1)
        if pertenece(mc1, c2):
            return False
        c1 = elimina(mc1, c1)
    return True
 
def disjuntos4(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return disjuntos4Aux(_c1, c2)
 
# 5ª solución
# ===========
 
def disjuntos5Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not c1.esVacio():
        mc1 = c1.menor()
        if c2.pertenece(mc1):
            return False
        c1.elimina(mc1)
    return True
 
def disjuntos5(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return disjuntos5Aux(_c1, c2)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_disjuntos(c1: Conj[int], c2: Conj[int]) -> None:
    r = disjuntos(c1, c2)
    assert disjuntos2(c1, c2) == r
    assert disjuntos3(c1, c2) == r
    assert disjuntos4(c1, c2) == r
    assert disjuntos5(c1, c2) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Conjuntos_disjuntos.py
#    1 passed in 0.34s

3. TAD de los conjuntos: Diferencia de conjuntos

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   diferencia :: Ord a => Conj a -> Conj a -> Conj a

tal que diferencia c1 c2 es el conjunto de los elementos de c1 que no son elementos de c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio)))
   λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio))
   λ> diferencia ej1 ej2
   {2, 5}
   λ> diferencia ej2 ej1
   {4}
   λ> diferencia ej1 ej1
   {}

Soluciones

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


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
diferencia :: Ord a => Conj a -> Conj a -> Conj a
diferencia c1 c2
  | esVacio c1       = vacio
  | pertenece mc1 c2 = diferencia rc1 c2
  | otherwise        = inserta mc1 (diferencia rc1 c2)
  where mc1 = menor c1
        rc1 = elimina mc1 c1
 
-- 2ª solución
-- ===========
 
diferencia2 :: Ord a => Conj a -> Conj a -> Conj a
diferencia2 c1 c2 =
  listaAconjunto [x | x <- conjuntoAlista c1, not (pertenece x c2)]
 
-- Las funciones conjuntoAlista y listaAconjunto está definida en el
-- ejercicio Transformaciones entre conjuntos y listas" que se encuentra
-- en https://bit.ly/3RexzxH
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_diferencia :: Conj Int -> Conj Int -> Bool
prop_diferencia c1 c2 =
  diferencia c1 c2 == diferencia2 c1 c2
 
-- La comprobación es
--    λ> quickCheck prop_diferencia
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar
 
from hypothesis import given
 
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
# 1ª solución
# ===========
 
def diferencia(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    if esVacio(c1):
        return vacio()
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    if pertenece(mc1, c2):
        return diferencia(rc1, c2)
    return inserta(mc1, diferencia(rc1, c2))
 
# 2ª solución
# ===========
 
def diferencia2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return listaAconjunto([x for x in conjuntoAlista(c1)
                           if not pertenece(x, c2)])
 
# Las funciones conjuntoAlista y listaAconjunto está definida en el
# ejercicio Transformaciones entre conjuntos y listas" que se encuentra
# en https://bit.ly/3RexzxH
 
# 3ª solución
# ===========
 
def diferencia3Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not esVacio(c1):
        mc1 = menor(c1)
        if not pertenece(mc1, c2):
            r = inserta(mc1, r)
        c1 = elimina(mc1, c1)
    return r
 
def diferencia3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    return diferencia3Aux(_c1, c2)
 
# 4ª solución
# ===========
 
def diferencia4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = Conj()
    while not c1.esVacio():
        mc1 = c1.menor()
        if not c2.pertenece(mc1):
            r.inserta(mc1)
        c1.elimina(mc1)
    return r
 
def diferencia4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    return diferencia4Aux(_c1, c2)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_diferencia(c1: Conj[int], c2: Conj[int]) -> None:
    r = diferencia(c1, c2)
    assert diferencia2(c1, c2) == r
    assert diferencia3(c1, c2) == r
    assert diferencia4(c1, c2) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Diferencia_de_conjuntos.py
#    1 passed in 0.31s

4. TAD de los conjuntos: Diferencia simétrica

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a

tal que diferenciaSimetrica c1 c2 es la diferencia simétrica de los conjuntos c1 y c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio)))
   λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio))
   λ> diferenciaSimetrica ej1 ej2
   {2, 4, 5}

Soluciones

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


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_Diferencia_de_conjuntos (diferencia)
import TAD_Interseccion_de_dos_conjuntos (interseccion)
import TAD_Union_de_dos_conjuntos (union)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
 
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a
diferenciaSimetrica c1 c2 =
  diferencia (union c1 c2) (interseccion c1 c2)
 
-- 2ª solución
-- ===========
 
diferenciaSimetrica2 :: Ord a => Conj a -> Conj a -> Conj a
diferenciaSimetrica2 c1 c2 =
  listaAconjunto ([x | x <- xs, x `notElem` ys] ++
                  [y | y <- ys, y `notElem` xs])
  where xs = conjuntoAlista c1
        ys = conjuntoAlista c2
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_diferenciaSimetrica :: Conj Int -> Conj Int -> Bool
prop_diferenciaSimetrica c1 c2 =
  diferenciaSimetrica c1 c2 == diferenciaSimetrica2 c2 c1
 
-- La comprobación es
--    λ> quickCheck prop_diferenciaSimetrica
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar
 
from hypothesis import given
 
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Diferencia_de_conjuntos import diferencia
from src.TAD_Interseccion_de_dos_conjuntos import interseccion
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)
from src.TAD_Union_de_dos_conjuntos import union
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
# 1ª solución
# ===========
 
def diferenciaSimetrica(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return diferencia(union(c1, c2), interseccion(c1, c2))
 
# 2ª solución
# ===========
 
def diferenciaSimetrica2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    xs = conjuntoAlista(c1)
    ys = conjuntoAlista(c2)
    return listaAconjunto([x for x in xs if x not in ys] +
                          [y for y in ys if y not in xs])
 
# 3ª solución
# ===========
 
def diferenciaSimetrica3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    while not esVacio(_c1):
        mc1 = menor(_c1)
        if not pertenece(mc1, c2):
            r = inserta(mc1, r)
        _c1 = elimina(mc1, _c1)
    while not esVacio(_c2):
        mc2 = menor(_c2)
        if not pertenece(mc2, c1):
            r = inserta(mc2, r)
        _c2 = elimina(mc2, _c2)
    return r
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_diferenciaSimetrica(c1: Conj[int], c2: Conj[int]) -> None:
    r = diferenciaSimetrica(c1, c2)
    assert diferenciaSimetrica2(c1, c2) == r
    assert diferenciaSimetrica3(c1, c2) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Diferencia_simetrica.py
#    1 passed in 0.30s

5. TAD de los conjuntos: Subconjunto determinado por una propiedad

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a

tal filtra p c es el conjunto de elementos de c que verifican el predicado p. Por ejemplo,

   λ> filtra even (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))
   {2, 4}
   λ> filtra odd (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))
   {5, 7}

Soluciones

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


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Test.QuickCheck.HigherOrder
 
-- 1ª solución
-- ===========
 
filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a
filtra p c
  | esVacio c = vacio
  | p mc      = inserta mc (filtra p rc)
  | otherwise = filtra p rc
  where mc = menor c
        rc = elimina mc c
 
-- 2ª solución
-- ===========
 
filtra2 :: Ord a => (a -> Bool) -> Conj a -> Conj a
filtra2 p c =
  listaAconjunto (filter p (conjuntoAlista c))
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_filtra :: (Int -> Bool) -> [Int] -> Bool
prop_filtra p xs =
  filtra p c == filtra2 p c
  where c = listaAconjunto xs
 
-- La comprobación es
--    λ> quickCheck' prop_filtra
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from copy import deepcopy
from typing import Callable, Protocol, TypeVar
 
from hypothesis import given
 
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
# 1ª solución
# ===========
 
def filtra(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    if esVacio(c):
        return vacio()
    mc = menor(c)
    rc = elimina(mc, c)
    if p(mc):
        return inserta(mc, filtra(p, rc))
    return filtra(p, rc)
 
# 2ª solución
# ===========
 
def filtra2(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    return listaAconjunto(list(filter(p, conjuntoAlista(c))))
 
# 3ª solución
# ===========
 
def filtra3Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if p(mc):
            r = inserta(mc, r)
    return r
 
def filtra3(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    _c = deepcopy(c)
    return filtra3Aux(p, _c)
 
# 4ª solución
# ===========
 
def filtra4Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    r: Conj[A] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if p(mc):
            r.inserta(mc)
    return r
 
def filtra4(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    _c = deepcopy(c)
    return filtra4Aux(p, _c)
 
# Comprobación de equivalencia de las definiciones
# ================================================
 
# La propiedad es
@given(c=conjuntoAleatorio())
def test_filtra(c: Conj[int]) -> None:
    r = filtra(lambda x: x % 2 == 0, c)
    assert filtra2(lambda x: x % 2 == 0, c) == r
    assert filtra3(lambda x: x % 2 == 0, c) == r
    assert filtra4(lambda x: x % 2 == 0, c) == r
 
# La comprobación es
#    src> poetry run pytest -q TAD_Subconjunto_por_propiedad.py
#    1 passed in 0.28s
PFH