Pilas

TAD de las pilas: Máximo elemento de una pila

PorJosé A. Alonso 6-febrero-202322-enero-2023

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

   maxPila :: Ord a => Pila a -> a

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

tal que maxPila p sea el mayor de los elementos de la pila p. Por ejemplo,

   λ> maxPila (apila 3 (apila 5 (apila 1 vacia)))
   5

1 2	λ> maxPila (apila 3 (apila 5 (apila 1 vacia))) 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 (pilaAlista)
import Test.QuickCheck

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

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

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

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

maxPila2 :: Ord a => Pila a -> a
maxPila2 =
  maximum . pilaAlista

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

-- La propiedad es
prop_maxPila :: Pila Int -> Property
prop_maxPila p =
  not (esVacia p) ==> maxPila1 p == maxPila2 p

-- La comprobación es
--    λ> quickCheck prop_maxPila
--    +++ OK, passed 100 tests; 17 discarded.

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

import Transformaciones_pilas_listas (pilaAlista)

import Test.QuickCheck

-- 1ª solución

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

maxPila1 :: Ord a => Pila a -> a

maxPila1 p

| esVacia dp = cp

| otherwise = max cp (maxPila1 dp)

where cp = cima p

dp = desapila p

-- 2ª solución

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

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

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

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

maxPila2 :: Ord a => Pila a -> a

maxPila2 =

maximum . pilaAlista

-- Comprobación de equivalencia

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

-- La propiedad es

prop_maxPila :: Pila Int -> Property

prop_maxPila p =

not (esVacia p) ==> maxPila1 p == maxPila2 p

-- La comprobación es

-- λ> quickCheck prop_maxPila

-- +++ OK, passed 100 tests; 17 discarded.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import assume, 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 maxPila1(p: Pila[A]) -> A:
    cp = cima(p)
    dp = desapila(p)
    if esVacia(dp):
        return cp
    return max(cp, maxPila1(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

def maxPila2(p: Pila[A]) -> A:
    return max(pilaAlista(p))

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

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

def maxPila3(p: Pila[A]) -> A:
    q = deepcopy(p)
    return maxPila3Aux(q)

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

def maxPila4Aux(p: Pila[A]) -> A:
    r = p.cima()
    while not esVacia(p):
        cp = p.cima()
        if cp > r:
            r = cp
        p.desapila()
    return r

def maxPila4(p: Pila[A]) -> A:
    q = deepcopy(p)
    return maxPila4Aux(q)

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

# La propiedad es
@given(p=pilaAleatoria())
def test_maxPila(p: Pila[int]) -> None:
    assume(not esVacia(p))
    r = maxPila1(p)
    assert maxPila2(p) == r
    assert maxPila3(p) == r
    assert maxPila4(p) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import assume, 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 maxPila1(p: Pila[A]) -> A:

cp = cima(p)

dp = desapila(p)

if esVacia(dp):

return cp

return max(cp, maxPila1(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

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

return max(pilaAlista(p))

# 3ª solución

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

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

cp = p.cima()

p.desapila()

if esVacia(p):

return cp

return max(cp, maxPila3Aux(p))

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

q = deepcopy(p)

return maxPila3Aux(q)

# 4ª solución

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

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

r = p.cima()

while not esVacia(p):

cp = p.cima()

if cp > r:

r = cp

p.desapila()

return r

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

q = deepcopy(p)

return maxPila4Aux(q)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=pilaAleatoria())

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

assume(not esVacia(p))

r = maxPila1(p)

assert maxPila2(p) == r

assert maxPila3(p) == r

assert maxPila4(p) == r

# La comprobación es

# src> poetry run pytest -q maxPila.py

# 1 passed in 0.25s

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

PorJosé A. Alonso 3-febrero-202322-enero-2023

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

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

PorJosé A. Alonso 2-febrero-202322-enero-2023

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

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

PorJosé A. Alonso 1-febrero-202322-enero-2023

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

TAD de las pilas: Reconocimiento de subpilas

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

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

TAD de las pilas: Máximo elemento de una pila

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

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

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

TAD de las pilas: Reconocimiento de subpilas

Entradas recientes

Buscar

Correo electrónico