27-enero-2023 – Exercitium

TAD de las pilas: Inclusión de pilas

PorJosé A. Alonso 27-enero-202322-enero-2023

Utilizando el tipo abstracto de datos de las pilas, definir la función

   contenidaPila :: Eq a => Pila a -> Pila a -> Bool

1	contenidaPila :: Eq a => Pila a -> Pila a -> Bool

tal que contenidaPila p1 p2 se verifica si todos los elementos de de la pila p1 son elementos de la pila p2. Por ejemplo,

   λ> ej1 = apila 3 (apila 2 vacia)
   λ> ej2 = apila 3 (apila 4 vacia)
   λ> ej3 = apila 5 (apila 2 (apila 3 vacia))
   λ> contenidaPila ej1 ej3
   True
   λ> contenidaPila ej2 ej3
   False

λ> ej1 = apila 3 (apila 2 vacia)

λ> ej2 = apila 3 (apila 4 vacia)

λ> ej3 = apila 5 (apila 2 (apila 3 vacia))

λ> contenidaPila ej1 ej3

True

λ> contenidaPila ej2 ej3

False

Soluciones

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

Soluciones en Haskell

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import PertenecePila (pertenecePila)
import Test.QuickCheck

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

-- Se usará la función pertenecePila del ejercicio
-- "Pertenencia a una pila" que se encuentra en
-- https://bit.ly/3WdM9GC

contenidaPila1 :: Eq a => Pila a -> Pila a -> Bool
contenidaPila1 p1 p2
  | esVacia p1 = True
  | otherwise  = pertenecePila cp1 p2 && contenidaPila1 dp1 p2
  where cp1 = cima p1
        dp1 = desapila p1

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

contenidaPila2 :: Eq a => Pila a -> Pila a -> Bool
contenidaPila2 p1 p2 =
  contenidaLista (pilaAlista p1) (pilaAlista p2)

contenidaLista :: Eq a => [a] -> [a] -> Bool
contenidaLista xs ys =
  all (`elem` ys) xs

-- (pilaALista p) es la lista formada por los elementos de la
-- lista p. Por ejemplo,
--    λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia)))
--    [3, 2, 5]
pilaAlista :: Pila a -> [a]
pilaAlista = reverse . aux
  where aux p | esVacia p = []
              | otherwise = cp : aux dp
          where cp = cima p
                dp = desapila p

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

-- La propiedad es
prop_contenidaPila :: Pila Int -> Pila Int -> Bool
prop_contenidaPila p1 p2 =
  contenidaPila1 p1 p2 == contenidaPila2 p1 p2

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

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)

import PertenecePila (pertenecePila)

import Test.QuickCheck

-- 1ª solución

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

-- Se usará la función pertenecePila del ejercicio

-- "Pertenencia a una pila" que se encuentra en

-- https://bit.ly/3WdM9GC

contenidaPila1 :: Eq a => Pila a -> Pila a -> Bool

contenidaPila1 p1 p2

| esVacia p1 = True

| otherwise = pertenecePila cp1 p2 && contenidaPila1 dp1 p2

where cp1 = cima p1

dp1 = desapila p1

-- 2ª solución

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

contenidaPila2 :: Eq a => Pila a -> Pila a -> Bool

contenidaPila2 p1 p2 =

contenidaLista (pilaAlista p1) (pilaAlista p2)

contenidaLista :: Eq a => [a] -> [a] -> Bool

contenidaLista xs ys =

all (`elem` ys) xs

-- (pilaALista p) es la lista formada por los elementos de la

-- lista p. Por ejemplo,

-- λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia)))

-- [3, 2, 5]

pilaAlista :: Pila a -> [a]

pilaAlista = reverse . aux

where aux p | esVacia p = []

| otherwise = cp : aux dp

where cp = cima p

dp = desapila p

-- Comprobación de equivalencia

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

-- La propiedad es

prop_contenidaPila :: Pila Int -> Pila Int -> Bool

prop_contenidaPila p1 p2 =

contenidaPila1 p1 p2 == contenidaPila2 p1 p2

-- La comprobación es

-- λ> quickCheck prop_contenidaPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.pertenecePila import pertenecePila
from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)
from src.transformaciones_pilas_listas import pilaAlista

