PFH: La semana en Exercitium (4 de febrero de 2023)

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

1. TAD de las pilas: Reconocimiento de prefijos de pilas
2. TAD de las pilas: Reconocimiento de subpilas
3. TAD de las pilas: Reconocimiento de ordenación de pilas
4. TAD de las pilas: Ordenación de pilas por inserción
5. hTAD de las pilas: Eliminación de repeticiones en una pila

A continuación se muestran las soluciones.

1. TAD de las pilas: Reconocimiento de prefijos de pilas

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

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

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

tal que prefijoPila p1 p2 se verifica si la pila p1 es justamente un prefijo de la pila p2. Por ejemplo,

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

λ> ej1 = apila 4 (apila 2 vacia)

λ> ej2 = apila 4 (apila 2 (apila 5 vacia))

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

λ> prefijoPila ej1 ej2

True

λ> prefijoPila ej1 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 Transformaciones_pilas_listas (pilaAlista)
import Data.List (isSuffixOf)
import Test.QuickCheck

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

prefijoPila :: Eq a => Pila a -> Pila a -> Bool
prefijoPila p1 p2
  | esVacia p1 = True
  | esVacia p2 = False
  | otherwise  = cp1 == cp2 && prefijoPila dp1 dp2
  where cp1 = cima p1
        dp1 = desapila p1
        cp2 = cima p2
        dp2 = desapila 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

prefijoPila2 :: Eq a => Pila a -> Pila a -> Bool
prefijoPila2 p1 p2 =
  pilaAlista p1 `isSuffixOf` pilaAlista p2

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

-- La propiedad es
prop_prefijoPila :: Pila Int -> Pila Int -> Bool
prop_prefijoPila p1 p2 =
  prefijoPila p1 p2 == prefijoPila2 p1 p2

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

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

import Transformaciones_pilas_listas (pilaAlista)

import Data.List (isSuffixOf)

import Test.QuickCheck

-- 1ª solución

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

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

prefijoPila p1 p2

| esVacia p1 = True

| esVacia p2 = False

| otherwise = cp1 == cp2 && prefijoPila dp1 dp2

where cp1 = cima p1

dp1 = desapila p1

cp2 = cima p2

dp2 = desapila 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

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

prefijoPila2 p1 p2 =

pilaAlista p1 `isSuffixOf` pilaAlista p2

-- Comprobación de equivalencia

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

-- La propiedad es

prop_prefijoPila :: Pila Int -> Pila Int -> Bool

prop_prefijoPila p1 p2 =

prefijoPila p1 p2 == prefijoPila2 p1 p2

-- La comprobación es

-- λ> quickCheck prop_prefijoPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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
# ===========

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

# 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 esSufijoLista(xs: list[A], ys: list[A]) -> bool:
    if not xs:
        return True
    return xs == ys[-len(xs):]

def prefijoPila2(p1: Pila[A], p2: Pila[A]) -> bool:
    return esSufijoLista(pilaAlista(p1), pilaAlista(p2))

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

def prefijoPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    if p1.esVacia():
        return True
    if p2.esVacia():
        return False
    cp1 = p1.cima()
    p1.desapila()
    cp2 = p2.cima()
    p2.desapila()
    return cp1 == cp2 and prefijoPila3(p1, p2)

def prefijoPila3(p1: Pila[A], p2: Pila[A]) -> bool:
    q1 = deepcopy(p1)
    q2 = deepcopy(p2)
    return prefijoPila3Aux(q1, q2)

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

def prefijoPila4Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    while not p2.esVacia() and not p1.esVacia():
        if p1.cima() != p2.cima():
            return False
        p1.desapila()
        p2.desapila()
    return p1.esVacia()

def prefijoPila4(p1: Pila[A], p2: Pila[A]) -> bool:
    q1 = deepcopy(p1)
    q2 = deepcopy(p2)
    return prefijoPila4Aux(q1, q2)

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

