La semana en Exercitium (25 de febrero de 2023)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sobre el tipo abstracto de las colas.

1. Pertenencia a una cola
2. Inclusión de colas
3. Reconocimiento de prefijos de colas
4. Reconocimiento de subcolas
5. Reconocimiento de ordenación de colas

A continuación se muestran las soluciones.

1. Pertenencia a una cola

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

   perteneceCola :: Eq a => a -> Cola a -> Bool

1	perteneceCola :: Eq a => a -> Cola a -> Bool

tal que perteneceCola x c se verifica si x es un elemento de la cola c. Por ejemplo,

   perteneceCola 2 (inserta 5 (inserta 2 (inserta 3 vacia))) == True
   perteneceCola 4 (inserta 5 (inserta 2 (inserta 3 vacia))) == False

1 2	perteneceCola 2 (inserta 5 (inserta 2 (inserta 3 vacia))) == True perteneceCola 4 (inserta 5 (inserta 2 (inserta 3 vacia))) == False

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia)
import Transformaciones_colas_listas colaAlista
import Test.QuickCheck

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

perteneceCola :: Eq a => a -> Cola a -> Bool
perteneceCola x c
  | esVacia c = False
  | otherwise = x == primero(c) || perteneceCola x (resto c)

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

perteneceCola2 :: Eq a => a -> Cola a -> Bool
perteneceCola2 x c =
  x `elem` colaAlista c

-- La función colaAlista está definida en el ejercicio
-- "Transformaciones entre colas y listas" que se encuentra en
-- https://bit.ly/3Xv0oIt

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

-- La propiedad es
prop_perteneceCola :: Int -> Cola Int -> Bool
prop_perteneceCola x p =
  perteneceCola x p == perteneceCola2 x p

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

import TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia)

import Transformaciones_colas_listas colaAlista

import Test.QuickCheck

-- 1ª solución

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

perteneceCola :: Eq a => a -> Cola a -> Bool

perteneceCola x c

| esVacia c = False

| otherwise = x == primero(c) || perteneceCola x (resto c)

-- 2ª solución

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

perteneceCola2 :: Eq a => a -> Cola a -> Bool

perteneceCola2 x c =

x `elem` colaAlista c

-- La función colaAlista está definida en el ejercicio

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

prop_perteneceCola :: Int -> Cola Int -> Bool

prop_perteneceCola x p =

perteneceCola x p == perteneceCola2 x p

-- La comprobación es

-- λ> quickCheck prop_perteneceCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.cola import (Cola, vacia, inserta, primero, resto, esVacia,
                          colaAleatoria)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def perteneceCola(x: A, c: Cola[A]) -> bool:
    if esVacia(c):
        return False
    return x == primero(c) or perteneceCola(x, resto(c))

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

def perteneceCola2(x: A, c: Cola[A]) -> bool:
    return x in colaAlista(c)

# Las función colaAlista está definida en el ejercicio
# "Transformaciones entre colas y listas" que se encuentra en
# https://bit.ly/3Xv0oIt

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

def perteneceCola3Aux(x: A, c: Cola[A]) -> bool:
    if c.esVacia():
        return False
    pc = c.primero()
    c.resto()
    return x == pc or perteneceCola3Aux(x, c)

def perteneceCola3(x: A, c: Cola[A]) -> bool:
    c1 = deepcopy(c)
    return perteneceCola3Aux(x, c1)

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

def perteneceCola4Aux(x: A, c: Cola[A]) -> bool:
    while not c.esVacia():
        pc = c.primero()
        c.resto()
        if x == pc:
            return True
    return False

def perteneceCola4(x: A, c: Cola[A]) -> bool:
    c1 = deepcopy(c)
    return perteneceCola4Aux(x, c1)

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

# La propiedad es
@given(x=st.integers(), c=colaAleatoria())
def test_perteneceCola(x: int, c: Cola[int]) -> None:
    r = perteneceCola(x, c)
    assert perteneceCola2(x, c) == r
    assert perteneceCola3(x, c) == r
    assert perteneceCola4(x, c) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.cola import (Cola, vacia, inserta, primero, resto, esVacia,

colaAleatoria)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def perteneceCola(x: A, c: Cola[A]) -> bool:

