TAD de las pilas: Reconocimiento de subpilas

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

   λ> 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

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.

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