# La propiedad es
@given(p1=pilaAleatoria(), p2=pilaAleatoria())
def test_prefijoPila(p1: Pila[int], p2: Pila[int]) -> None:
    r = prefijoPila(p1, p2)
    assert prefijoPila2(p1, p2) == r
    assert prefijoPila3(p1, p2) == r
    assert prefijoPila4(p1, p2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

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

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

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

if esVacia(p1):

return True

if esVacia(p2):

return False

cp1 = cima(p1)

dp1 = desapila(p1)

cp2 = cima(p2)

dp2 = desapila(p2)

return cp1 == cp2 and prefijoPila(dp1, dp2)

# 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 esSufijoLista(xs: list[A], ys: list[A]) -> bool:

if not xs:

return True

return xs == ys[-len(xs):]

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

return esSufijoLista(pilaAlista(p1), pilaAlista(p2))

# 3ª solución

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

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

if p1.esVacia():

return True

if p2.esVacia():

return False

cp1 = p1.cima()

p1.desapila()

cp2 = p2.cima()

p2.desapila()

return cp1 == cp2 and prefijoPila3(p1, p2)

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

q1 = deepcopy(p1)

q2 = deepcopy(p2)

return prefijoPila3Aux(q1, q2)

# 4ª solución

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

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

while not p2.esVacia() and not p1.esVacia():

if p1.cima() != p2.cima():

return False

p1.desapila()

p2.desapila()

return p1.esVacia()

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

q1 = deepcopy(p1)

q2 = deepcopy(p2)

return prefijoPila4Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

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

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

r = prefijoPila(p1, p2)

assert prefijoPila2(p1, p2) == r

assert prefijoPila3(p1, p2) == r

assert prefijoPila4(p1, p2) == r

# La comprobación es

# src> poetry run pytest -q prefijoPila.py

# 1 passed in 0.32s

2. TAD de las pilas: Reconocimiento de subpilas

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

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

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

tal que subPila p1 p2 se verifica si p1 es una subpila de p2. Por ejemplo,

   λ> ej1 = apila 2 (apila 3 vacia)
   λ> ej2 = apila 7 (apila 2 (apila 3 (apila 5 vacia)))
   λ> ej3 = apila 2 (apila 7 (apila 3 (apila 5 vacia)))
   λ> subPila ej1 ej2
   True
   λ> subPila ej1 ej3
   False

λ> ej1 = apila 2 (apila 3 vacia)

λ> ej2 = apila 7 (apila 2 (apila 3 (apila 5 vacia)))

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

λ> subPila ej1 ej2

True

λ> subPila ej1 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 Transformaciones_pilas_listas (pilaAlista)
import PrefijoPila (prefijoPila)
import Data.List (isPrefixOf, tails)
import Test.QuickCheck

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

-- Se usará la función PrefijoPila del ejercicio
-- "Reconocimiento de prefijos de pilas" que se encuentra en
-- https://bit.ly/3Xqu7lo

subPila1 :: Eq a => Pila a -> Pila a -> Bool
subPila1 p1 p2
    | esVacia p1 = True
    | esVacia p2 = False
    | cp1 == cp2 = prefijoPila dp1 dp2 || subPila1 p1 dp2
    | otherwise  = subPila1 p1 dp2
    where cp1 = cima p1
          dp1 = desapila p1
          cp2 = cima p2
          dp2 = desapila 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

subPila2 :: Eq a => Pila a -> Pila a -> Bool
subPila2 p1 p2 =
  sublista (pilaAlista p1) (pilaAlista p2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por
-- ejemplo,
--    sublista [3,2] [5,3,2,7]  ==  True
--    sublista [3,2] [5,3,7,2]  ==  False
sublista :: Eq a => [a] -> [a] -> Bool
sublista xs ys =
  any (xs `isPrefixOf`) (tails ys)

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

-- La propiedad es
prop_subPila :: Pila Int -> Pila Int -> Bool
prop_subPila p1 p2 =
  subPila1 p1 p2 == subPila2 p1 p2

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

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

import Transformaciones_pilas_listas (pilaAlista)

import PrefijoPila (prefijoPila)

import Data.List (isPrefixOf, tails)

import Test.QuickCheck

-- 1ª solución

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

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

-- "Reconocimiento de prefijos de pilas" que se encuentra en

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

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

subPila1 p1 p2

| esVacia p1 = True

| esVacia p2 = False

| cp1 == cp2 = prefijoPila dp1 dp2 || subPila1 p1 dp2

| otherwise = subPila1 p1 dp2

where cp1 = cima p1

dp1 = desapila p1

cp2 = cima p2

dp2 = desapila 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

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

subPila2 p1 p2 =

sublista (pilaAlista p1) (pilaAlista p2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por

-- ejemplo,

-- sublista [3,2] [5,3,2,7] == True

-- sublista [3,2] [5,3,7,2] == False

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

sublista xs ys =

any (xs `isPrefixOf`) (tails ys)

-- Comprobación de equivalencia

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

-- La propiedad es

prop_subPila :: Pila Int -> Pila Int -> Bool

prop_subPila p1 p2 =

subPila1 p1 p2 == subPila2 p1 p2

-- La comprobación es

-- λ> quickCheck prop_subPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.prefijoPila import prefijoPila
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 PrefijoPila del ejercicio
# "Reconocimiento de prefijos de pilas" que se encuentra en
# https://bit.ly/3Xqu7lo

def subPila1(p1: Pila[A], p2: Pila[A]) -> bool:
    if esVacia(p1):
        return True
    if esVacia(p2):
        return False
    cp1 = cima(p1)
    dp1 = desapila(p1)
    cp2 = cima(p2)
    dp2 = desapila(p2)
    if cp1 == cp2:
        return prefijoPila(dp1, dp2) or subPila1(p1, dp2)
    return subPila1(p1, dp2)

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

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

# sublista(xs, ys) se verifica si xs es una sublista de ys. Por
# ejemplo,
#    >>> sublista([3,2], [5,3,2,7])
#    True
#    >>> sublista([3,2], [5,3,7,2])
#    False
def sublista(xs: list[A], ys: list[A]) -> bool:
    return any(xs == ys[i:i+len(xs)] for i in range(len(ys) - len(xs) + 1))

def subPila2(p1: Pila[A], p2: Pila[A]) -> bool:
    return sublista(pilaAlista(p1), pilaAlista(p2))

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

def subPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:
    if p1.esVacia():
        return True
    if p2.esVacia():
        return False
    if p1.cima() != p2.cima():
        p2.desapila()
        return subPila3Aux(p1, p2)
    q1 = deepcopy(p1)
    p1.desapila()
    p2.desapila()
    return prefijoPila(p1, p2) or subPila3Aux(q1, p2)

def subPila3(p1: Pila[A], p2: Pila[A]) -> bool:
    q1 = deepcopy(p1)
    q2 = deepcopy(p2)
    return subPila3Aux(q1, q2)

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

# La propiedad es
@given(p1=pilaAleatoria(), p2=pilaAleatoria())
def test_subPila(p1: Pila[int], p2: Pila[int]) -> None:
    r = subPila1(p1, p2)
    assert subPila2(p1, p2) == r
    assert subPila3(p1, p2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.prefijoPila import prefijoPila

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 PrefijoPila del ejercicio

# "Reconocimiento de prefijos de pilas" que se encuentra en

# https://bit.ly/3Xqu7lo

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

if esVacia(p1):

return True

if esVacia(p2):

return False

cp1 = cima(p1)

dp1 = desapila(p1)

cp2 = cima(p2)

dp2 = desapila(p2)

if cp1 == cp2:

return prefijoPila(dp1, dp2) or subPila1(p1, dp2)

return subPila1(p1, dp2)

# 2ª solución

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

# Se usará la función pilaAlista del ejercicio

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

# https://bit.ly/3ZHewQ8

# sublista(xs, ys) se verifica si xs es una sublista de ys. Por

# ejemplo,

# >>> sublista([3,2], [5,3,2,7])

# True

# >>> sublista([3,2], [5,3,7,2])

# False

def sublista(xs: list[A], ys: list[A]) -> bool:

return any(xs == ys[i:i+len(xs)] for i in range(len(ys) - len(xs) + 1))

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

return sublista(pilaAlista(p1), pilaAlista(p2))

# 3ª solución

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

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

if p1.esVacia():

return True

if p2.esVacia():

return False

if p1.cima() != p2.cima():

p2.desapila()

return subPila3Aux(p1, p2)

q1 = deepcopy(p1)

p1.desapila()

p2.desapila()

return prefijoPila(p1, p2) or subPila3Aux(q1, p2)

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

q1 = deepcopy(p1)

q2 = deepcopy(p2)

return subPila3Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

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

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

r = subPila1(p1, p2)

assert subPila2(p1, p2) == r

assert subPila3(p1, p2) == r

# La comprobación es

# src> poetry run pytest -q subPila.py

# 1 passed in 0.32s

3. TAD de las pilas: Reconocimiento de ordenación de pilas

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

   ordenadaPila :: Ord a => Pila a -> Bool

1	ordenadaPila :: Ord a => Pila a -> Bool

tal que ordenadaPila p se verifica si los elementos de la pila p están ordenados en orden creciente. Por ejemplo,

   ordenadaPila (apila 1 (apila 5 (apila 6 vacia))) == True
   ordenadaPila (apila 1 (apila 0 (apila 6 vacia))) == False

1 2	ordenadaPila (apila 1 (apila 5 (apila 6 vacia))) == True ordenadaPila (apila 1 (apila 0 (apila 6 vacia))) == 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 Transformaciones_pilas_listas (pilaAlista)
import Test.QuickCheck

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

ordenadaPila :: Ord a => Pila a -> Bool
ordenadaPila p
  | esVacia p  = True
  | esVacia dp = True
  | otherwise  = cp <= cdp && ordenadaPila dp
  where cp  = cima p
        dp  = desapila p
        cdp = cima dp

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

ordenadaPila2 :: Ord a => Pila a -> Bool
ordenadaPila2 =
  ordenadaLista . reverse . pilaAlista

-- (ordenadaLista xs) se verifica si la lista xs está ordenada de menor
-- a mayor. Por ejemplo,
ordenadaLista :: Ord a => [a] -> Bool
ordenadaLista xs =
  and [x <= y | (x,y) <- zip xs (tail xs)]

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

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

-- La propiedad es
prop_ordenadaPila :: Pila Int -> Bool
prop_ordenadaPila p =
  ordenadaPila p == ordenadaPila2 p

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

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

import Transformaciones_pilas_listas (pilaAlista)

import Test.QuickCheck

-- 1ª solución

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

ordenadaPila :: Ord a => Pila a -> Bool

ordenadaPila p

| esVacia p = True

| esVacia dp = True

| otherwise = cp <= cdp && ordenadaPila dp

where cp = cima p

dp = desapila p

cdp = cima dp

-- 2ª solución

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

ordenadaPila2 :: Ord a => Pila a -> Bool

ordenadaPila2 =

ordenadaLista . reverse . pilaAlista

-- (ordenadaLista xs) se verifica si la lista xs está ordenada de menor

-- a mayor. Por ejemplo,

ordenadaLista :: Ord a => [a] -> Bool

ordenadaLista xs =

and [x <= y | (x,y) <- zip xs (tail xs)]

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

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

prop_ordenadaPila :: Pila Int -> Bool

prop_ordenadaPila p =

ordenadaPila p == ordenadaPila2 p

-- La comprobación es

-- λ> quickCheck prop_ordenadaPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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

A = TypeVar('A', int, float, str)

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

def ordenadaPila(p: Pila[A]) -> bool:
    if esVacia(p):
        return True
    cp = cima(p)
    dp = desapila(p)
    if esVacia(dp):
        return True
    cdp = cima(dp)
    return cp <= cdp and ordenadaPila(dp)

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

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

# ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por
# ejemplo,
#    >>> ordenadaLista([2, 5, 8])
#    True
#    >>> ordenadalista([2, 8, 5])
#    False
def ordenadaLista(xs: list[A]) -> bool:
    return all((x <= y for (x, y) in zip(xs, xs[1:])))

def ordenadaPila2(p: Pila[A]) -> bool:
    return ordenadaLista(list(reversed(pilaAlista(p))))

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

def ordenadaPila3Aux(p: Pila[A]) -> bool:
    if p.esVacia():
        return True
    cp = p.cima()
    p.desapila()
    if p.esVacia():
        return True
    return cp <= p.cima() and ordenadaPila3Aux(p)

def ordenadaPila3(p: Pila[A]) -> bool:
    q = deepcopy(p)
    return ordenadaPila3Aux(q)

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

def ordenadaPila4Aux(p: Pila[A]) -> bool:
    while not p.esVacia():
        cp = p.cima()
        p.desapila()
        if not p.esVacia() and cp > p.cima():
            return False
    return True

def ordenadaPila4(p: Pila[A]) -> bool:
    q = deepcopy(p)
    return ordenadaPila4Aux(q)

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

# La propiedad es
@given(p=pilaAleatoria())
def test_ordenadaPila(p: Pila[int]) -> None:
    r = ordenadaPila(p)
    assert ordenadaPila2(p) == r
    assert ordenadaPila3(p) == r
    assert ordenadaPila4(p) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

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

vacia)

from src.transformaciones_pilas_listas import pilaAlista

A = TypeVar('A', int, float, str)

# 1ª solución

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

def ordenadaPila(p: Pila[A]) -> bool:

if esVacia(p):

return True

cp = cima(p)

dp = desapila(p)

if esVacia(dp):

return True

cdp = cima(dp)

return cp <= cdp and ordenadaPila(dp)

# 2ª solución

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

# Se usará la función pilaAlista del ejercicio

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

# https://bit.ly/3ZHewQ8

# ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por

# ejemplo,

# >>> ordenadaLista([2, 5, 8])

# True

# >>> ordenadalista([2, 8, 5])

# False

def ordenadaLista(xs: list[A]) -> bool:

return all((x <= y for (x, y) in zip(xs, xs[1:])))

def ordenadaPila2(p: Pila[A]) -> bool:

return ordenadaLista(list(reversed(pilaAlista(p))))

# 3ª solución

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

def ordenadaPila3Aux(p: Pila[A]) -> bool:

if p.esVacia():

return True

cp = p.cima()

p.desapila()

if p.esVacia():

return True

return cp <= p.cima() and ordenadaPila3Aux(p)

def ordenadaPila3(p: Pila[A]) -> bool:

q = deepcopy(p)

return ordenadaPila3Aux(q)

# 4ª solución

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

def ordenadaPila4Aux(p: Pila[A]) -> bool:

while not p.esVacia():

cp = p.cima()

p.desapila()

if not p.esVacia() and cp > p.cima():

return False

return True

def ordenadaPila4(p: Pila[A]) -> bool:

q = deepcopy(p)

return ordenadaPila4Aux(q)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=pilaAleatoria())

def test_ordenadaPila(p: Pila[int]) -> None:

r = ordenadaPila(p)

assert ordenadaPila2(p) == r

assert ordenadaPila3(p) == r

assert ordenadaPila4(p) == r

# La comprobación es

# src> poetry run pytest -q ordenadaPila.py

# 1 passed in 0.31s

4. TAD de las pilas: Ordenación de pilas por inserción

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

   ordenaInserPila :: Ord a => Pila a -> Pila a

1	ordenaInserPila :: Ord a => Pila a -> Pila a

tal que ordenaInserPila p es la pila obtenida ordenando por inserción los los elementos de la pila p. Por ejemplo,

   λ> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia)))
   1 | 3 | 4