if esVacia(c):

return False

return x == primero(c) or perteneceCola(x, resto(c))

# 2ª solución

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

def perteneceCola2(x: A, c: Cola[A]) -> bool:

return x in colaAlista(c)

# Las función colaAlista está definida en el ejercicio

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def perteneceCola3Aux(x: A, c: Cola[A]) -> bool:

if c.esVacia():

return False

pc = c.primero()

c.resto()

return x == pc or perteneceCola3Aux(x, c)

def perteneceCola3(x: A, c: Cola[A]) -> bool:

c1 = deepcopy(c)

return perteneceCola3Aux(x, c1)

# 4ª solución

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

def perteneceCola4Aux(x: A, c: Cola[A]) -> bool:

while not c.esVacia():

pc = c.primero()

c.resto()

if x == pc:

return True

return False

def perteneceCola4(x: A, c: Cola[A]) -> bool:

c1 = deepcopy(c)

return perteneceCola4Aux(x, c1)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(x=st.integers(), c=colaAleatoria())

def test_perteneceCola(x: int, c: Cola[int]) -> None:

r = perteneceCola(x, c)

assert perteneceCola2(x, c) == r

assert perteneceCola3(x, c) == r

assert perteneceCola4(x, c) == r

# La comprobación es

# src> poetry run pytest -q perteneceCola.py

# 1 passed in 0.25s

2. Inclusión de colas

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

   contenidaCola :: Eq a => Cola a -> Cola a -> Bool

1	contenidaCola :: Eq a => Cola a -> Cola a -> Bool

tal que contenidaCola c1 c2 se verifica si todos los elementos de la cola c1 son elementos de la cola c2. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 2 vacia)
   λ> ej2 = inserta 3 (inserta 4 vacia)
   λ> ej3 = inserta 5 (inserta 2 (inserta 3 vacia))
   λ> contenidaCola ej1 ej3
   True
   λ> contenidaCola ej2 ej3
   False

λ> ej1 = inserta 3 (inserta 2 vacia)

λ> ej2 = inserta 3 (inserta 4 vacia)

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

λ> contenidaCola ej1 ej3

True

λ> contenidaCola ej2 ej3

False

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)
import PerteneceCola (perteneceCola)
import Transformaciones_colas_listas (colaAlista)
import Test.QuickCheck

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

contenidaCola1 :: Eq a => Cola a -> Cola a -> Bool
contenidaCola1 c1 c2
  | esVacia c1 = True
  | otherwise  = perteneceCola (primero c1) c2 &&
                 contenidaCola1 (resto c1) c2

-- La función perteneceCola está definida en el ejercicio
-- "Pertenencia a una cola" que se encuentra en
-- https://bit.ly/3RcVgqb

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

contenidaCola2 :: Eq a => Cola a -> Cola a -> Bool
contenidaCola2 c1 c2 =
  contenidaLista (colaAlista c1) (colaAlista c2)

-- La función colaAlista está definida en el ejercicio
-- "Transformaciones entre colas y listas" que se
-- encuentra en https://bit.ly/3Xv0oIt

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

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

-- La propiedad es
prop_contenidaCola :: Cola Int -> Cola Int -> Bool
prop_contenidaCola c1 c2 =
  contenidaCola1 c1 c2 == contenidaCola2 c1 c2

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

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)

import PerteneceCola (perteneceCola)

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

contenidaCola1 :: Eq a => Cola a -> Cola a -> Bool

contenidaCola1 c1 c2

| esVacia c1 = True

| otherwise = perteneceCola (primero c1) c2 &&

contenidaCola1 (resto c1) c2

-- La función perteneceCola está definida en el ejercicio

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

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

-- 2ª solución

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

contenidaCola2 :: Eq a => Cola a -> Cola a -> Bool

contenidaCola2 c1 c2 =

contenidaLista (colaAlista c1) (colaAlista c2)

-- La función colaAlista está definida en el ejercicio

-- "Transformaciones entre colas y listas" que se

-- encuentra en https://bit.ly/3Xv0oIt

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

contenidaLista xs ys =

all (`elem` ys) xs

-- Comprobación de equivalencia

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

