PFH: La semana en Exercitium (7 de enero de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Elementos del nivel k de un árbol
- 2. Árbol de factorización
- 3. Valor de un árbol booleano
- 4. Valor de una expresión aritmética básica
- 5. Aplicación de una función a una expresión aritmética
A continuación se muestran las soluciones.
1. Elementos del nivel k de un árbol
Los árboles binarios con valores en las hojas y en los nodos se definen por
|
1 2 |
data Arbol a = H a | N a (Arbol a) (Arbol a) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
7 / \ / \ 2 9 / \ 5 4 |
se representa por
|
1 |
N 7 (N 2 (H 5) (H 4)) (H 9) |
Un elemento de un árbol se dirá de nivel k si aparece en el árbol a distancia k de la raíz.
Definir la función
|
1 |
nivel :: Int -> Arbol a -> [a] |
tal que nivel k a es la lista de los elementos de nivel k del árbol a. Por ejemplo,
|
1 2 3 4 5 6 |
nivel 0 (H 5) == [5] nivel 1 (H 5) == [] nivel 0 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [7] nivel 1 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [2,9] nivel 2 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [5,4] nivel 3 (N 7 (N 2 (H 5) (H 4)) (H 9)) == [] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 |
data Arbol a = H a | N a (Arbol a) (Arbol a) nivel :: Int -> Arbol a -> [a] nivel 0 (H x) = [x] nivel 0 (N x _ _) = [x] nivel _ (H _ ) = [] nivel k (N _ i d) = nivel (k-1) i ++ nivel (k-1) d |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
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] def nivel(k: int, a: Arbol[A]) -> list[A]: match (k, a): case (0, H(x)): return [x] case (0, N(x, _, _)): return [x] case (_, H(_)): return [] case (_, N(_, i, d)): return nivel(k - 1, i) + nivel(k - 1, d) assert False |
2. Árbol de factorización
Los divisores medios de un número son los que ocupan la media entre los divisores de n, ordenados de menor a mayor. Por ejemplo, los divisores de 60 son [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60] y sus divisores medios son 6 y 10. Para los números que son cuadrados perfectos, sus divisores medios de son sus raíces cuadradas; por ejemplos, los divisores medios de 9 son 3 y 3.
El árbol de factorización de un número compuesto n se construye de la siguiente manera:
- la raíz es el número n,
- la rama izquierda es el árbol de factorización de su divisor medio menor y
- la rama derecha es el árbol de factorización de su divisor medio mayor
Si el número es primo, su árbol de factorización sólo tiene una hoja con dicho número. Por ejemplo, el árbol de factorización de 60 es
|
1 2 3 4 5 |
60 / \ 6 10 / \ / \ 2 3 2 5 |
Definir la función
|
1 |
arbolFactorizacion :: Int -> Arbol |
tal que arbolFactorizacion n es el árbol de factorización de n. Por ejemplo,
|
1 2 3 4 5 6 7 |
arbolFactorizacion 60 == N 60 (N 6 (H 2) (H 3)) (N 10 (H 2) (H 5)) arbolFactorizacion 45 == N 45 (H 5) (N 9 (H 3) (H 3)) arbolFactorizacion 7 == H 7 arbolFactorizacion 9 == N 9 (H 3) (H 3) arbolFactorizacion 14 == N 14 (H 2) (H 7) arbolFactorizacion 28 == N 28 (N 4 (H 2) (H 2)) (H 7) arbolFactorizacion 84 == N 84 (H 7) (N 12 (H 3) (N 4 (H 2) (H 2))) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
import Test.QuickCheck -- 1ª solución -- =========== data Arbol = H Int | N Int Arbol Arbol deriving (Eq, Show) arbolFactorizacion1 :: Int -> Arbol arbolFactorizacion1 n | esPrimo n = H n | otherwise = N n (arbolFactorizacion1 x) (arbolFactorizacion1 y) where (x,y) = divisoresMedio n -- (esPrimo n) se verifica si n es primo. Por ejemplo, -- esPrimo 7 == True -- esPrimo 9 == False esPrimo :: Int -> Bool esPrimo n = divisores n == [1,n] -- (divisoresMedio n) es el par formado por los divisores medios de -- n. Por ejemplo, -- divisoresMedio 30 == (5,6) -- divisoresMedio 7 == (1,7) -- divisoresMedio 16 == (4,4) divisoresMedio :: Int -> (Int,Int) divisoresMedio n = (n `div` x,x) where xs = divisores n x = xs !! (length xs `div` 2) -- (divisores n) es la lista de los divisores de n. Por ejemplo, -- divisores 30 == [1,2,3,5,6,10,15,30] divisores :: Int -> [Int] divisores n = [x | x <- [1..n], n `rem` x == 0] -- 2ª solución -- =========== arbolFactorizacion2 :: Int -> Arbol arbolFactorizacion2 n | x == 1 = H n | otherwise = N n (arbolFactorizacion2 x) (arbolFactorizacion2 y) where (x,y) = divisoresMedio n -- (divisoresMedio2 n) es el par formado por los divisores medios de -- n. Por ejemplo, -- divisoresMedio2 30 == (5,6) -- divisoresMedio2 7 == (1,7) divisoresMedio2 :: Int -> (Int,Int) divisoresMedio2 n = (n `div` x,x) where m = ceiling (sqrt (fromIntegral n)) x = head [y | y <- [m..n], n `rem` y == 0] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_arbolFactorizacion :: Int -> Property prop_arbolFactorizacion n = n > 1 ==> arbolFactorizacion1 n == arbolFactorizacion2 n -- La comprobación es -- λ> quickCheck prop_arbolFactorizacion -- +++ OK, passed 100 tests; 162 discarded. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
from dataclasses import dataclass from math import ceil, sqrt from hypothesis import given from hypothesis import strategies as st # 1ª solución # =========== @dataclass class Arbol: pass @dataclass class H(Arbol): x: int @dataclass class N(Arbol): x: int i: Arbol d: Arbol # divisores(n) es la lista de los divisores de n. Por ejemplo, # divisores(30) == [1,2,3,5,6,10,15,30] def divisores(n: int) -> list[int]: return [x for x in range(1, n + 1) if n % x == 0] # divisoresMedio(n) es el par formado por los divisores medios de # n. Por ejemplo, # divisoresMedio(30) == (5,6) # divisoresMedio(7) == (1,7) # divisoresMedio(16) == (4,4) def divisoresMedio(n: int) -> tuple[int, int]: xs = divisores(n) x = xs[len(xs) // 2] return (n // x, x) # esPrimo(n) se verifica si n es primo. Por ejemplo, # esPrimo(7) == True # esPrimo(9) == False def esPrimo(n: int) -> bool: return divisores(n) == [1, n] def arbolFactorizacion1(n: int) -> Arbol: if esPrimo(n): return H(n) (x, y) = divisoresMedio(n) return N(n, arbolFactorizacion1(x), arbolFactorizacion1(y)) # 2ª solución # =========== # divisoresMedio2(n) es el par formado por los divisores medios de # n. Por ejemplo, # divisoresMedio2(30) == (5,6) # divisoresMedio2(7) == (1,7) # divisoresMedio2(16) == (4,4) def divisoresMedio2(n: int) -> tuple[int, int]: m = ceil(sqrt(n)) x = [y for y in range(m, n + 1) if n % y == 0][0] return (n // x, x) def arbolFactorizacion2(n: int) -> Arbol: if esPrimo(n): return H(n) (x, y) = divisoresMedio2(n) return N(n, arbolFactorizacion2(x), arbolFactorizacion2(y)) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=2, max_value=200)) def test_arbolFactorizacion(n: int) -> None: assert arbolFactorizacion1(n) == arbolFactorizacion2(n) # La comprobación es # src> poetry run pytest -q arbol_de_factorizacion.py # 1 passed in 0.14s |
3. Valor de un árbol booleano
Se consideran los árboles con operaciones booleanas definidos por
|
1 2 3 4 |
data Arbol = H Bool | Conj Arbol Arbol | Disy Arbol Arbol | Neg Arbol |
Por ejemplo, los árboles
|
1 2 3 4 5 6 7 8 |
Conj Conj / \ / \ / \ / \ Disy Conj Disy Conj / \ / \ / \ / \ Conj Neg Neg True Conj Neg Neg True / \ | | / \ | | True False False False True False True False |
se definen por
|
1 2 3 4 5 6 7 8 9 10 |
ej1, ej2:: Arbol ej1 = Conj (Disy (Conj (H True) (H False)) (Neg (H False))) (Conj (Neg (H False)) (H True)) ej2 = Conj (Disy (Conj (H True) (H False)) (Neg (H True))) (Conj (Neg (H False)) (H True)) |
Definir la función
|
1 |
valor :: Arbol -> Bool |
tal que valor a) es el resultado de procesar el árbol a realizando las operaciones booleanas especificadas en los nodos. Por ejemplo,
|
1 2 |
valor ej1 == True valor ej2 == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
data Arbol = H Bool | Conj Arbol Arbol | Disy Arbol Arbol | Neg Arbol ej1, ej2 :: Arbol ej1 = Conj (Disy (Conj (H True) (H False)) (Neg (H False))) (Conj (Neg (H False)) (H True)) ej2 = Conj (Disy (Conj (H True) (H False)) (Neg (H True))) (Conj (Neg (H False)) (H True)) valor :: Arbol -> Bool valor (H x) = x valor (Neg a) = not (valor a) valor (Conj i d) = valor i && valor d valor (Disy i d) = valor i || valor d |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
from dataclasses import dataclass @dataclass class Arbol: pass @dataclass class H(Arbol): x: bool @dataclass class Conj(Arbol): i: Arbol d: Arbol @dataclass class Disy(Arbol): i: Arbol d: Arbol @dataclass class Neg(Arbol): a: Arbol ej1: Arbol = Conj(Disy(Conj(H(True), H(False)), (Neg(H(False)))), (Conj(Neg(H(False)), (H(True))))) ej2: Arbol = Conj(Disy(Conj(H(True), H(False)), (Neg(H(True)))), (Conj(Neg(H(False)), (H(True))))) def valor(a: Arbol) -> bool: match a: case H(x): return x case Neg(b): return not valor(b) case Conj(i, d): return valor(i) and valor(d) case Disy(i, d): return valor(i) or valor(d) assert False |
4. Valor de una expresión aritmética básica
Las expresiones aritméticas básicas pueden representarse usando el siguiente tipo de datos
|
1 2 3 |
data Expr = C Int | S Expr Expr | P Expr Expr |
Por ejemplo, la expresión 2*(3+7) se representa por
|
1 |
P (C 2) (S (C 3) (C 7)) |
Definir la función
|
1 |
valor :: Expr -> Int |
tal que valor e es el valor de la expresión aritmética e. Por ejemplo,
|
1 |
valor (P (C 2) (S (C 3) (C 7))) == 20 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 |
data Expr = C Int | S Expr Expr | P Expr Expr valor :: Expr -> Int valor (C x) = x valor (S x y) = valor x + valor y valor (P x y) = valor x * valor y |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
from dataclasses import dataclass @dataclass class Expr: pass @dataclass class C(Expr): x: int @dataclass class S(Expr): x: Expr y: Expr @dataclass class P(Expr): x: Expr y: Expr def valor(e: Expr) -> int: match e: case C(x): return x case S(x, y): return valor(x) + valor(y) case P(x, y): return valor(x) * valor(y) assert False |
5. Aplicación de una función a una expresión aritmética
Las expresiones aritméticas básicas pueden representarse usando el siguiente tipo de datos
|
1 2 3 4 |
data Expr = C Int | S Expr Expr | P Expr Expr deriving (Show, Eq) |
Por ejemplo, la expresión 2*(3+7) se representa por
|
1 |
P (C 2) (S (C 3) (C 7)) |
Definir la función
|
1 |
aplica :: (Int -> Int) -> Expr -> Expr |
tal que aplica f e es la expresión obtenida aplicando la función f a cada uno de los números de la expresión e. Por ejemplo,
|
1 2 3 4 |
λ> aplica (+2) (S (P (C 3) (C 5)) (P (C 6) (C 7))) S (P (C 5) (C 7)) (P (C 8) (C 9)) λ> aplica (*2) (S (P (C 3) (C 5)) (P (C 6) (C 7))) S (P (C 6) (C 10)) (P (C 12) (C 14)) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 |
data Expr = C Int | S Expr Expr | P Expr Expr deriving (Show, Eq) aplica :: (Int -> Int) -> Expr -> Expr aplica f (C x) = C (f x) aplica f (S e1 e2) = S (aplica f e1) (aplica f e2) aplica f (P e1 e2) = P (aplica f e1) (aplica f e2) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
from dataclasses import dataclass from typing import Callable @dataclass class Expr: pass @dataclass class C(Expr): x: int @dataclass class S(Expr): x: Expr y: Expr @dataclass class P(Expr): x: Expr y: Expr def aplica(f: Callable[[int], int], e: Expr) -> Expr: match e: case C(x): return C(f(x)) case S(x, y): return S(aplica(f, x), aplica(f, y)) case P(x, y): return P(aplica(f, x), aplica(f, y)) assert False |