1 2	λ> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia))) 1 \| 3 \| 4

Comprobar con QuickCheck que la pila (ordenaInserPila p) está ordenada.

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 Transformaciones_pilas_listas (listaApila, pilaAlista)
import OrdenadaPila (ordenadaPila)
import Test.QuickCheck

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

ordenaInserPila1 :: Ord a => Pila a -> Pila a
ordenaInserPila1 p
  | esVacia p = p
  | otherwise = insertaPila cp (ordenaInserPila1 dp)
  where cp = cima p
        dp = desapila p

insertaPila :: Ord a => a -> Pila a -> Pila a
insertaPila x p
  | esVacia p = apila x p
  | x < cp    = apila x p
  | otherwise = apila cp (insertaPila x dp)
  where cp = cima p
        dp = desapila p

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

ordenaInserPila2 :: Ord a => Pila a -> Pila a
ordenaInserPila2  =
  listaApila . reverse . ordenaInserLista . pilaAlista

ordenaInserLista :: Ord a => [a] -> [a]
ordenaInserLista []      = []
ordenaInserLista (x: xs) = insertaLista x (ordenaInserLista xs)

insertaLista :: Ord a => a -> [a] -> [a]
insertaLista x [] = [x]
insertaLista x (y:ys) | x < y = x : y : ys
                      | otherwise = y : insertaLista x ys

