{"id":7883,"date":"2023-02-04T17:40:05","date_gmt":"2023-02-04T16:40:05","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7883"},"modified":"2023-02-04T17:40:24","modified_gmt":"2023-02-04T16:40:24","slug":"04-feb-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/04-feb-23\/","title":{"rendered":"PFH: La semana en Exercitium (4 de febrero de 2023)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. TAD de las pilas: Reconocimiento de prefijos de pilas<\/a><\/li>\n<li><a href=\"#ej2\">2. TAD de las pilas: Reconocimiento de subpilas<\/a><\/li>\n<li><a href=\"#ej3\">3. TAD de las pilas: Reconocimiento de ordenaci\u00f3n de pilas<\/a><\/li>\n<li><a href=\"#ej4\">4. TAD de las pilas: Ordenaci\u00f3n de pilas por inserci\u00f3n<\/a><\/li>\n<li><a href=\"#ej5\">5. hTAD de las pilas: Eliminaci\u00f3n de repeticiones en una pila<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. TAD de las pilas: Reconocimiento de prefijos de pilas<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3GTToyK\">tipo abstracto de datos de las pilas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   prefijoPila :: Eq a => Pila a -> Pila a -> Bool\n<\/pre>\n<p>tal que <code>prefijoPila p1 p2<\/code> se verifica si la pila <code>p1<\/code> es justamente un prefijo de la pila <code>p2<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ej1 = apila 4 (apila 2 vacia)\n   \u03bb> ej2 = apila 4 (apila 2 (apila 5 vacia))\n   \u03bb> ej3 = apila 5 (apila 4 (apila 2 vacia))\n   \u03bb> prefijoPila ej1 ej2\n   True\n   \u03bb> prefijoPila ej1 ej3\n   False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)\nimport Transformaciones_pilas_listas (pilaAlista)\nimport Data.List (isSuffixOf)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprefijoPila :: Eq a => Pila a -> Pila a -> Bool\nprefijoPila p1 p2\n  | esVacia p1 = True\n  | esVacia p2 = False\n  | otherwise  = cp1 == cp2 && prefijoPila dp1 dp2\n  where cp1 = cima p1\n        dp1 = desapila p1\n        cp2 = cima p2\n        dp2 = desapila p2\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Se usar\u00e1 la funci\u00f3n pilaAlista del ejercicio\n-- \"Transformaciones entre pilas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3ZHewQ8\n\nprefijoPila2 :: Eq a => Pila a -> Pila a -> Bool\nprefijoPila2 p1 p2 =\n  pilaAlista p1 `isSuffixOf` pilaAlista p2\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_prefijoPila :: Pila Int -> Pila Int -> Bool\nprop_prefijoPila p1 p2 =\n  prefijoPila p1 p2 == prefijoPila2 p1 p2\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_prefijoPila\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import given\n\nfrom src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,\n                          vacia)\nfrom src.transformaciones_pilas_listas import pilaAlista\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef prefijoPila(p1: Pila[A], p2: Pila[A]) -> bool:\n    if esVacia(p1):\n        return True\n    if esVacia(p2):\n        return False\n    cp1 = cima(p1)\n    dp1 = desapila(p1)\n    cp2 = cima(p2)\n    dp2 = desapila(p2)\n    return cp1 == cp2 and prefijoPila(dp1, dp2)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1 la funci\u00f3n pilaAlista del ejercicio\n# \"Transformaciones entre pilas y listas\" que se encuentra en\n# https:\/\/bit.ly\/3ZHewQ8\n\ndef esSufijoLista(xs: list[A], ys: list[A]) -> bool:\n    if not xs:\n        return True\n    return xs == ys[-len(xs):]\n\ndef prefijoPila2(p1: Pila[A], p2: Pila[A]) -> bool:\n    return esSufijoLista(pilaAlista(p1), pilaAlista(p2))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef prefijoPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:\n    if p1.esVacia():\n        return True\n    if p2.esVacia():\n        return False\n    cp1 = p1.cima()\n    p1.desapila()\n    cp2 = p2.cima()\n    p2.desapila()\n    return cp1 == cp2 and prefijoPila3(p1, p2)\n\ndef prefijoPila3(p1: Pila[A], p2: Pila[A]) -> bool:\n    q1 = deepcopy(p1)\n    q2 = deepcopy(p2)\n    return prefijoPila3Aux(q1, q2)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef prefijoPila4Aux(p1: Pila[A], p2: Pila[A]) -> bool:\n    while not p2.esVacia() and not p1.esVacia():\n        if p1.cima() != p2.cima():\n            return False\n        p1.desapila()\n        p2.desapila()\n    return p1.esVacia()\n\ndef prefijoPila4(p1: Pila[A], p2: Pila[A]) -> bool:\n    q1 = deepcopy(p1)\n    q2 = deepcopy(p2)\n    return prefijoPila4Aux(q1, q2)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones\n# ================================================\n\n# La propiedad es\n@given(p1=pilaAleatoria(), p2=pilaAleatoria())\ndef test_prefijoPila(p1: Pila[int], p2: Pila[int]) -> None:\n    r = prefijoPila(p1, p2)\n    assert prefijoPila2(p1, p2) == r\n    assert prefijoPila3(p1, p2) == r\n    assert prefijoPila4(p1, p2) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q prefijoPila.py\n#    1 passed in 0.32s\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. TAD de las pilas: Reconocimiento de subpilas<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3GTToyK\">tipo abstracto de datos de las pilas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   subPila :: Eq a => Pila a -> Pila a -> Bool\n<\/pre>\n<p>tal que <code>subPila p1 p2<\/code> se verifica si <code>p1<\/code> es una subpila de <code>p2<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ej1 = apila 2 (apila 3 vacia)\n   \u03bb> ej2 = apila 7 (apila 2 (apila 3 (apila 5 vacia)))\n   \u03bb> ej3 = apila 2 (apila 7 (apila 3 (apila 5 vacia)))\n   \u03bb> subPila ej1 ej2\n   True\n   \u03bb> subPila ej1 ej3\n   False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)\nimport Transformaciones_pilas_listas (pilaAlista)\nimport PrefijoPila (prefijoPila)\nimport Data.List (isPrefixOf, tails)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\n-- Se usar\u00e1 la funci\u00f3n PrefijoPila del ejercicio\n-- \"Reconocimiento de prefijos de pilas\" que se encuentra en\n-- https:\/\/bit.ly\/3Xqu7lo\n\nsubPila1 :: Eq a => Pila a -> Pila a -> Bool\nsubPila1 p1 p2\n    | esVacia p1 = True\n    | esVacia p2 = False\n    | cp1 == cp2 = prefijoPila dp1 dp2 || subPila1 p1 dp2\n    | otherwise  = subPila1 p1 dp2\n    where cp1 = cima p1\n          dp1 = desapila p1\n          cp2 = cima p2\n          dp2 = desapila p2\n\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Se usar\u00e1 la funci\u00f3n pilaAlista del ejercicio\n-- \"Transformaciones entre pilas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3ZHewQ8\n\nsubPila2 :: Eq a => Pila a -> Pila a -> Bool\nsubPila2 p1 p2 =\n  sublista (pilaAlista p1) (pilaAlista p2)\n\n-- (sublista xs ys) se verifica si xs es una sublista de ys. Por\n-- ejemplo,\n--    sublista [3,2] [5,3,2,7]  ==  True\n--    sublista [3,2] [5,3,7,2]  ==  False\nsublista :: Eq a => [a] -> [a] -> Bool\nsublista xs ys =\n  any (xs `isPrefixOf`) (tails ys)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_subPila :: Pila Int -> Pila Int -> Bool\nprop_subPila p1 p2 =\n  subPila1 p1 p2 == subPila2 p1 p2\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_subPila\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import given\n\nfrom src.prefijoPila import prefijoPila\nfrom src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,\n                          vacia)\nfrom src.transformaciones_pilas_listas import pilaAlista\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1 la funci\u00f3n PrefijoPila del ejercicio\n# \"Reconocimiento de prefijos de pilas\" que se encuentra en\n# https:\/\/bit.ly\/3Xqu7lo\n\ndef subPila1(p1: Pila[A], p2: Pila[A]) -> bool:\n    if esVacia(p1):\n        return True\n    if esVacia(p2):\n        return False\n    cp1 = cima(p1)\n    dp1 = desapila(p1)\n    cp2 = cima(p2)\n    dp2 = desapila(p2)\n    if cp1 == cp2:\n        return prefijoPila(dp1, dp2) or subPila1(p1, dp2)\n    return subPila1(p1, dp2)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1 la funci\u00f3n pilaAlista del ejercicio\n# \"Transformaciones entre pilas y listas\" que se encuentra en\n# https:\/\/bit.ly\/3ZHewQ8\n\n# sublista(xs, ys) se verifica si xs es una sublista de ys. Por\n# ejemplo,\n#    >>> sublista([3,2], [5,3,2,7])\n#    True\n#    >>> sublista([3,2], [5,3,7,2])\n#    False\ndef sublista(xs: list[A], ys: list[A]) -> bool:\n    return any(xs == ys[i:i+len(xs)] for i in range(len(ys) - len(xs) + 1))\n\ndef subPila2(p1: Pila[A], p2: Pila[A]) -> bool:\n    return sublista(pilaAlista(p1), pilaAlista(p2))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef subPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool:\n    if p1.esVacia():\n        return True\n    if p2.esVacia():\n        return False\n    if p1.cima() != p2.cima():\n        p2.desapila()\n        return subPila3Aux(p1, p2)\n    q1 = deepcopy(p1)\n    p1.desapila()\n    p2.desapila()\n    return prefijoPila(p1, p2) or subPila3Aux(q1, p2)\n\ndef subPila3(p1: Pila[A], p2: Pila[A]) -> bool:\n    q1 = deepcopy(p1)\n    q2 = deepcopy(p2)\n    return subPila3Aux(q1, q2)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones\n# ================================================\n\n# La propiedad es\n@given(p1=pilaAleatoria(), p2=pilaAleatoria())\ndef test_subPila(p1: Pila[int], p2: Pila[int]) -> None:\n    r = subPila1(p1, p2)\n    assert subPila2(p1, p2) == r\n    assert subPila3(p1, p2) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q subPila.py\n#    1 passed in 0.32s\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. TAD de las pilas: Reconocimiento de ordenaci\u00f3n de pilas<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3GTToyK\">tipo abstracto de datos de las pilas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ordenadaPila :: Ord a => Pila a -> Bool\n<\/pre>\n<p>tal que <code>ordenadaPila p<\/code> se verifica si los elementos de la pila <code>p<\/code> est\u00e1n ordenados en orden creciente. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ordenadaPila (apila 1 (apila 5 (apila 6 vacia))) == True\n   ordenadaPila (apila 1 (apila 0 (apila 6 vacia))) == False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)\nimport Transformaciones_pilas_listas (pilaAlista)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nordenadaPila :: Ord a => Pila a -> Bool\nordenadaPila p\n  | esVacia p  = True\n  | esVacia dp = True\n  | otherwise  = cp <= cdp &#038;&#038; ordenadaPila dp\n  where cp  = cima p\n        dp  = desapila p\n        cdp = cima dp\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nordenadaPila2 :: Ord a => Pila a -> Bool\nordenadaPila2 =\n  ordenadaLista . reverse . pilaAlista\n\n-- (ordenadaLista xs) se verifica si la lista xs est\u00e1 ordenada de menor\n-- a mayor. Por ejemplo,\nordenadaLista :: Ord a => [a] -> Bool\nordenadaLista xs =\n  and [x <= y | (x,y) <- zip xs (tail xs)]\n\n-- Se usar\u00e1 la funci\u00f3n pilaAlista del ejercicio\n-- \"Transformaciones entre pilas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3ZHewQ8\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_ordenadaPila :: Pila Int -> Bool\nprop_ordenadaPila p =\n  ordenadaPila p == ordenadaPila2 p\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ordenadaPila\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import given\n\nfrom src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,\n                          vacia)\nfrom src.transformaciones_pilas_listas import pilaAlista\n\nA = TypeVar('A', int, float, str)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef ordenadaPila(p: Pila[A]) -> bool:\n    if esVacia(p):\n        return True\n    cp = cima(p)\n    dp = desapila(p)\n    if esVacia(dp):\n        return True\n    cdp = cima(dp)\n    return cp <= cdp and ordenadaPila(dp)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1 la funci\u00f3n pilaAlista del ejercicio\n# \"Transformaciones entre pilas y listas\" que se encuentra en\n# https:\/\/bit.ly\/3ZHewQ8\n\n# ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por\n# ejemplo,\n#    >>> ordenadaLista([2, 5, 8])\n#    True\n#    >>> ordenadalista([2, 8, 5])\n#    False\ndef ordenadaLista(xs: list[A]) -> bool:\n    return all((x <= y for (x, y) in zip(xs, xs[1:])))\n\ndef ordenadaPila2(p: Pila[A]) -> bool:\n    return ordenadaLista(list(reversed(pilaAlista(p))))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef ordenadaPila3Aux(p: Pila[A]) -> bool:\n    if p.esVacia():\n        return True\n    cp = p.cima()\n    p.desapila()\n    if p.esVacia():\n        return True\n    return cp <= p.cima() and ordenadaPila3Aux(p)\n\ndef ordenadaPila3(p: Pila[A]) -> bool:\n    q = deepcopy(p)\n    return ordenadaPila3Aux(q)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef ordenadaPila4Aux(p: Pila[A]) -> bool:\n    while not p.esVacia():\n        cp = p.cima()\n        p.desapila()\n        if not p.esVacia() and cp > p.cima():\n            return False\n    return True\n\ndef ordenadaPila4(p: Pila[A]) -> bool:\n    q = deepcopy(p)\n    return ordenadaPila4Aux(q)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones\n# ================================================\n\n# La propiedad es\n@given(p=pilaAleatoria())\ndef test_ordenadaPila(p: Pila[int]) -> None:\n    r = ordenadaPila(p)\n    assert ordenadaPila2(p) == r\n    assert ordenadaPila3(p) == r\n    assert ordenadaPila4(p) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q ordenadaPila.py\n#    1 passed in 0.31s\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. TAD de las pilas: Ordenaci\u00f3n de pilas por inserci\u00f3n<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3GTToyK\">tipo abstracto de datos de las pilas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ordenaInserPila :: Ord a => Pila a -> Pila a\n<\/pre>\n<p>tal que <code>ordenaInserPila p<\/code> es la pila obtenida ordenando por inserci\u00f3n los los elementos de la pila <code>p<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia)))\n   1 | 3 | 4\n<\/pre>\n<p>Comprobar con QuickCheck que la pila <code>(ordenaInserPila p)<\/code> est\u00e1 ordenada.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)\nimport Transformaciones_pilas_listas (listaApila, pilaAlista)\nimport OrdenadaPila (ordenadaPila)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nordenaInserPila1 :: Ord a => Pila a -> Pila a\nordenaInserPila1 p\n  | esVacia p = p\n  | otherwise = insertaPila cp (ordenaInserPila1 dp)\n  where cp = cima p\n        dp = desapila p\n\ninsertaPila :: Ord a => a -> Pila a -> Pila a\ninsertaPila x p\n  | esVacia p = apila x p\n  | x < cp    = apila x p\n  | otherwise = apila cp (insertaPila x dp)\n  where cp = cima p\n        dp = desapila p\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nordenaInserPila2 :: Ord a => Pila a -> Pila a\nordenaInserPila2  =\n  listaApila . reverse . ordenaInserLista . pilaAlista\n\nordenaInserLista :: Ord a => [a] -> [a]\nordenaInserLista []      = []\nordenaInserLista (x: xs) = insertaLista x (ordenaInserLista xs)\n\ninsertaLista :: Ord a => a -> [a] -> [a]\ninsertaLista x [] = [x]\ninsertaLista x (y:ys) | x < y = x : y : ys\n                      | otherwise = y : insertaLista x ys\n\n-- Se usar\u00e1n las funciones listaApila y pilaAlista del ejercicio\n-- \"Transformaciones entre pilas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3ZHewQ8\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_ordenaInserPila :: Pila Int -> Bool\nprop_ordenaInserPila p =\n  ordenaInserPila1 p == ordenaInserPila2 p\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ordenaInserPila\n--    +++ OK, passed 100 tests.\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- Se usar\u00e1 la funci\u00f3n ordenadaPila del ejercicio\n-- \"Reconocimiento de ordenaci\u00f3n de pilas\" que se encuentra en\n-- https:\/\/bit.ly\/3COqRbK\n\n-- La propiedad es\nprop_ordenadaOrdenaInserPila :: Pila Int -> Bool\nprop_ordenadaOrdenaInserPila p =\n  ordenadaPila (ordenaInserPila1 p)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ordenadaOrdenaInserPila\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import given\n\nfrom src.ordenadaPila import ordenadaPila\nfrom src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,\n                          vacia)\nfrom src.transformaciones_pilas_listas import listaApila, pilaAlista\n\nA = TypeVar('A', int, float, str)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef insertaPila(x: A, p: Pila[A]) -> Pila[A]:\n    if esVacia(p):\n        return apila(x, p)\n    cp = cima(p)\n    if x < cp:\n        return apila(x, p)\n    dp = desapila(p)\n    return apila(cp, insertaPila(x, dp))\n\ndef ordenaInserPila1(p: Pila[A]) -> Pila[A]:\n    if esVacia(p):\n        return p\n    cp = cima(p)\n    dp = desapila(p)\n    return insertaPila(cp, ordenaInserPila1(dp))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1n las funciones listaApila y pilaAlista del ejercicio\n# \"Transformaciones entre pilas y listas\" que se encuentra en\n# https:\/\/bit.ly\/3ZHewQ8\n\ndef insertaLista(x: A, ys: list[A]) -> list[A]:\n    if not ys:\n        return [x]\n    if x < ys[0]:\n        return [x] + ys\n    return [ys[0]] + insertaLista(x, ys[1:])\n\ndef ordenaInserLista(xs: list[A]) -> list[A]:\n    if not xs:\n        return []\n    return insertaLista(xs[0], ordenaInserLista(xs[1:]))\n\ndef ordenaInserPila2(p: Pila[A]) -> Pila[A]:\n    return listaApila(list(reversed(ordenaInserLista(pilaAlista(p)))))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef ordenaInserPila3Aux(p: Pila[A]) -> Pila[A]:\n    if p.esVacia():\n        return p\n    cp = p.cima()\n    p.desapila()\n    return insertaPila(cp, ordenaInserPila3Aux(p))\n\ndef ordenaInserPila3(p: Pila[A]) -> Pila[A]:\n    q = deepcopy(p)\n    return ordenaInserPila3Aux(q)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones\n# ================================================\n\n# La propiedad es\n@given(p=pilaAleatoria())\ndef test_ordenaInserPila(p: Pila[int]) -> None:\n    r = ordenaInserPila1(p)\n    assert ordenaInserPila2(p) == r\n    assert ordenaInserPila3(p) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q ordenaInserPila.py\n#    1 passed in 0.31s\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# Se usar\u00e1 la funci\u00f3n ordenadaPila del ejercicio\n# \"Reconocimiento de ordenaci\u00f3n de pilas\" que se encuentra en\n# https:\/\/bit.ly\/3COqRbK\n\n# La propiedad es\n@given(p=pilaAleatoria())\ndef test_ordenadaOrdenaInserPila(p: Pila[int]) -> None:\n    ordenadaPila(ordenaInserPila1(p))\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q ordenaInserPila.py\n#    2 passed in 0.47s\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. TAD de las pilas: Eliminaci\u00f3n de repeticiones en una pila<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3GTToyK\">tipo abstracto de datos de las pilas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   nubPila :: Eq a => Pila a -> Pila a\n<\/pre>\n<p>tal que <code>nubPila p<\/code> es la pila con los elementos de <code>p<\/code> sin repeticiones. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> nubPila (apila 3 (apila 1 (apila 3 (apila 5 vacia))))\n   1 | 3 | 5\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)\nimport Transformaciones_pilas_listas (listaApila, pilaAlista)\nimport PertenecePila (pertenecePila)\nimport Data.List (nub)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\n-- Se usar\u00e1 la funci\u00f3n pertenecePila del ejercicio\n-- \"Pertenencia a una pila\" que se encuentra en\n-- https:\/\/bit.ly\/3WdM9GC\n\nnubPila1 :: Eq a => Pila a -> Pila a\nnubPila1 p\n  | esVacia p           = vacia\n  | pertenecePila cp dp = nubPila1 dp\n  | otherwise           = apila cp (nubPila1 dp)\n  where cp = cima p\n        dp = desapila p\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Se usar\u00e1n las funciones listaApila y pilaAlista del ejercicio\n-- \"Transformaciones entre pilas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3ZHewQ8\n\nnubPila2 :: Eq a => Pila a -> Pila a\nnubPila2 =\n  listaApila . nub . pilaAlista\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_nubPila :: Pila Int -> Bool\nprop_nubPila p =\n  nubPila1 p == nubPila2 p\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_nubPila\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import given\n\nfrom src.pertenecePila import pertenecePila\nfrom src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,\n                          vacia)\nfrom src.transformaciones_pilas_listas import listaApila, pilaAlista\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1 la funci\u00f3n pertenecePila del ejercicio\n# \"Pertenencia a una pila\" que se encuentra en\n# https:\/\/bit.ly\/3WdM9GC\n\ndef nubPila1(p: Pila[A]) -> Pila[A]:\n    if esVacia(p):\n        return p\n    cp = cima(p)\n    dp = desapila(p)\n    if pertenecePila(cp, dp):\n        return nubPila1(dp)\n    return apila(cp, nubPila1(dp))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1n las funciones listaApila y pilaAlista del ejercicio\n# \"Transformaciones entre pilas y listas\" que se encuentra en\n# https:\/\/bit.ly\/3ZHewQ8\n\ndef nub(xs: list[A]) -> list[A]:\n    return [x for i, x in enumerate(xs) if x not in xs[:i]]\n\ndef nubPila2(p: Pila[A]) -> Pila[A]:\n    return listaApila(nub(pilaAlista(p)))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef nubPila3Aux(p: Pila[A]) -> Pila[A]:\n    if p.esVacia():\n        return p\n    cp = p.cima()\n    p.desapila()\n    if pertenecePila(cp, p):\n        return nubPila3Aux(p)\n    return apila(cp, nubPila3Aux(p))\n\ndef nubPila3(p: Pila[A]) -> Pila[A]:\n    q = deepcopy(p)\n    return nubPila3Aux(q)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones\n# ================================================\n\n# La propiedad es\n@given(p=pilaAleatoria())\ndef test_nubPila(p: Pila[int]) -> None:\n    r = nubPila1(p)\n    assert nubPila2(p) == r\n    assert nubPila3(p) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q nubPila.py\n#    1 passed in 0.27s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>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\u00f3n de pilas 4. TAD de las pilas: Ordenaci\u00f3n de pilas por inserci\u00f3n 5. hTAD de las pilas:&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7883"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7883"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7883\/revisions"}],"predecessor-version":[{"id":7884,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7883\/revisions\/7884"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7883"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7883"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7883"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}