A = TypeVar('A')

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

# Se usará la función pertenecePila del ejercicio
# "Pertenencia a una pila" que se encuentra en
# https://bit.ly/3WdM9GC

def contenidaPila1(p1: Pila[A], p2: Pila[A]) -> bool:
    if esVacia(p1):
        return True
    cp1 = cima(p1)
    dp1 = desapila(p1)
    return pertenecePila(cp1, p2) and contenidaPila1(dp1, p2)

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

# Se usará la función pilaAlista del ejercicio
# "Transformaciones entre pilas y listas" que se encuentra en
# https://bit.ly/3ZHewQ8

def contenidaPila2(p1: Pila[A], p2: Pila[A]) -> bool:
    return set(pilaAlista(p1)) <= set(pilaAlista(p2))

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

def contenidaPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    if p1.esVacia():
        return True
    cp1 = p1.cima()
    p1.desapila()
    return pertenecePila(cp1, p2) and contenidaPila1(p1, p2)

def contenidaPila3(p1: Pila[A], p2: Pila[A]) -> bool:
    q = deepcopy(p1)
    return contenidaPila3Aux(q, p2)

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

def contenidaPila4Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    while not p1.esVacia():
        cp1 = p1.cima()
        p1.desapila()
        if not pertenecePila(cp1, p2):
            return False
    return True

def contenidaPila4(p1: Pila[A], p2: Pila[A]) -> bool:
    q = deepcopy(p1)
    return contenidaPila4Aux(q, p2)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(p1=pilaAleatoria(), p2=pilaAleatoria())
def test_contenidaPila(p1: Pila[int], p2: Pila[int]) -> None:
    r = contenidaPila1(p1, p2)
    assert contenidaPila2(p1, p2) == r
    assert contenidaPila3(p1, p2) == r
    assert contenidaPila4(p1, p2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.pertenecePila import pertenecePila

from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,

vacia)

from src.transformaciones_pilas_listas import pilaAlista

A = TypeVar('A')

# 1ª solución

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

# Se usará la función pertenecePila del ejercicio

# "Pertenencia a una pila" que se encuentra en

# https://bit.ly/3WdM9GC

def contenidaPila1(p1: Pila[A], p2: Pila[A]) -> bool:

if esVacia(p1):

return True

cp1 = cima(p1)

dp1 = desapila(p1)

return pertenecePila(cp1, p2) and contenidaPila1(dp1, p2)

# 2ª solución

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

# Se usará la función pilaAlista del ejercicio

# "Transformaciones entre pilas y listas" que se encuentra en

# https://bit.ly/3ZHewQ8

def contenidaPila2(p1: Pila[A], p2: Pila[A]) -> bool:

return set(pilaAlista(p1)) <= set(pilaAlista(p2))

# 3ª solución

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

def contenidaPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:

if p1.esVacia():

return True

cp1 = p1.cima()

p1.desapila()

return pertenecePila(cp1, p2) and contenidaPila1(p1, p2)

def contenidaPila3(p1: Pila[A], p2: Pila[A]) -> bool:

q = deepcopy(p1)

return contenidaPila3Aux(q, p2)

# 4ª solución

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

def contenidaPila4Aux(p1: Pila[A], p2: Pila[A]) -> bool:

while not p1.esVacia():

cp1 = p1.cima()

p1.desapila()

if not pertenecePila(cp1, p2):

return False

return True

def contenidaPila4(p1: Pila[A], p2: Pila[A]) -> bool:

q = deepcopy(p1)

return contenidaPila4Aux(q, p2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p1=pilaAleatoria(), p2=pilaAleatoria())

def test_contenidaPila(p1: Pila[int], p2: Pila[int]) -> None:

r = contenidaPila1(p1, p2)

assert contenidaPila2(p1, p2) == r

assert contenidaPila3(p1, p2) == r

assert contenidaPila4(p1, p2) == r

# La comprobación es

# src> poetry run pytest -q contenidaPila.py

# 1 passed in 0.40s

Día: 27-enero-2023

TAD de las pilas: Inclusión de pilas

Entradas recientes

Buscar

Correo electrónico