-- Se usarán las funciones listaApila y pilaAlista del ejercicio
-- "Transformaciones entre pilas y listas" que se encuentra en
-- https://bit.ly/3ZHewQ8

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

-- La propiedad es
prop_ordenaInserPila :: Pila Int -> Bool
prop_ordenaInserPila p =
  ordenaInserPila1 p == ordenaInserPila2 p

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

-- Comprobación de la propiedad
-- ============================

-- Se usará la función ordenadaPila del ejercicio
-- "Reconocimiento de ordenación de pilas" que se encuentra en
-- https://bit.ly/3COqRbK

-- La propiedad es
prop_ordenadaOrdenaInserPila :: Pila Int -> Bool
prop_ordenadaOrdenaInserPila p =
  ordenadaPila (ordenaInserPila1 p)

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

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

import Transformaciones_pilas_listas (listaApila, pilaAlista)

import OrdenadaPila (ordenadaPila)

import Test.QuickCheck

-- 1ª solución

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

ordenaInserPila1 :: Ord a => Pila a -> Pila a

ordenaInserPila1 p

| esVacia p = p

| otherwise = insertaPila cp (ordenaInserPila1 dp)

where cp = cima p

dp = desapila p

insertaPila :: Ord a => a -> Pila a -> Pila a

insertaPila x p