-- La propiedad es

prop_contenidaCola :: Cola Int -> Cola Int -> Bool

prop_contenidaCola c1 c2 =

contenidaCola1 c1 c2 == contenidaCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_contenidaCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.perteneceCola import perteneceCola
from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def contenidaCola1(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    return perteneceCola(primero(c1), c2) and contenidaCola1(resto(c1), c2)

# L función perteneceCola está definida en el ejercicio
# "Pertenencia a una cola" que se encuentra en
# https://bit.ly/3RcVgqb

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

def contenidaCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return set(colaAlista(c1)) <= set(colaAlista(c2))

# La función colaAlista está definida en el ejercicio
# "Transformaciones entre colas y listas" que se encuentra en
# https://bit.ly/3Xv0oIt

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

def contenidaCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    pc1 = c1.primero()
    c1.resto()
    return perteneceCola(pc1, c2) and contenidaCola1(c1, c2)

def contenidaCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    _c1 = deepcopy(c1)
    return contenidaCola3Aux(_c1, c2)

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

def contenidaCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    while not c1.esVacia():
        pc1 = c1.primero()
        c1.resto()
        if not perteneceCola(pc1, c2):
            return False
    return True

def contenidaCola4(c1: Cola[A], c2: Cola[A]) -> bool:
    _c1 = deepcopy(c1)
    return contenidaCola4Aux(_c1, c2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_contenidaCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = contenidaCola1(c1, c2)
    assert contenidaCola2(c1, c2) == r
    assert contenidaCola3(c1, c2) == r
    assert contenidaCola4(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.perteneceCola import perteneceCola

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def contenidaCola1(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

return perteneceCola(primero(c1), c2) and contenidaCola1(resto(c1), c2)

# L función perteneceCola está definida en el ejercicio

# "Pertenencia a una cola" que se encuentra en

# https://bit.ly/3RcVgqb

# 2ª solución

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

def contenidaCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return set(colaAlista(c1)) <= set(colaAlista(c2))

# La función colaAlista está definida en el ejercicio

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def contenidaCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

pc1 = c1.primero()

c1.resto()

return perteneceCola(pc1, c2) and contenidaCola1(c1, c2)

def contenidaCola3(c1: Cola[A], c2: Cola[A]) -> bool:

_c1 = deepcopy(c1)

return contenidaCola3Aux(_c1, c2)

# 4ª solución

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

def contenidaCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:

while not c1.esVacia():

pc1 = c1.primero()

c1.resto()

if not perteneceCola(pc1, c2):

return False

return True

def contenidaCola4(c1: Cola[A], c2: Cola[A]) -> bool:

_c1 = deepcopy(c1)

return contenidaCola4Aux(_c1, c2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_contenidaCola(c1: Cola[int], c2: Cola[int]) -> None:

r = contenidaCola1(c1, c2)

assert contenidaCola2(c1, c2) == r

assert contenidaCola3(c1, c2) == r

assert contenidaCola4(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q contenidaCola.py

# 1 passed in 0.44s

3. Reconocimiento de prefijos de colas

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

   prefijoCola :: Eq a => Cola a -> Cola a -> Bool

1	prefijoCola :: Eq a => Cola a -> Cola a -> Bool

tal que prefijoCola c1 c2 se verifica si la cola c1 es justamente un prefijo de la cola c2. Por ejemplo,

   λ> ej1 = inserta 4 (inserta 2 vacia)
   λ> ej2 = inserta 5 (inserta 4 (inserta 2 vacia))
   λ> ej3 = inserta 5 (inserta 2 (inserta 4 vacia))
   λ> prefijoCola ej1 ej2
   True
   λ> prefijoCola ej1 ej3
   False

λ> ej1 = inserta 4 (inserta 2 vacia)

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

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

λ> prefijoCola ej1 ej2

True

λ> prefijoCola ej1 ej3

False

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)
import Transformaciones_colas_listas (colaAlista)
import Data.List (isPrefixOf)
import Test.QuickCheck

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

prefijoCola :: Eq a => Cola a -> Cola a -> Bool
prefijoCola c1 c2
  | esVacia c1 = True
  | esVacia c2 = False
  | otherwise  = primero c1 == primero c2 &&
                 prefijoCola (resto c1) (resto c2)

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

prefijoCola2 :: Eq a => Cola a -> Cola a -> Bool
prefijoCola2 c1 c2 =
  colaAlista c1 `isPrefixOf` colaAlista c2

-- La función colaAlista está definida en el ejercicio
-- "Transformaciones entre colas y listas" que se encuentra en
-- https://bit.ly/3Xv0oIt

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

-- La propiedad es
prop_prefijoCola :: Cola Int -> Cola Int -> Bool
prop_prefijoCola c1 c2 =
  prefijoCola c1 c2 == prefijoCola2 c1 c2

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

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)

import Transformaciones_colas_listas (colaAlista)

import Data.List (isPrefixOf)

import Test.QuickCheck

-- 1ª solución

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

prefijoCola :: Eq a => Cola a -> Cola a -> Bool

prefijoCola c1 c2

| esVacia c1 = True

| esVacia c2 = False

| otherwise = primero c1 == primero c2 &&

prefijoCola (resto c1) (resto c2)

-- 2ª solución

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

prefijoCola2 :: Eq a => Cola a -> Cola a -> Bool

prefijoCola2 c1 c2 =

colaAlista c1 `isPrefixOf` colaAlista c2

-- La función colaAlista está definida en el ejercicio

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

prop_prefijoCola :: Cola Int -> Cola Int -> Bool

prop_prefijoCola c1 c2 =

prefijoCola c1 c2 == prefijoCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_prefijoCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def prefijoCola(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    if esVacia(c2):
        return False
    return primero(c1) == primero(c2) and prefijoCola(resto(c1), resto(c2))

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

def esPrefijoLista(xs: list[A], ys: list[A]) -> bool:
    return ys[:len(xs)] == xs

def prefijoCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return esPrefijoLista(colaAlista(c1), colaAlista(c2))

# La función colaAlista está definida en el ejercicio
# "Transformaciones entre colas y listas" que se encuentra en
# https://bit.ly/3Xv0oIt

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

def prefijoCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    if c2.esVacia():
        return False
    cc1 = c1.primero()
    c1.resto()
    cc2 = c2.primero()
    c2.resto()
    return cc1 == cc2 and prefijoCola3(c1, c2)

def prefijoCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return prefijoCola3Aux(q1, q2)

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

def prefijoCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    while not c2.esVacia() and not c1.esVacia():
        if c1.primero() != c2.primero():
            return False
        c1.resto()
        c2.resto()
    return c1.esVacia()

def prefijoCola4(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return prefijoCola4Aux(q1, q2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_prefijoCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = prefijoCola(c1, c2)
    assert prefijoCola2(c1, c2) == r
    assert prefijoCola3(c1, c2) == r
    assert prefijoCola4(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def prefijoCola(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

if esVacia(c2):

return False

return primero(c1) == primero(c2) and prefijoCola(resto(c1), resto(c2))

# 2ª solución

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

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

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

def prefijoCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return esPrefijoLista(colaAlista(c1), colaAlista(c2))

# La función colaAlista está definida en el ejercicio

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def prefijoCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

if c2.esVacia():

return False

cc1 = c1.primero()

c1.resto()

cc2 = c2.primero()

c2.resto()

return cc1 == cc2 and prefijoCola3(c1, c2)

def prefijoCola3(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return prefijoCola3Aux(q1, q2)

# 4ª solución

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

def prefijoCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool:

while not c2.esVacia() and not c1.esVacia():

if c1.primero() != c2.primero():

return False

c1.resto()

c2.resto()

return c1.esVacia()

def prefijoCola4(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return prefijoCola4Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_prefijoCola(c1: Cola[int], c2: Cola[int]) -> None:

r = prefijoCola(c1, c2)

assert prefijoCola2(c1, c2) == r

assert prefijoCola3(c1, c2) == r

assert prefijoCola4(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q prefijoCola.py

# 1 passed in 0.29s

4. Reconocimiento de subcolas

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

   subCola :: Eq a => Cola a -> Cola a -> Bool

1	subCola :: Eq a => Cola a -> Cola a -> Bool

tal que subCola c1 c2 se verifica si c1 es una subcola de c2. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 3 vacia)
   λ> ej2 = inserta 7 (inserta 2 (inserta 3 (inserta 5 vacia)))
   λ> ej3 = inserta 2 (inserta 7 (inserta 3 (inserta 5 vacia)))
   λ> subCola ej1 ej2
   True
   λ> subCola ej1 ej3
   False

λ> ej1 = inserta 2 (inserta 3 vacia)

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

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

λ> subCola ej1 ej2

True

λ> subCola ej1 ej3

False

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)
import Transformaciones_colas_listas (colaAlista)
import PrefijoCola (prefijoCola)
import Data.List (isPrefixOf, tails)
import Test.QuickCheck

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

subCola1 :: Eq a => Cola a -> Cola a -> Bool
subCola1 c1 c2
    | esVacia c1 = True
    | esVacia c2 = False
    | pc1 == pc2 = prefijoCola rc1 rc2 || subCola1 c1 rc2
    | otherwise  = subCola1 c1 rc2
    where pc1 = primero c1
          rc1 = resto c1
          pc2 = primero c2
          rc2 = resto c2

-- La función PrefijoCola está definida en el ejercicio
-- "Reconocimiento de prefijos de colas" que se encuentra en
-- https://bit.ly/3HaK20x

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

subCola2 :: Eq a => Cola a -> Cola a -> Bool
subCola2 c1 c2 =
  sublista (colaAlista c1) (colaAlista c2)

-- La función colaAlista está definida en el ejercicio
-- "Transformaciones entre colas y listas" que se encuentra en
-- https://bit.ly/3Xv0oIt

-- (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_subCola :: Cola Int -> Cola Int -> Bool
prop_subCola c1 c2 =
  subCola1 c1 c2 == subCola2 c1 c2

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

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)

import Transformaciones_colas_listas (colaAlista)

import PrefijoCola (prefijoCola)

import Data.List (isPrefixOf, tails)

import Test.QuickCheck

-- 1ª solución

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

subCola1 :: Eq a => Cola a -> Cola a -> Bool

subCola1 c1 c2

| esVacia c1 = True

| esVacia c2 = False

| pc1 == pc2 = prefijoCola rc1 rc2 || subCola1 c1 rc2

| otherwise = subCola1 c1 rc2

where pc1 = primero c1

rc1 = resto c1

pc2 = primero c2

rc2 = resto c2

-- La función PrefijoCola está definida en el ejercicio

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

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

-- 2ª solución

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

subCola2 :: Eq a => Cola a -> Cola a -> Bool

subCola2 c1 c2 =

sublista (colaAlista c1) (colaAlista c2)

-- La función colaAlista está definida en el ejercicio

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

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

-- (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_subCola :: Cola Int -> Cola Int -> Bool

prop_subCola c1 c2 =

subCola1 c1 c2 == subCola2 c1 c2

-- La comprobación es

-- λ> quickCheck prop_subCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.prefijoCola import prefijoCola
from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

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

def subCola1(c1: Cola[A], c2: Cola[A]) -> bool:
    if esVacia(c1):
        return True
    if esVacia(c2):
        return False
    pc1 = primero(c1)
    rc1 = resto(c1)
    pc2 = primero(c2)
    rc2 = resto(c2)
    if pc1 == pc2:
        return prefijoCola(rc1, rc2) or subCola1(c1, rc2)
    return subCola1(c1, rc2)

# La función prefijoCola está definida en el ejercicio
# "Reconocimiento de prefijos de colas" que se encuentra en
# https://bit.ly/3HaK20x

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

# 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 subCola2(c1: Cola[A], c2: Cola[A]) -> bool:
    return sublista(colaAlista(c1), colaAlista(c2))

# La función colaAlista está definida en el ejercicio
# "Transformaciones entre colas y listas" que se encuentra en
# https://bit.ly/3Xv0oIt

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

def subCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:
    if c1.esVacia():
        return True
    if c2.esVacia():
        return False
    if c1.primero() != c2.primero():
        c2.resto()
        return subCola3Aux(c1, c2)
    q1 = deepcopy(c1)
    c1.resto()
    c2.resto()
    return prefijoCola(c1, c2) or subCola3Aux(q1, c2)

def subCola3(c1: Cola[A], c2: Cola[A]) -> bool:
    q1 = deepcopy(c1)
    q2 = deepcopy(c2)
    return subCola3Aux(q1, q2)

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

# La propiedad es
@given(c1=colaAleatoria(), c2=colaAleatoria())
def test_subCola(c1: Cola[int], c2: Cola[int]) -> None:
    r = subCola1(c1, c2)
    assert subCola2(c1, c2) == r
    assert subCola3(c1, c2) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.prefijoCola import prefijoCola

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

A = TypeVar('A')

# 1ª solución

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

def subCola1(c1: Cola[A], c2: Cola[A]) -> bool:

if esVacia(c1):

return True

if esVacia(c2):

return False

pc1 = primero(c1)

rc1 = resto(c1)

pc2 = primero(c2)

rc2 = resto(c2)

if pc1 == pc2:

return prefijoCola(rc1, rc2) or subCola1(c1, rc2)

return subCola1(c1, rc2)

# La función prefijoCola está definida en el ejercicio

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

# https://bit.ly/3HaK20x

# 2ª solución

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

# 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 subCola2(c1: Cola[A], c2: Cola[A]) -> bool:

return sublista(colaAlista(c1), colaAlista(c2))

# La función colaAlista está definida en el ejercicio

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def subCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool:

if c1.esVacia():

return True

if c2.esVacia():

return False

if c1.primero() != c2.primero():

c2.resto()

return subCola3Aux(c1, c2)

q1 = deepcopy(c1)

c1.resto()

c2.resto()

return prefijoCola(c1, c2) or subCola3Aux(q1, c2)

def subCola3(c1: Cola[A], c2: Cola[A]) -> bool:

q1 = deepcopy(c1)

q2 = deepcopy(c2)

return subCola3Aux(q1, q2)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(c1=colaAleatoria(), c2=colaAleatoria())

def test_subCola(c1: Cola[int], c2: Cola[int]) -> None:

r = subCola1(c1, c2)

assert subCola2(c1, c2) == r

assert subCola3(c1, c2) == r

# La comprobación es

# src> poetry run pytest -q subCola.py

# 1 passed in 0.31s

5. Reconocimiento de ordenación de colas

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

   ordenadaCola :: Ord a => Cola a -> Bool

1	ordenadaCola :: Ord a => Cola a -> Bool

tal que ordenadaCola c se verifica si los elementos de la cola c están ordenados en orden creciente. Por ejemplo,

   ordenadaCola (inserta 6 (inserta 5 (inserta 1 vacia))) == True
   ordenadaCola (inserta 1 (inserta 0 (inserta 6 vacia))) == False

1 2	ordenadaCola (inserta 6 (inserta 5 (inserta 1 vacia))) == True ordenadaCola (inserta 1 (inserta 0 (inserta 6 vacia))) == False

Soluciones

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

Soluciones en Haskell

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)
import Transformaciones_colas_listas (colaAlista)
import Test.QuickCheck

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

ordenadaCola :: Ord a => Cola a -> Bool
ordenadaCola c
  | esVacia c  = True
  | esVacia rc = True
  | otherwise  = pc <= prc && ordenadaCola rc
  where pc  = primero c
        rc  = resto c
        prc = primero rc

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

ordenadaCola2 :: Ord a => Cola a -> Bool
ordenadaCola2 =
  ordenadaLista . colaAlista

-- (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)]

-- La función colaAlista está definida en el ejercicio
-- "Transformaciones entre colas y listas" que se encuentra en
-- https://bit.ly/3Xv0oIt

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

-- La propiedad es
prop_ordenadaCola :: Cola Int -> Bool
prop_ordenadaCola c =
  ordenadaCola c == ordenadaCola2 c

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

import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)

import Transformaciones_colas_listas (colaAlista)

import Test.QuickCheck

-- 1ª solución

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

ordenadaCola :: Ord a => Cola a -> Bool

ordenadaCola c

| esVacia c = True

| esVacia rc = True

| otherwise = pc <= prc && ordenadaCola rc

where pc = primero c

rc = resto c

prc = primero rc

-- 2ª solución

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

ordenadaCola2 :: Ord a => Cola a -> Bool

ordenadaCola2 =

ordenadaLista . colaAlista

-- (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)]

-- La función colaAlista está definida en el ejercicio

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

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

-- Comprobación de equivalencia

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

-- La propiedad es

prop_ordenadaCola :: Cola Int -> Bool

prop_ordenadaCola c =

ordenadaCola c == ordenadaCola2 c

-- La comprobación es

-- λ> quickCheck prop_ordenadaCola

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,
                          resto, vacia)
from src.transformaciones_colas_listas import colaAlista

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

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

def ordenadaCola(c: Cola[A]) -> bool:
    if esVacia(c):
        return True
    pc = primero(c)
    rc = resto(c)
    if esVacia(rc):
        return True
    prc = primero(rc)
    return pc <= prc and ordenadaCola(rc)

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

# 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 ordenadaCola2(p: Cola[A]) -> bool:
    return ordenadaLista(colaAlista(p))

# La función colaAlista  está definida en el ejercicio
# "Transformaciones entre colas y listas" que se encuentra en
# https://bit.ly/3Xv0oIt

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

def ordenadaCola3Aux(c: Cola[A]) -> bool:
    if c.esVacia():
        return True
    pc = c.primero()
    c.resto()
    if c.esVacia():
        return True
    return pc <= c.primero() and ordenadaCola3Aux(c)

def ordenadaCola3(c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return ordenadaCola3Aux(_c)

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

def ordenadaCola4Aux(c: Cola[A]) -> bool:
    while not c.esVacia():
        pc = c.primero()
        c.resto()
        if not c.esVacia() and pc > c.primero():
            return False
    return True

def ordenadaCola4(c: Cola[A]) -> bool:
    _c = deepcopy(c)
    return ordenadaCola4Aux(_c)

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

# La propiedad es
@given(p=colaAleatoria())
def test_ordenadaCola(p: Cola[int]) -> None:
    r = ordenadaCola(p)
    assert ordenadaCola2(p) == r
    assert ordenadaCola3(p) == r
    assert ordenadaCola4(p) == r

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

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,

resto, vacia)

from src.transformaciones_colas_listas import colaAlista

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

# 1ª solución

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

def ordenadaCola(c: Cola[A]) -> bool:

if esVacia(c):

return True

pc = primero(c)

rc = resto(c)

if esVacia(rc):

return True

prc = primero(rc)

return pc <= prc and ordenadaCola(rc)

# 2ª solución

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

# 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 ordenadaCola2(p: Cola[A]) -> bool:

return ordenadaLista(colaAlista(p))

# La función colaAlista está definida en el ejercicio

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

# https://bit.ly/3Xv0oIt

# 3ª solución

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

def ordenadaCola3Aux(c: Cola[A]) -> bool:

if c.esVacia():

return True

pc = c.primero()

c.resto()

if c.esVacia():

return True

return pc <= c.primero() and ordenadaCola3Aux(c)

def ordenadaCola3(c: Cola[A]) -> bool:

_c = deepcopy(c)

return ordenadaCola3Aux(_c)

# 4ª solución

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

def ordenadaCola4Aux(c: Cola[A]) -> bool:

while not c.esVacia():

pc = c.primero()

c.resto()

if not c.esVacia() and pc > c.primero():

return False

return True

def ordenadaCola4(c: Cola[A]) -> bool:

_c = deepcopy(c)

return ordenadaCola4Aux(_c)

# Comprobación de equivalencia de las definiciones

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

# La propiedad es

@given(p=colaAleatoria())

def test_ordenadaCola(p: Cola[int]) -> None:

r = ordenadaCola(p)

assert ordenadaCola2(p) == r

assert ordenadaCola3(p) == r

assert ordenadaCola4(p) == r

# La comprobación es

# src> poetry run pytest -q ordenadaCola.py

# 1 passed in 0.27s

1. Pertenencia a una cola

2. Inclusión de colas

3. Reconocimiento de prefijos de colas

4. Reconocimiento de subcolas

5. Reconocimiento de ordenación de colas

Se puede imprimir o compartir con