Menu Close

PFH: La semana en Exercitium (31 de diciembre de 2022)

José A. Alonso-

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

A continuación se muestran las soluciones.

1. Rama izquierda de un árbol binario

Los árboles binarios con valores en los nodos se pueden definir por

   data Arbol a = H
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Definir la función

   ramaIzquierda :: Arbol a -> [a]

tal que ramaIzquierda a es la lista de los valores de los nodos de la rama izquierda del árbol a. Por ejemplo,

   λ> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H))
   [2,5,3]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)
 
ramaIzquierda :: Arbol a -> [a]
ramaIzquierda H         = []
ramaIzquierda (N x i _) = x : ramaIzquierda i


Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class H(Arbol[A]):
    pass
 
@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]
 
def ramaIzquierda(a: Arbol[A]) -> list[A]:
    match a:
        case H():
            return []
        case N(x, i, _):
            return [x] + ramaIzquierda(i)
    assert False

2. Árboles balanceados

Los árboles binarios con valores en los nodos se pueden definir por

   data Arbol a = H
                | N a (Arbol a) (Arbol a)
     deriving (Show, Eq)

Por ejemplo, el árbol

        9
       / \
      /   \
     8     6
    / \   / \
   3   2 4   5

se puede representar por

   N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Diremos que un árbol está balanceado si para cada nodo la diferencia entre el número de nodos de sus subárboles izquierdo y derecho es menor o igual que uno.

Definir la función

   balanceado :: Arbol a -> Bool

tal que (balanceado a) se verifica si el árbol a está balanceado. Por ejemplo,

   λ> balanceado (N 5 H (N 3 H H))
   True
   λ> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H))))
   False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)
 
balanceado :: Arbol a -> Bool
balanceado H         = True
balanceado (N _ i d) = abs (numeroNodos i - numeroNodos d) <= 1
                       && balanceado i
                       && balanceado d
 
-- (numeroNodos a) es el número de nodos del árbol a. Por ejemplo,
--    numeroNodos (N 5 H (N 3 H H)) ==  2
numeroNodos :: Arbol a -> Int
numeroNodos H         = 0
numeroNodos (N _ i d) = 1 + numeroNodos i + numeroNodos d


Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class H(Arbol[A]):
    pass
 
@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]
 
def numeroNodos(a: Arbol[A]) -> int:
    match a:
        case H():
            return 0
        case N(_, i, d):
            return 1 + numeroNodos(i) + numeroNodos(d)
    assert False
 
def balanceado(a: Arbol[A]) -> bool:
    match a:
        case H():
            return True
        case N(_, i, d):
            return abs(numeroNodos(i) - numeroNodos(d)) <= 1 \
                and balanceado(i) and balanceado(d)
    assert False

3. Árboles con bordes iguales