| esVacia p = apila x p

| x < cp = apila x p

| otherwise = apila cp (insertaPila x dp)

where cp = cima p

dp = desapila p

-- 2ª solución

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

ordenaInserPila2 :: Ord a => Pila a -> Pila a

ordenaInserPila2 =

listaApila . reverse . ordenaInserLista . pilaAlista

ordenaInserLista :: Ord a => [a] -> [a]

ordenaInserLista [] = []

ordenaInserLista (x: xs) = insertaLista x (ordenaInserLista xs)

insertaLista :: Ord a => a -> [a] -> [a]

insertaLista x [] = [x]

insertaLista x (y:ys) | x < y = x : y : ys

| otherwise = y : insertaLista x ys

-- Se usarán las funciones listaApila y pilaAlista del ejercicio

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

prop_ordenaInserPila :: Pila Int -> Bool

prop_ordenaInserPila p =

ordenaInserPila1 p == ordenaInserPila2 p

-- La comprobación es

-- λ> quickCheck prop_ordenaInserPila

-- +++ OK, passed 100 tests.

-- Comprobación de la propiedad

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

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

-- "Reconocimiento de ordenación de pilas" que se encuentra en

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

-- La propiedad es

prop_ordenadaOrdenaInserPila :: Pila Int -> Bool

