{"id":7870,"date":"2022-12-25T08:27:13","date_gmt":"2022-12-25T07:27:13","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7870"},"modified":"2022-12-25T08:27:13","modified_gmt":"2022-12-25T07:27:13","slug":"24-dic-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/24-dic-22\/","title":{"rendered":"PFH: La semana en Exercitium (24 de diciembre de 2022)"},"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. Recorrido de \u00e1rboles binarios<\/a><\/li>\n<li><a href=\"#ej2\">2. Imagen especular de un \u00e1rbol binario<\/a><\/li>\n<li><a href=\"#ej3\">3. Sub\u00e1rbol de profundidad dada<\/a><\/li>\n<li><a href=\"#ej4\">4. \u00c1rbol de profundidad n con nodos iguales<\/a><\/li>\n<li><a href=\"#ej5\">5. Suma de un \u00e1rbol<\/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. Recorrido de \u00e1rboles binarios<\/h3>\n<p>El \u00e1rbol binario<\/p>\n<pre lang=\"text\">\n        9\n       \/ \\\n      \/   \\\n     3     7\n    \/ \\\n   2   4\n<\/pre>\n<p>se puede representar por<\/p>\n<pre lang=\"text\">\n   N 9 (N 3 (H 2) (H 4)) (H 7)\n<\/pre>\n<p>El tipo de los \u00e1rboles binarios se puede definir por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n     deriving (Show, Eq)\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   preorden  :: Arbol a -> [a]\n   postorden :: Arbol a -> [a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>preorden<\/code> es la lista correspondiente al recorrido preorden del \u00e1rbol <code>x<\/code>; es decir, primero visita la ra\u00edz del \u00e1rbol, a continuaci\u00f3n recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el sub\u00e1rbol derecho. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]\n<\/pre>\n<ul>\n<li><code>postorden x<\/code> es la lista correspondiente al recorrido postorden del \u00e1rbol <code>x<\/code>; es decir, primero recorre el sub\u00e1rbol izquierdo, a continuaci\u00f3n el sub\u00e1rbol derecho y, finalmente, la ra\u00edz del \u00e1rbol. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]\n<\/pre>\n<p>Comprobar con QuickCheck que la longitud de la lista obtenida recorriendo un \u00e1rbol en cualquiera de los sentidos es igual al n\u00famero de nodos del \u00e1rbol m\u00e1s el n\u00famero de hojas.<br \/>\n<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 Test.QuickCheck\n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\npreorden :: Arbol a -> [a]\npreorden (H x)     = [x]\npreorden (N x i d) = x : preorden i ++ preorden d\n\npostorden :: Arbol a -> [a]\npostorden (H x)     = [x]\npostorden (N x i d) = postorden i ++ postorden d ++ [x]\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- (arbolArbitrario n) es un \u00e1rbol aleatorio de altura n. Por ejemplo,\n--    \u03bb> sample (arbolArbitrario 3 :: Gen (Arbol Int))\n--    N 0 (H 0) (H 0)\n--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)\n--    N 3 (H 1) (H 2)\n--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))\n--    H 7\n--    N (-8) (H (-8)) (H 9)\n--    H 2\n--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))\n--    H (-3)\n--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)\n--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario 0 = H <$> arbitrary\narbolArbitrario n =\n  oneof [H <$> arbitrary,\n         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]\n\n-- Arbol es subclase de Arbitrary\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbolArbitrario\n\n-- La propiedad es\nprop_longitud_recorrido :: Arbol Int -> Bool\nprop_longitud_recorrido x =\n   length (preorden x)  == n &&\n   length (postorden x) == n\n   where n = nNodos x + nHojas x\n\n-- (nNodos x) es el n\u00famero de nodos del \u00e1rbol x. Por ejemplo,\n--      nNodos (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  2\nnNodos :: Arbol a -> Int\nnNodos (H _)     = 0\nnNodos (N _ i d) = 1 + nNodos i + nNodos d\n\n-- (nHojas x) es el n\u00famero de hojas del \u00e1rbol x. Por ejemplo,\n--    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3\nnHojas :: Arbol a -> Int\nnHojas (H _)     = 1\nnHojas (N _ i d) = nHojas i + nHojas d\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_longitud_recorrido\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 dataclasses import dataclass\nfrom random import choice, randint\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar(\"A\")\n\n@dataclass\nclass Arbol(Generic[A]):\n    pass\n\n@dataclass\nclass H(Arbol[A]):\n    x: A\n\n@dataclass\nclass N(Arbol[A]):\n    x: A\n    i: Arbol[A]\n    d: Arbol[A]\n\ndef preorden(a: Arbol[A]) -> list[A]:\n    match a:\n        case H(x):\n            return [x]\n        case N(x, i, d):\n            return [x] + preorden(i) + preorden(d)\n    assert False\n\ndef postorden(a: Arbol[A]) -> list[A]:\n    match a:\n        case H(x):\n            return [x]\n        case N(x, i, d):\n            return postorden(i) + postorden(d) + [x]\n    assert False\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# (arbolArbitrario n) es un \u00e1rbol aleatorio de orden n. Por ejemplo,\n#    >>> arbolArbitrario(4)\n#    N(x=2, i=H(x=1), d=H(x=9))\n#    >>> arbolArbitrario(4)\n#    H(x=10)\n#    >>> arbolArbitrario(4)\n#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))\ndef arbolArbitrario(n: int) -> Arbol[int]:\n    if n <= 1:\n        return H(randint(0, 10))\n    m = n \/\/ 2\n    return choice([H(randint(0, 10)),\n                   N(randint(0, 10),\n                     arbolArbitrario(m),\n                     arbolArbitrario(m))])\n\n# nNodos(x) es el n\u00famero de nodos del \u00e1rbol x. Por ejemplo,\n#    nNodos(N(9, N(3, H(2), H(4)), H(7)))  ==  2\ndef nNodos(a: Arbol[A]) -> int:\n    match a:\n        case H(_):\n            return 0\n        case N(_, i, d):\n            return 1 + nNodos(i) + nNodos(d)\n    assert False\n\n# (nHojas x) es el n\u00famero de hojas del \u00e1rbol x. Por ejemplo,\n#    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3\ndef nHojas(a: Arbol[A]) -> int:\n    match a:\n        case H(_):\n            return 1\n        case N(_, i, d):\n            return nHojas(i) + nHojas(d)\n    assert False\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=10))\ndef test_recorrido(n: int) -> None:\n    a = arbolArbitrario(n)\n    m = nNodos(a) + nHojas(a)\n    assert len(preorden(a)) == m\n    assert len(postorden(a)) == m\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q recorrido_de_arboles_binarios.py\n#    1 passed in 0.16s\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Imagen especular de un \u00e1rbol binario<\/h3>\n<p>El \u00e1rbol binario<\/p>\n<pre lang=\"text\">\n        9\n       \/ \\\n      \/   \\\n     3     7\n    \/ \\\n   2   4\n<\/pre>\n<p>se puede representar por<\/p>\n<pre lang=\"text\">\n   N 9 (N 3 (H 2) (H 4)) (H 7)\n<\/pre>\n<p>El tipo de los \u00e1rboles binarios se puede definir por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n     deriving (Show, Eq)\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   espejo :: Arbol a -> Arbol a\n<\/pre>\n<p>tal que <code>espejo x<\/code> es la imagen especular del \u00e1rbol <code>x<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2))\n<\/pre>\n<p>Comprobar con QuickCheck las siguientes propiedades, para todo \u00e1rbol <code>x<\/code>,<\/p>\n<pre lang=\"text\">\n   espejo (espejo x) = x\n   reverse (preorden (espejo x)) = postorden x\n   postorden (espejo x) = reverse (preorden x)\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 Test.QuickCheck\n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\nespejo :: Arbol a -> Arbol a\nespejo (H x)     = H x\nespejo (N x i d) = N x (espejo d) (espejo i)\n\n-- Generador para las comprobaciones\n-- =================================\n\n-- (arbolArbitrario n) es un \u00e1rbol aleatorio de altura n. Por ejemplo,\n--    \u03bb> sample (arbolArbitrario 3 :: Gen (Arbol Int))\n--    N 0 (H 0) (H 0)\n--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)\n--    N 3 (H 1) (H 2)\n--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))\n--    H 7\n--    N (-8) (H (-8)) (H 9)\n--    H 2\n--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))\n--    H (-3)\n--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)\n--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario 0 = H <$> arbitrary\narbolArbitrario n =\n  oneof [H <$> arbitrary,\n         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]\n\n-- Arbol es subclase de Arbitrary\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbolArbitrario\n\n-- Funciones auxiliares para la comprobaci\u00f3n\n-- =========================================\n\n-- (preorden x) es la lista correspondiente al recorrido preorden del\n-- \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a continuaci\u00f3n\n-- recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el sub\u00e1rbol\n-- derecho. Por ejemplo,\n--    preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]\npreorden :: Arbol a -> [a]\npreorden (H x)     = [x]\npreorden (N x i d) = x : preorden i ++ preorden d\n\n-- (postorden x) es la lista correspondiente al recorrido postorden\n-- del \u00e1rbol x; es decir, primero recorre el sub\u00e1rbol izquierdo, a\n-- continuaci\u00f3n el sub\u00e1rbol derecho y, finalmente, la ra\u00edz del\n-- \u00e1rbol. Por ejemplo,\n--    postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]\npostorden :: Arbol a -> [a]\npostorden (H x)     = [x]\npostorden (N x i d) = postorden i ++ postorden d ++ [x]\n\n-- Comprobaci\u00f3n de las propiedades\n-- ===============================\n\n-- Las propiedades son\nprop_espejo :: Arbol Int -> Bool\nprop_espejo x =\n  espejo (espejo x) == x &&\n  reverse (preorden (espejo x)) == postorden x &&\n  postorden (espejo x) == reverse (preorden x)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_espejo\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 dataclasses import dataclass\nfrom random import choice, randint\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar(\"A\")\n\n@dataclass\nclass Arbol(Generic[A]):\n    pass\n\n@dataclass\nclass H(Arbol[A]):\n    x: A\n\n@dataclass\nclass N(Arbol[A]):\n    x: A\n    i: Arbol[A]\n    d: Arbol[A]\n\ndef espejo(a: Arbol[A]) -> Arbol[A]:\n    match a:\n        case H(x):\n            return H(x)\n        case N(x, i, d):\n            return N(x, espejo(d), espejo(i))\n    assert False\n\n# Generador para las comprobaciones\n# =================================\n\n# (arbolArbitrario n) es un \u00e1rbol aleatorio de orden n. Por ejemplo,\n#    >>> arbolArbitrario(4)\n#    N(x=2, i=H(x=1), d=H(x=9))\n#    >>> arbolArbitrario(4)\n#    H(x=10)\n#    >>> arbolArbitrario(4)\n#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))\ndef arbolArbitrario(n: int) -> Arbol[int]:\n    if n <= 1:\n        return H(randint(0, 10))\n    m = n \/\/ 2\n    return choice([H(randint(0, 10)),\n                   N(randint(0, 10),\n                     arbolArbitrario(m),\n                     arbolArbitrario(m))])\n\n# Funciones auxiliares para la comprobaci\u00f3n\n# =========================================\n\n# preorden(x) es la lista correspondiente al recorrido preorden del\n# \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a continuaci\u00f3n\n# recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el sub\u00e1rbol\n# derecho. Por ejemplo,\n#    >>> preorden(N(9, N(3, H(2), H(4)), H(7)))\n#    [9, 3, 2, 4, 7]\ndef preorden(a: Arbol[A]) -> list[A]:\n    match a:\n        case H(x):\n            return [x]\n        case N(x, i, d):\n            return [x] + preorden(i) + preorden(d)\n    assert False\n\n# (postorden x) es la lista correspondiente al recorrido postorden\n# del \u00e1rbol x; es decir, primero recorre el sub\u00e1rbol izquierdo, a\n# continuaci\u00f3n el sub\u00e1rbol derecho y, finalmente, la ra\u00edz del\n# \u00e1rbol. Por ejemplo,\n#    >>> postorden(N(9, N(3, H(2), H(4)), H(7)))\n#    [2, 4, 3, 7, 9]\ndef postorden(a: Arbol[A]) -> list[A]:\n    match a:\n        case H(x):\n            return [x]\n        case N(x, i, d):\n            return postorden(i) + postorden(d) + [x]\n    assert False\n\n# Comprobaci\u00f3n de las propiedades\n# ===============================\n\n# Las propiedades son\n@given(st.integers(min_value=1, max_value=10))\ndef test_espejo(n: int) -> None:\n    x = arbolArbitrario(n)\n    assert espejo(espejo(x)) == x\n    assert list(reversed(preorden(espejo(x)))) == postorden(x)\n    assert postorden(espejo(x)) == list(reversed(preorden(x)))\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q imagen_especular_de_un_arbol_binario.py\n#    1 passed in 0.16s\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Sub\u00e1rbol de profundidad dada<\/h3>\n<p>El \u00e1rbol binario<\/p>\n<pre lang=\"text\">\n        9\n       \/ \\\n      \/   \\\n     3     7\n    \/ \\\n   2   4\n<\/pre>\n<p>se puede representar por<\/p>\n<pre lang=\"text\">\n   N 9 (N 3 (H 2) (H 4)) (H 7)\n<\/pre>\n<p>El tipo de los \u00e1rboles binarios se puede definir por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n     deriving (Show, Eq)\n<\/pre>\n<p>La funci\u00f3n take est\u00e1 definida por<\/p>\n<pre lang=\"text\">\n   take :: Int -> [a] -> [a]\n   take 0            = []\n   take (n+1) []     = []\n   take (n+1) (x:xs) = x : take n xs\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   takeArbol ::  Int -> Arbol a -> Arbol a\n<\/pre>\n<p>tal que <code>takeArbol n t<\/code> es el sub\u00e1rbol de <code>t<\/code> de profundidad <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9\n   takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)\n   takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)\n   takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)\n<\/pre>\n<p>Comprobar con QuickCheck que la profundidad de <code>takeArbol n x<\/code> es menor o igual que <code>n<\/code>, para todo n\u00famero natural <code>n<\/code> y todo \u00e1rbol <code>x<\/code>.<\/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 Test.QuickCheck\n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\ntakeArbol :: Int -> Arbol a -> Arbol a\ntakeArbol _ (H x)     = H x\ntakeArbol 0 (N x _ _) = H x\ntakeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d)\n\n-- Generador para las comprobaciones\n-- =================================\n\n-- (arbolArbitrario n) es un \u00e1rbol aleatorio de altura n. Por ejemplo,\n--    \u03bb> sample (arbolArbitrario 3 :: Gen (Arbol Int))\n--    N 0 (H 0) (H 0)\n--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)\n--    N 3 (H 1) (H 2)\n--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))\n--    H 7\n--    N (-8) (H (-8)) (H 9)\n--    H 2\n--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))\n--    H (-3)\n--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)\n--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario 0 = H <$> arbitrary\narbolArbitrario n =\n  oneof [H <$> arbitrary,\n         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]\n\n-- Arbol es subclase de Arbitrary\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbolArbitrario\n\n-- Funci\u00f3n auxiliar para la comprobaci\u00f3n\n-- =====================================\n\n-- (profundidad x) es la profundidad del \u00e1rbol x. Por ejemplo,\n--    profundidad (N 9 (N 3 (H 2) (H 4)) (H 7))              ==  2\n--    profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7))  ==  3\n--    profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4)))  ==  2\nprofundidad :: Arbol a -> Int\nprofundidad (H _)     = 0\nprofundidad (N _ i d) = 1 + max (profundidad i) (profundidad d)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_takeArbol :: Int -> Arbol Int -> Property\nprop_takeArbol n x =\n  n >= 0 ==> profundidad (takeArbol n x) <= n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_takeArbol\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 dataclasses import dataclass\nfrom random import choice, randint\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar(\"A\")\n\n@dataclass\nclass Arbol(Generic[A]):\n    pass\n\n@dataclass\nclass H(Arbol[A]):\n    x: A\n\n@dataclass\nclass N(Arbol[A]):\n    x: A\n    i: Arbol[A]\n    d: Arbol[A]\n\ndef takeArbol(n: int, a: Arbol[A]) -> Arbol[A]:\n    match (n, a):\n        case (_, H(x)):\n            return H(x)\n        case (0, N(x, _, _)):\n            return H(x)\n        case (n, N(x, i, d)):\n            return N(x, takeArbol(n - 1, i), takeArbol(n - 1, d))\n    assert False\n\n# Generador para las comprobaciones\n# =================================\n\n# (arbolArbitrario n) es un \u00e1rbol aleatorio de orden n. Por ejemplo,\n#    >>> arbolArbitrario(4)\n#    N(x=2, i=H(x=1), d=H(x=9))\n#    >>> arbolArbitrario(4)\n#    H(x=10)\n#    >>> arbolArbitrario(4)\n#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))\ndef arbolArbitrario(n: int) -> Arbol[int]:\n    if n <= 1:\n        return H(randint(0, 10))\n    m = n \/\/ 2\n    return choice([H(randint(0, 10)),\n                   N(randint(0, 10),\n                     arbolArbitrario(m),\n                     arbolArbitrario(m))])\n\n# Funci\u00f3n auxiliar para la comprobaci\u00f3n\n# =====================================\n\n# profundidad(x) es la profundidad del \u00e1rbol x. Por ejemplo,\n#    profundidad(N(9, N(3, H(2), H(4)), H(7)))              ==  2\n#    profundidad(N(9, N(3, H(2), N(1, H(4), H(5))), H(7)))  ==  3\n#    profundidad(N(4, N(5, H(4), H(2)), N(3, H(7), H(4))))  ==  2\ndef profundidad(a: Arbol[A]) -> int:\n    match a:\n        case H(_):\n            return 0\n        case N(_, i, d):\n            return 1 + max(profundidad(i), profundidad(d))\n    assert False\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=12),\n       st.integers(min_value=1, max_value=10))\ndef test_takeArbol(n: int, m: int) -> None:\n    x = arbolArbitrario(m)\n    assert profundidad(takeArbol(n, x)) <= n\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q subarbol_de_profundidad_dada.py\n#    1 passed in 0.23s\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. \u00c1rbol de profundidad n con nodos iguales<\/h3>\n<p>El \u00e1rbol binario<\/p>\n<pre lang=\"text\">\n        9\n       \/ \\\n      \/   \\\n     3     7\n    \/ \\\n   2   4\n<\/pre>\n<p>se puede representar por<\/p>\n<pre lang=\"text\">\n   N 9 (N 3 (H 2) (H 4)) (H 7)\n<\/pre>\n<p>El tipo de los \u00e1rboles binarios se puede definir por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n     deriving (Show, Eq)\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   repeatArbol    :: a -> Arbol a\n   replicateArbol :: Int -> a -> Arbol a\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>repeatArbol x<\/code> es es \u00e1rbol con infinitos nodos <code>x<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     takeArbol 0 (repeatArbol 3) == H 3\n     takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)\n     takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))\n<\/pre>\n<ul>\n<li><code>replicate n x<\/code> es el \u00e1rbol de profundidad <code>n<\/code> cuyos nodos son <code>x<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     replicateArbol 0 5  ==  H 5\n     replicateArbol 1 5  ==  N 5 (H 5) (H 5)\n     replicateArbol 2 5  ==  N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))\n<\/pre>\n<p>Comprobar con QuickCheck que el n\u00famero de hojas de <code>replicateArbol n x<\/code> es <code>2^n<\/code>, para todo n\u00famero natural <code>n<\/code>.<br \/>\n<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 Test.QuickCheck\n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\nrepeatArbol :: a -> Arbol a\nrepeatArbol x = N x t t\n  where t = repeatArbol x\n\nreplicateArbol :: Int -> a -> Arbol a\nreplicateArbol n = takeArbol n . repeatArbol\n\n-- (takeArbol n t) es el sub\u00e1rbol de t de profundidad n. Por ejemplo,\n--    takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9\n--    takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)\n--    takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)\n--    takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)\ntakeArbol :: Int -> Arbol a -> Arbol a\ntakeArbol _ (H x)     = H x\ntakeArbol 0 (N x _ _) = H x\ntakeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d)\n\n-- Generador para las comprobaciones\n-- =================================\n\n-- (arbolArbitrario n) es un \u00e1rbol aleatorio de altura n. Por ejemplo,\n--    \u03bb> sample (arbolArbitrario 3 :: Gen (Arbol Int))\n--    N 0 (H 0) (H 0)\n--    N 1 (N (-2) (H (-1)) (H 1)) (H 2)\n--    N 3 (H 1) (H 2)\n--    N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4))\n--    H 7\n--    N (-8) (H (-8)) (H 9)\n--    H 2\n--    N (-1) (H 7) (N 9 (H (-2)) (H (-8)))\n--    H (-3)\n--    N 0 (N 16 (H (-14)) (H (-18))) (H 7)\n--    N (-16) (H 18) (N (-19) (H (-15)) (H (-18)))\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario 0 = H <$> arbitrary\narbolArbitrario n =\n  oneof [H <$> arbitrary,\n         N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)]\n\n-- Arbol es subclase de Arbitrary\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbolArbitrario\n\n-- Funci\u00f3n auxiliar para la comprobaci\u00f3n\n-- =====================================\n\n-- (nHojas x) es el n\u00famero de hojas del \u00e1rbol x. Por ejemplo,\n--    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3\nnHojas :: Arbol a -> Int\nnHojas (H _)     = 1\nnHojas (N _ i d) = nHojas i + nHojas d\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_replicateArbol :: Int -> Int -> Property\nprop_replicateArbol n x =\n  n >= 0 ==> nHojas (replicateArbol n x) == 2^n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol\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 dataclasses import dataclass\nfrom random import choice, randint\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar(\"A\")\n\n@dataclass\nclass Arbol(Generic[A]):\n    pass\n\n@dataclass\nclass H(Arbol[A]):\n    x: A\n\n@dataclass\nclass N(Arbol[A]):\n    x: A\n    i: Arbol[A]\n    d: Arbol[A]\n\ndef replicateArbol(n: int, x: A) -> Arbol[A]:\n    match n:\n        case 0:\n            return H(x)\n        case n:\n            t = replicateArbol(n - 1, x)\n            return N(x, t, t)\n    assert False\n\n# Generador para las comprobaciones\n# =================================\n\n# (arbolArbitrario n) es un \u00e1rbol aleatorio de orden n. Por ejemplo,\n#    >>> arbolArbitrario(4)\n#    N(x=2, i=H(x=1), d=H(x=9))\n#    >>> arbolArbitrario(4)\n#    H(x=10)\n#    >>> arbolArbitrario(4)\n#    N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6))\ndef arbolArbitrario(n: int) -> Arbol[int]:\n    if n <= 1:\n        return H(randint(0, 10))\n    m = n \/\/ 2\n    return choice([H(randint(0, 10)),\n                   N(randint(0, 10),\n                     arbolArbitrario(m),\n                     arbolArbitrario(m))])\n\n# Funci\u00f3n auxiliar para la comprobaci\u00f3n\n# =====================================\n\n# nHojas(x) es el n\u00famero de hojas del \u00e1rbol x. Por ejemplo,\n#    nHojas(N(9, N(3, H(2), H(4)), H(7)))  ==  3\ndef nHojas(a: Arbol[A]) -> int:\n    match a:\n        case H(_):\n            return 1\n        case N(_, i, d):\n            return nHojas(i) + nHojas(d)\n    assert False\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=1, max_value=10),\n       st.integers(min_value=1, max_value=10))\ndef test_nHojas(n: int, x: int) -> None:\n    assert nHojas(replicateArbol(n, x)) == 2**n\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q arbol_de_profundidad_n_con_nodos_iguales.py\n#    1 passed in 0.20s\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Suma de un \u00e1rbol<\/h3>\n<p>Los \u00e1rboles binarios con valores en los nodos se pueden definir por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H\n                | N a (Arbol1 a) (Arbol1 a)\n     deriving (Show, Eq)\n<\/pre>\n<p>Por ejemplo, el \u00e1rbol<\/p>\n<pre lang=\"text\">\n        9\n       \/ \\\n      \/   \\\n     8     6\n    \/ \\   \/ \\\n   3   2 4   5\n<\/pre>\n<p>se puede representar por<\/p>\n<pre lang=\"text\">\n   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))\n<\/pre>\n<p>Definir por recursi\u00f3n la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   sumaArbol :: Num a => Arbol1 a -> a\n<\/pre>\n<p>tal <code>sumaArbol x<\/code> es la suma de los valores que hay en el \u00e1rbol <code>x<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21\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\">\ndata Arbol1 a = H\n              | N a (Arbol1 a) (Arbol1 a)\n  deriving (Show, Eq)\n\nsumaArbol :: Num a => Arbol1 a -> a\nsumaArbol H         = 0\nsumaArbol (N x i d) = x + sumaArbol i + sumaArbol d\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom dataclasses import dataclass\n\n@dataclass\nclass Arbol:\n    pass\n\n@dataclass\nclass H(Arbol):\n    pass\n\n@dataclass\nclass N(Arbol):\n    x: int\n    i: Arbol\n    d: Arbol\n\ndef sumaArbol(a: Arbol) -> int:\n    match a:\n        case H():\n            return 0\n        case N(x, i, d):\n            return x + sumaArbol(i) + sumaArbol(d)\n    assert False\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Recorrido de \u00e1rboles binarios 2. Imagen especular de un \u00e1rbol binario 3. Sub\u00e1rbol de profundidad dada 4. \u00c1rbol de profundidad n con nodos iguales 5. Suma de un \u00e1rbol A continuaci\u00f3n se muestran las soluciones.<\/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\/7870"}],"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=7870"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7870\/revisions"}],"predecessor-version":[{"id":7871,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7870\/revisions\/7871"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7870"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7870"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7870"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}