{"id":7872,"date":"2022-12-31T08:37:39","date_gmt":"2022-12-31T07:37:39","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7872"},"modified":"2022-12-31T08:37:39","modified_gmt":"2022-12-31T07:37:39","slug":"31-dic-22","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/31-dic-22\/","title":{"rendered":"PFH: La semana en Exercitium (31 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. Rama izquierda de un \u00e1rbol binario<\/a><\/li>\n<li><a href=\"#ej2\">2. \u00c1rboles balanceados<\/a><\/li>\n<li><a href=\"#ej3\">3. \u00c1rboles con bordes iguales<\/a><\/li>\n<li><a href=\"#ej4\">4. \u00c1rboles con igual estructura<\/a><\/li>\n<li><a href=\"#ej5\">5. Existencia de elementos del \u00e1rbol que verifican una propiedad<\/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. Rama izquierda de un \u00e1rbol binario<\/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 (Arbol a) (Arbol 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 la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ramaIzquierda :: Arbol a -> [a]\n<\/pre>\n<p>tal que <code>ramaIzquierda a<\/code> es la lista de los valores de los nodos de la rama izquierda del \u00e1rbol <code>a<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H))\n   [2,5,3]\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 Arbol a = H\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\nramaIzquierda :: Arbol a -> [a]\nramaIzquierda H         = []\nramaIzquierda (N x i _) = x : ramaIzquierda i\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 typing import Generic, TypeVar\n\nA = TypeVar(\"A\")\n\n@dataclass\nclass Arbol(Generic[A]):\n    pass\n\n@dataclass\nclass H(Arbol[A]):\n    pass\n\n@dataclass\nclass N(Arbol[A]):\n    x: A\n    i: Arbol[A]\n    d: Arbol[A]\n\ndef ramaIzquierda(a: Arbol[A]) -> list[A]:\n    match a:\n        case H():\n            return []\n        case N(x, i, _):\n            return [x] + ramaIzquierda(i)\n    assert False\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. \u00c1rboles balanceados<\/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 (Arbol a) (Arbol 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>Diremos que un \u00e1rbol est\u00e1 balanceado si para cada nodo la diferencia entre el n\u00famero de nodos de sus sub\u00e1rboles izquierdo y derecho es menor o igual que uno.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   balanceado :: Arbol a -> Bool\n<\/pre>\n<p>tal que (balanceado a) se verifica si el \u00e1rbol a est\u00e1 balanceado. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> balanceado (N 5 H (N 3 H H))\n   True\n   \u03bb> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H))))\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\">\ndata Arbol a = H\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\nbalanceado :: Arbol a -> Bool\nbalanceado H         = True\nbalanceado (N _ i d) = abs (numeroNodos i - numeroNodos d) <= 1\n                       &#038;&#038; balanceado i\n                       &#038;&#038; balanceado d\n\n-- (numeroNodos a) es el n\u00famero de nodos del \u00e1rbol a. Por ejemplo,\n--    numeroNodos (N 5 H (N 3 H H)) ==  2\nnumeroNodos :: Arbol a -> Int\nnumeroNodos H         = 0\nnumeroNodos (N _ i d) = 1 + numeroNodos i + numeroNodos 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\nfrom typing import Generic, TypeVar\n\nA = TypeVar(\"A\")\n\n@dataclass\nclass Arbol(Generic[A]):\n    pass\n\n@dataclass\nclass H(Arbol[A]):\n    pass\n\n@dataclass\nclass N(Arbol[A]):\n    x: A\n    i: Arbol[A]\n    d: Arbol[A]\n\ndef numeroNodos(a: Arbol[A]) -> int:\n    match a:\n        case H():\n            return 0\n        case N(_, i, d):\n            return 1 + numeroNodos(i) + numeroNodos(d)\n    assert False\n\ndef balanceado(a: Arbol[A]) -> bool:\n    match a:\n        case H():\n            return True\n        case N(_, i, d):\n            return abs(numeroNodos(i) - numeroNodos(d)) <= 1 \\\n                and balanceado(i) and balanceado(d)\n    assert False\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. \u00c1rboles con bordes iguales<\/h3>\n<p>Los \u00e1rboles binarios con valores en las hojas se pueden definir por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N (Arbol a) (Arbol a)\n     deriving Show\n<\/pre>\n<p>Por ejemplo, los \u00e1rboles<\/p>\n<pre lang=\"text\">\n   \u00e1rbol1          \u00e1rbol2       \u00e1rbol3     \u00e1rbol4\n      o              o           o           o\n     \/ \\            \/ \\         \/ \\         \/ \\\n    1   o          o   3       o   3       o   1\n       \/ \\        \/ \\         \/ \\         \/ \\\n      2   3      1   2       1   4       2   3\n<\/pre>\n<p>se representan por<\/p>\n<pre lang=\"text\">\n   arbol1, arbol2, arbol3, arbol4 :: Arbol Int\n   arbol1 = N (H 1) (N (H 2) (H 3))\n   arbol2 = N (N (H 1) (H 2)) (H 3)\n   arbol3 = N (N (H 1) (H 4)) (H 3)\n   arbol4 = N (N (H 2) (H 3)) (H 1)\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   igualBorde :: Eq a => Arbol a -> Arbol a -> Bool\n<\/pre>\n<p>tal que <code>igualBorde t1 t2<\/code> se verifica si los bordes de los \u00e1rboles <code>t1<\/code> y <code>t2<\/code> son iguales. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   igualBorde arbol1 arbol2  ==  True\n   igualBorde arbol1 arbol3  ==  False\n   igualBorde arbol1 arbol4  ==  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\">\ndata Arbol a = N (Arbol a) (Arbol a)\n             | H a\n  deriving Show\n\narbol1, arbol2, arbol3, arbol4 :: Arbol Int\narbol1 = N (H 1) (N (H 2) (H 3))\narbol2 = N (N (H 1) (H 2)) (H 3)\narbol3 = N (N (H 1) (H 4)) (H 3)\narbol4 = N (N (H 2) (H 3)) (H 1)\n\nigualBorde :: Eq a => Arbol a -> Arbol a -> Bool\nigualBorde t1 t2 = borde t1 == borde t2\n\n-- (borde t) es el borde del \u00e1rbol t; es decir, la lista de las hojas\n-- del \u00e1rbol t le\u00eddas de izquierda a derecha. Por ejemplo,\n--    borde arbol4  ==  [2,3,1]\nborde :: Arbol a -> [a]\nborde (N i d) = borde i ++ borde d\nborde (H x)   = [x]\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 typing import Generic, TypeVar\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    i: Arbol[A]\n    d: Arbol[A]\n\narbol1: Arbol[int] = N(H(1), N(H(2), H(3)))\narbol2: Arbol[int] = N(N(H(1), H(2)), H(3))\narbol3: Arbol[int] = N(N(H(1), H(4)), H(3))\narbol4: Arbol[int] = N(N(H(2), H(3)), H(1))\n\n# borde(t) es el borde del \u00e1rbol t; es decir, la lista de las hojas\n# del \u00e1rbol t le\u00eddas de izquierda a derecha. Por ejemplo,\n#    borde(arbol4)  ==  [2, 3, 1]\ndef borde(a: Arbol[A]) -> list[A]:\n    match a:\n        case H(x):\n            return [x]\n        case N(i, d):\n            return borde(i) + borde(d)\n    assert False\n\ndef igualBorde(t1: Arbol[A], t2: Arbol[A]) -> bool:\n    return borde(t1) == borde(t2)\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. \u00c1rboles con igual estructura<\/h3>\n<p>Los \u00e1rboles binarios con valores en las hojas y en los nodos se definen por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n     deriving Show\n<\/pre>\n<p>Por ejemplo, los \u00e1rboles<\/p>\n<pre lang=\"text\">\n        5              8             5           5\n       \/ \\            \/ \\           \/ \\         \/ \\\n      \/   \\          \/   \\         \/   \\       \/   \\\n     9     7        9     3       9     2     4     7\n    \/ \\   \/ \\      \/ \\   \/ \\     \/ \\               \/ \\\n   1   4 6   8    1   4 6   2   1   4             6   2\n<\/pre>\n<p>se pueden representar por<\/p>\n<pre lang=\"text\">\n   ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int\n   ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))\n   ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))\n   ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)\n   ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   igualEstructura :: Arbol -> Arbol -> Bool\n<\/pre>\n<p>tal que <code>igualEstructura a1 a2<\/code> se verifica si los \u00e1rboles <code>a1<\/code> y <code>a2<\/code> tienen la misma estructura. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   igualEstructura ej3arbol1 ej3arbol2 == True\n   igualEstructura ej3arbol1 ej3arbol3 == False\n   igualEstructura ej3arbol1 ej3arbol4 == 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\">\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\nej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int\nej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))\nej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))\nej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)\nej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))\n\nigualEstructura :: Arbol a -> Arbol a -> Bool\nigualEstructura (H _) (H _)             = True\nigualEstructura (N _ i1 d1) (N _ i2 d2) =\n  igualEstructura i1 i2 &&\n  igualEstructura d1 d2\nigualEstructura _ _                       = False\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 typing import Generic, TypeVar\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\nej3arbol1: Arbol[int] = N(5, N(9, H(1), H(4)), N(7, H(6), H(8)))\nej3arbol2: Arbol[int] = N(8, N(9, H(1), H(4)), N(3, H(6), H(2)))\nej3arbol3: Arbol[int] = N(5, N(9, H(1), H(4)), H(2))\nej3arbol4: Arbol[int] = N(5, H(4), N(7, H(6), H(2)))\n\ndef igualEstructura(a: Arbol[A], b: Arbol[A]) -> bool:\n    match (a, b):\n        case (H(_), H(_)):\n            return True\n        case (N(_, i1, d1), N(_, i2, d2)):\n            return igualEstructura(i1, i2) and igualEstructura(d1, d2)\n        case (_, _):\n            return False\n    assert False\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Existencia de elementos del \u00e1rbol que verifican una propiedad<\/h3>\n<p>Los \u00e1rboles binarios con valores en las hojas y en los nodos se definen por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N a (Arbol a) (Arbol a)\n     deriving Show\n<\/pre>\n<p>Por ejemplo, el \u00e1rbol<\/p>\n<pre lang=\"text\">\n        5\n       \/ \\\n      \/   \\\n     3     2\n    \/ \\\n   1   4\n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   N 5 (N 3 (H 1) (H 4)) (H 2)\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   algunoArbol :: Arbol t -> (t -> Bool) -> Bool\n<\/pre>\n<p>tal que <code>algunoArbol a p<\/code> se verifica si alg\u00fan elemento del \u00e1rbol <code>a<\/code> cumple la propiedad <code>p<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4)  ==  True\n   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7)  ==  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\">\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n  deriving Show\n\nalgunoArbol :: Arbol a -> (a -> Bool) -> Bool\nalgunoArbol (H x) p     = p x\nalgunoArbol (N x i d) p = p x || algunoArbol i p || algunoArbol d p\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 typing import Callable, Generic, TypeVar\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 algunoArbol(a: Arbol[A], p: Callable[[A], bool]) -> bool:\n    match a:\n        case H(x):\n            return p(x)\n        case N(x, i, d):\n            return p(x) or algunoArbol(i, p) or algunoArbol(d, p)\n    assert False\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Rama izquierda de un \u00e1rbol binario 2. \u00c1rboles balanceados 3. \u00c1rboles con bordes iguales 4. \u00c1rboles con igual estructura 5. Existencia de elementos del \u00e1rbol que verifican una propiedad 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\/7872"}],"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=7872"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7872\/revisions"}],"predecessor-version":[{"id":7873,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7872\/revisions\/7873"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7872"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7872"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7872"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}