TAD de las colas: Reconocimiento de subcolas
Utilizando el tipo abstracto de datos de las colas, definir la función
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,
1 2 3 4 5 6 7 |
λ> 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
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. |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
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 |