prop_ordenadaOrdenaInserPila p =

ordenadaPila (ordenaInserPila1 p)

-- La comprobación es

-- λ> quickCheck prop_ordenadaOrdenaInserPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

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

A = TypeVar('A', int, float, str)

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

def insertaPila(x: A, p: Pila[A]) -> Pila[A]:
    if esVacia(p):
        return apila(x, p)
    cp = cima(p)
    if x < cp:
        return apila(x, p)
    dp = desapila(p)
    return apila(cp, insertaPila(x, dp))

def ordenaInserPila1(p: Pila[A]) -> Pila[A]:
    if esVacia(p):
        return p
    cp = cima(p)
    dp = desapila(p)
    return insertaPila(cp, ordenaInserPila1(dp))

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

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

def insertaLista(x: A, ys: list[A]) -> list[A]:
    if not ys:
        return [x]
    if x < ys[0]:
        return [x] + ys
    return [ys[0]] + insertaLista(x, ys[1:])

def ordenaInserLista(xs: list[A]) -> list[A]:
    if not xs:
        return []
    return insertaLista(xs[0], ordenaInserLista(xs[1:]))

def ordenaInserPila2(p: Pila[A]) -> Pila[A]:
    return listaApila(list(reversed(ordenaInserLista(pilaAlista(p)))))

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

def ordenaInserPila3Aux(p: Pila[A]) -> Pila[A]:
    if p.esVacia():
        return p
    cp = p.cima()
    p.desapila()
    return insertaPila(cp, ordenaInserPila3Aux(p))

def ordenaInserPila3(p: Pila[A]) -> Pila[A]:
    q = deepcopy(p)
    return ordenaInserPila3Aux(q)

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