Los árboles binarios con valores en las hojas se pueden definir por

   data Arbol a = H a
                | N (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, los árboles

   árbol1          árbol2       árbol3     árbol4
      o              o           o           o
     / \            / \         / \         / \
    1   o          o   3       o   3       o   1
       / \        / \         / \         / \
      2   3      1   2       1   4       2   3

se representan por

   arbol1, arbol2, arbol3, arbol4 :: Arbol Int
   arbol1 = N (H 1) (N (H 2) (H 3))
   arbol2 = N (N (H 1) (H 2)) (H 3)
   arbol3 = N (N (H 1) (H 4)) (H 3)
   arbol4 = N (N (H 2) (H 3)) (H 1)

Definir la función

   igualBorde :: Eq a => Arbol a -> Arbol a -> Bool

tal que igualBorde t1 t2 se verifica si los bordes de los árboles t1 y t2 son iguales. Por ejemplo,

   igualBorde arbol1 arbol2  ==  True
   igualBorde arbol1 arbol3  ==  False
   igualBorde arbol1 arbol4  ==  False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol a = N (Arbol a) (Arbol a)
             | H a
  deriving Show
 
arbol1, arbol2, arbol3, arbol4 :: Arbol Int
arbol1 = N (H 1) (N (H 2) (H 3))
arbol2 = N (N (H 1) (H 2)) (H 3)
arbol3 = N (N (H 1) (H 4)) (H 3)
arbol4 = N (N (H 2) (H 3)) (H 1)
 
igualBorde :: Eq a => Arbol a -> Arbol a -> Bool
igualBorde t1 t2 = borde t1 == borde t2
 
-- (borde t) es el borde del árbol t; es decir, la lista de las hojas
-- del árbol t leídas de izquierda a derecha. Por ejemplo,
--    borde arbol4  ==  [2,3,1]
borde :: Arbol a -> [a]
borde (N i d) = borde i ++ borde d
borde (H x)   = [x]


Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class H(Arbol[A]):
    x: A
 
@dataclass
class N(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]
 
arbol1: Arbol[int] = N(H(1), N(H(2), H(3)))
arbol2: Arbol[int] = N(N(H(1), H(2)), H(3))
arbol3: Arbol[int] = N(N(H(1), H(4)), H(3))
arbol4: Arbol[int] = N(N(H(2), H(3)), H(1))
 
# borde(t) es el borde del árbol t; es decir, la lista de las hojas
# del árbol t leídas de izquierda a derecha. Por ejemplo,
#    borde(arbol4)  ==  [2, 3, 1]
def borde(a: Arbol[A]) -> list[A]:
    match a:
        case H(x):
            return [x]
        case N(i, d):
            return borde(i) + borde(d)
    assert False
 
def igualBorde(t1: Arbol[A], t2: Arbol[A]) -> bool:
    return borde(t1) == borde(t2)

4. Árboles con igual estructura

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, los árboles

        5              8             5           5
       / \            / \           / \         / \
      /   \          /   \         /   \       /   \
     9     7        9     3       9     2     4     7
    / \   / \      / \   / \     / \               / \
   1   4 6   8    1   4 6   2   1   4             6   2

se pueden representar por

   ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int
   ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
   ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))
   ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)
   ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

Definir la función

   igualEstructura :: Arbol -> Arbol -> Bool

tal que igualEstructura a1 a2 se verifica si los árboles a1 y a2 tienen la misma estructura. Por ejemplo,

   igualEstructura ej3arbol1 ej3arbol2 == True
   igualEstructura ej3arbol1 ej3arbol3 == False
   igualEstructura ej3arbol1 ej3arbol4 == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)
 
ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int
ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))
ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)
ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))
 
igualEstructura :: Arbol a -> Arbol a -> Bool
igualEstructura (H _) (H _)             = True
igualEstructura (N _ i1 d1) (N _ i2 d2) =
  igualEstructura i1 i2 &&
  igualEstructura d1 d2
igualEstructura _ _                       = False


Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class H(Arbol[A]):
    x: A
 
@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]
 
ej3arbol1: Arbol[int] = N(5, N(9, H(1), H(4)), N(7, H(6), H(8)))
ej3arbol2: Arbol[int] = N(8, N(9, H(1), H(4)), N(3, H(6), H(2)))
ej3arbol3: Arbol[int] = N(5, N(9, H(1), H(4)), H(2))
ej3arbol4: Arbol[int] = N(5, H(4), N(7, H(6), H(2)))
 
def igualEstructura(a: Arbol[A], b: Arbol[A]) -> bool:
    match (a, b):
        case (H(_), H(_)):
            return True
        case (N(_, i1, d1), N(_, i2, d2)):
            return igualEstructura(i1, i2) and igualEstructura(d1, d2)
        case (_, _):
            return False
    assert False

5. Existencia de elementos del árbol que verifican una propiedad

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving Show

Por ejemplo, el árbol

        5
       / \
      /   \
     3     2
    / \
   1   4

se representa por

   N 5 (N 3 (H 1) (H 4)) (H 2)

Definir la función

   algunoArbol :: Arbol t -> (t -> Bool) -> Bool

tal que algunoArbol a p se verifica si algún elemento del árbol a cumple la propiedad p. Por ejemplo,

   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4)  ==  True
   algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7)  ==  False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving Show
 
algunoArbol :: Arbol a -> (a -> Bool) -> Bool
algunoArbol (H x) p     = p x
algunoArbol (N x i d) p = p x || algunoArbol i p || algunoArbol d p


Soluciones en Python

from dataclasses import dataclass
from typing import Callable, Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class H(Arbol[A]):
    x: A
 
@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]
 
def algunoArbol(a: Arbol[A], p: Callable[[A], bool]) -> bool:
    match a:
        case H(x):
            return p(x)
        case N(x, i, d):
            return p(x) or algunoArbol(i, p) or algunoArbol(d, p)
    assert False
PFH