# La propiedad es
@given(p=pilaAleatoria())
def test_ordenaInserPila(p: Pila[int]) -> None:
    r = ordenaInserPila1(p)
    assert ordenaInserPila2(p) == r
    assert ordenaInserPila3(p) == r

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

# Comprobación de la propiedad
# ============================

# Se usará la función ordenadaPila del ejercicio
# "Reconocimiento de ordenación de pilas" que se encuentra en
# https://bit.ly/3COqRbK

# La propiedad es
@given(p=pilaAleatoria())
def test_ordenadaOrdenaInserPila(p: Pila[int]) -> None:
    ordenadaPila(ordenaInserPila1(p))

# La comprobación es
#    src> poetry run pytest -q ordenaInserPila.py
#    2 passed in 0.47s

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.ordenadaPila import ordenadaPila

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

vacia)

from src.transformaciones_pilas_listas import listaApila, pilaAlista

A = TypeVar('A', int, float, str)

# 1ª solución

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

def insertaPila(x: A, p: Pila[A]) -> Pila[A]:

if esVacia(p):

return apila(x, p)

cp = cima(p)

if x < cp:

return apila(x, p)

dp = desapila(p)

return apila(cp, insertaPila(x, dp))

def ordenaInserPila1(p: Pila[A]) -> Pila[A]:

if esVacia(p):

return p

cp = cima(p)

dp = desapila(p)

return insertaPila(cp, ordenaInserPila1(dp))

# 2ª solución

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

# Se usarán las funciones listaApila y pilaAlista del ejercicio

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

# https://bit.ly/3ZHewQ8

def insertaLista(x: A, ys: list[A]) -> list[A]:

if not ys:

return [x]

if x < ys[0]:

return [x] + ys

return [ys[0]] + insertaLista(x, ys[1:])

def ordenaInserLista(xs: list[A]) -> list[A]:

if not xs:

return []

return insertaLista(xs[0], ordenaInserLista(xs[1:]))

def ordenaInserPila2(p: Pila[A]) -> Pila[A]:

return listaApila(list(reversed(ordenaInserLista(pilaAlista(p)))))

# 3ª solución

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

def ordenaInserPila3Aux(p: Pila[A]) -> Pila[A]:

if p.esVacia():

return p

cp = p.cima()

p.desapila()

return insertaPila(cp, ordenaInserPila3Aux(p))

def ordenaInserPila3(p: Pila[A]) -> Pila[A]:

q = deepcopy(p)

return ordenaInserPila3Aux(q)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=pilaAleatoria())

def test_ordenaInserPila(p: Pila[int]) -> None:

r = ordenaInserPila1(p)

assert ordenaInserPila2(p) == r

assert ordenaInserPila3(p) == r

# La comprobación es

# src> poetry run pytest -q ordenaInserPila.py

# 1 passed in 0.31s

# Comprobación de la propiedad

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

# Se usará la función ordenadaPila del ejercicio

# "Reconocimiento de ordenación de pilas" que se encuentra en

# https://bit.ly/3COqRbK

# La propiedad es

@given(p=pilaAleatoria())

def test_ordenadaOrdenaInserPila(p: Pila[int]) -> None:

ordenadaPila(ordenaInserPila1(p))

# La comprobación es

# src> poetry run pytest -q ordenaInserPila.py

# 2 passed in 0.47s

5. TAD de las pilas: Eliminación de repeticiones en una pila

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

   nubPila :: Eq a => Pila a -> Pila a

1	nubPila :: Eq a => Pila a -> Pila a

tal que nubPila p es la pila con los elementos de p sin repeticiones. Por ejemplo,

   λ> nubPila (apila 3 (apila 1 (apila 3 (apila 5 vacia))))
   1 | 3 | 5

1 2	λ> nubPila (apila 3 (apila 1 (apila 3 (apila 5 vacia)))) 1 \| 3 \| 5

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 Transformaciones_pilas_listas (listaApila, pilaAlista)
import PertenecePila (pertenecePila)
import Data.List (nub)
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

nubPila1 :: Eq a => Pila a -> Pila a
nubPila1 p
  | esVacia p           = vacia
  | pertenecePila cp dp = nubPila1 dp
  | otherwise           = apila cp (nubPila1 dp)
  where cp = cima p
        dp = desapila p

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

-- Se usarán las funciones listaApila y pilaAlista del ejercicio
-- "Transformaciones entre pilas y listas" que se encuentra en
-- https://bit.ly/3ZHewQ8

nubPila2 :: Eq a => Pila a -> Pila a
nubPila2 =
  listaApila . nub . pilaAlista

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

-- La propiedad es
prop_nubPila :: Pila Int -> Bool
prop_nubPila p =
  nubPila1 p == nubPila2 p

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

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

import Transformaciones_pilas_listas (listaApila, pilaAlista)

import PertenecePila (pertenecePila)

import Data.List (nub)

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

nubPila1 :: Eq a => Pila a -> Pila a

nubPila1 p

| esVacia p = vacia

| pertenecePila cp dp = nubPila1 dp

| otherwise = apila cp (nubPila1 dp)

where cp = cima p

dp = desapila p

-- 2ª solución

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

-- Se usarán las funciones listaApila y pilaAlista del ejercicio

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

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

nubPila2 :: Eq a => Pila a -> Pila a

nubPila2 =

listaApila . nub . pilaAlista

-- Comprobación de equivalencia

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

-- La propiedad es

prop_nubPila :: Pila Int -> Bool

prop_nubPila p =

nubPila1 p == nubPila2 p

-- La comprobación es

-- λ> quickCheck prop_nubPila

-- +++ 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 listaApila, 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 nubPila1(p: Pila[A]) -> Pila[A]:
    if esVacia(p):
        return p
    cp = cima(p)
    dp = desapila(p)
    if pertenecePila(cp, dp):
        return nubPila1(dp)
    return apila(cp, nubPila1(dp))

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

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

def nub(xs: list[A]) -> list[A]:
    return [x for i, x in enumerate(xs) if x not in xs[:i]]

def nubPila2(p: Pila[A]) -> Pila[A]:
    return listaApila(nub(pilaAlista(p)))

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

def nubPila3Aux(p: Pila[A]) -> Pila[A]:
    if p.esVacia():
        return p
    cp = p.cima()
    p.desapila()
    if pertenecePila(cp, p):
        return nubPila3Aux(p)
    return apila(cp, nubPila3Aux(p))

def nubPila3(p: Pila[A]) -> Pila[A]:
    q = deepcopy(p)
    return nubPila3Aux(q)

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

# La propiedad es
@given(p=pilaAleatoria())
def test_nubPila(p: Pila[int]) -> None:
    r = nubPila1(p)
    assert nubPila2(p) == r
    assert nubPila3(p) == r

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

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 listaApila, 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 nubPila1(p: Pila[A]) -> Pila[A]:

if esVacia(p):

return p

cp = cima(p)

dp = desapila(p)

if pertenecePila(cp, dp):

return nubPila1(dp)

return apila(cp, nubPila1(dp))

# 2ª solución

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

# Se usarán las funciones listaApila y pilaAlista del ejercicio

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

# https://bit.ly/3ZHewQ8

def nub(xs: list[A]) -> list[A]:

return [x for i, x in enumerate(xs) if x not in xs[:i]]

def nubPila2(p: Pila[A]) -> Pila[A]:

return listaApila(nub(pilaAlista(p)))

# 3ª solución

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

def nubPila3Aux(p: Pila[A]) -> Pila[A]:

if p.esVacia():

return p

cp = p.cima()

p.desapila()

if pertenecePila(cp, p):

return nubPila3Aux(p)

return apila(cp, nubPila3Aux(p))

def nubPila3(p: Pila[A]) -> Pila[A]:

q = deepcopy(p)

return nubPila3Aux(q)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=pilaAleatoria())

def test_nubPila(p: Pila[int]) -> None:

r = nubPila1(p)

assert nubPila2(p) == r

assert nubPila3(p) == r

# La comprobación es

# src> poetry run pytest -q nubPila.py

# 1 passed in 0.27s

1. TAD de las pilas: Reconocimiento de prefijos de pilas

2. TAD de las pilas: Reconocimiento de subpilas

3. TAD de las pilas: Reconocimiento de ordenación de pilas

4. TAD de las pilas: Ordenación de pilas por inserción

5. TAD de las pilas: Eliminación de repeticiones en una pila

Se puede imprimir o compartir con