Relación 30

-- I1M: Relación 30
-- Repaso del curso
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================

-- ============================================================================
-- Librerías
-- ============================================================================

import Data.List
import Test.QuickCheck

import qualified Data.Array as A
import qualified Data.Matrix as M

import PolinomioConListaDispersa
import GrafoConMatrizDeAdyacencia

-- ----------------------------------------------------------------------------
--
-- Ejercicio 1.1. Un número de n dígitos es un número de Armstrong si
-- es igual a la suma de las n-ésimas potencias de sus dígitos. Por ejemplo,
-- 371, 8208 y 4210818 son números de Armstrong ya que 
--        371 = 3^3 + 7^3 + 1^3
--       8208 = 8^4 + 2^4 + 0^4 + 8^4
--    4210818 = 4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7
--
-- Definir la función
--   esArmstrong :: Integer -> Bool
-- tal que '(esArmstrong m)' se verifica si el número natural 'm' es un número
-- de Armstrong. Por ejemplo,
--   esArmstrong 371                                      ==  True
--   esArmstrong 8208                                     ==  True
--   esArmstrong 4210818                                  ==  True
--   esArmstrong 2022                                     ==  False
--   esArmstrong 115132219018763992565095597973971522401  ==  True
--   esArmstrong 115132219018763992565095597973971522402  ==  False
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

esArmstrong :: Integer -> Bool
esArmstrong m = sum [(read [x] :: Integer)^n | x <- show m] == m
            where n = length (show m)
                  
-- ----------------------------------------------------------------------------
--
-- Ejercicio 1.2. Definir la función
--   armstrong :: [Integer]
-- tal que 'armstrong' es la lista formada por todos los números de Armstrong
-- en orden creciente. Por ejemplo,
--   take 18 armstrong  ==
--     [1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727]
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

armstrong :: [Integer]
armstrong = [x | x <- [1..], esArmstrong x]

-- ----------------------------------------------------------------------------
--
-- Ejercicio 2.1. Se dice que el número A es un divisor propio maximal
-- del número B si A es un divisor de B distinto de B y no existe ningún número
-- C tal que A < C < B, con A divisor de C y C divisor de B. Por ejemplo, 15 es
-- un divisor propio maximal de 30, pero 5 no lo es.
--
-- El árbol de los divisores de un número N es el árbol que tiene como raíz el
-- número N y cada nodo tiene como hijos sus divisores propios maximales. Por
-- ejemplo, el árbol de divisores de 30 es 
--
--           30
--           /|\
--          / | \
--         /  |  \
--        /   |   \
--       /    |    \
--      6    10    15
--     / \   / \   / \
--    2   3 2   5 3   5
--    |   | |   | |   |
--    1   1 1   1 1   1
--
-- Usando el tipo de dato
--    data Arbol = N Integer [Arbol]
--      deriving (Eq, Show)
-- el árbol anterior se representa por
--    N 30
--      [N 6
--         [N 2 [N 1 []],
--          N 3 [N 1 []]],
--       N 10
--         [N 2 [N 1 []],
--          N 5 [N 1 []]],
--       N 15
--         [N 3 [N 1 []],
--          N 5 [N 1 []]]]
--
-- Definir la función
--   arbolDivisores :: Integer -> Arbol
-- tal que '(arbolDivisores n)' es el árbol de los divisores del número natural
-- 'n'. Por ejemplo,  
--   arbolDivisores 30  ==
--     N 30 [N 6  [N 2 [N 1 []],N 3 [N 1 []]],
--           N 10 [N 2 [N 1 []],N 5 [N 1 []]],
--           N 15 [N 3 [N 1 []],N 5 [N 1 []]]]

-- ----------------------------------------------------------------------------

data Arbol = N Integer [Arbol]
           deriving (Eq, Show)


-- Álvaro Galisteo: 

arbolDivisores :: Integer -> Arbol
arbolDivisores n | n == 1 = N 1 []
                 | otherwise = N n (map arbolDivisores (divisoresMaximales n))

divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..(div n 2)], mod n x == 0]

divisoresMaximales :: Integer -> [Integer]
divisoresMaximales n = filter (\ a -> not (any (\ b -> mod b a == 0) (tail(dropWhile (/= a) (divisores n)))) ) (divisores n)
                    

-- ----------------------------------------------------------------------------
--
-- Ejercicio 2.2 Definir la función
--   nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
-- tal que '(nOcurrenciasArbolDivisores x n) es el número de veces que aparece
-- el número 'x' en el árbol de los divisores del número natural 'n'. Por
-- ejemplo,
--   nOcurrenciasArbolDivisores  3 30  ==  2
--   nOcurrenciasArbolDivisores  6 30  ==  1
--   nOcurrenciasArbolDivisores 30 30  ==  1
--   nOcurrenciasArbolDivisores  1 30  ==  6
--   nOcurrenciasArbolDivisores  9 30  ==  0
--   nOcurrenciasArbolDivisores  2 (product [1..10])  ==  360360
--   nOcurrenciasArbolDivisores  3 (product [1..10])  ==  180180
--   nOcurrenciasArbolDivisores  5 (product [1..10])  ==  90090
--   nOcurrenciasArbolDivisores  7 (product [1..10])  ==  45045
--   nOcurrenciasArbolDivisores  6 (product [1..10])  ==  102960
--   nOcurrenciasArbolDivisores 10 (product [1..10])  ==  51480
--   nOcurrenciasArbolDivisores 14 (product [1..10])  ==  25740
-- 
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
nOcurrenciasArbolDivisores x n = nOcurrenciasAux (arbolDivisores n) x

nOcurrenciasAux :: Arbol -> Integer -> Integer
nOcurrenciasAux (N n a) x | n == x = sum [nOcurrenciasAux z x | z <- a] + 1
                          | otherwise = sum [nOcurrenciasAux z x | z <- a]



-- ----------------------------------------------------------------------------
-- 
-- Ejercicio 3. El problema del número de emparejamientos de amigos
-- consiste en calcular el número de formas de emparejar n amigos teniendo en
-- cuenta que cada uno puede permanecer soltero o puede ser emparejado con
-- algún otro amigo y que cada amigo puede ser emparejado sólo una vez. Por
-- ejemplo, los 4 posibles emparejamientos de 3 amigos son   
--    {1}, {2}, {3} 
--    {1}, {2, 3} 
--    {1, 2}, {3} 
--    {1, 3}, {2}
--
-- Definir, usando programación dinámica, la función
--   nEmparejamientos :: Integer -> Integer
-- tal que '(nEmparejamientos n)' es el número de formas de emparejar a los 'n'
-- amigos. Por ejemplo,
--   nEmparejamientos 2   ==  2
--   nEmparejamientos 3   ==  4
--   nEmparejamientos 4   ==  10
--   nEmparejamientos 10  ==  9496
--   nEmparejamientos 30  ==  606917269909048576
--   length (show (nEmparejamientos (10^4)))  ==  17872
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

nEmparejamientos :: Integer -> Integer
nEmparejamientos n = m A.! n
                    where m = A.array (1,n) [(i,f i) | i <- [1..n]]
                          f i | i == 1 = 1
                              | i == 2 = 2
                              | otherwise = m A.! (i-1) + (i - 1 ) * m A.! (i-2)
                              
                              
-- ----------------------------------------------------------------------------
--
-- Ejercicio 4. El grafo de divisibilidad de orden n es el grafo cuyos nodos
-- son los números naturales entre 1 y n, cuyas aristas son los pares (x,y)
-- tales que x divide a y o y divide a y el coste de cada arista es el cociente
-- entre su mayor y menor elemento.
--
-- Definir la siguiente función:
--  grafoDivisibilidad :: Int -> Grafo Int Int
-- tal que
-- (grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,
--    grafoDivisibilidad 12 == 
-- G[ND] N:{1,2,3,4,5,6,7,8,9,10,11,12}
--       A:{(1,2)[2],(1,3)[3],(1,4)[4],(1,5)[5],(1,6)[6],
--          (1,7)[7],(1,8)[8],(1,9)[9],(1,10)[10],(1,11)[11],(1,12)[12],
--          (2,1)[2],(2,4)[2],(2,6)[3],(2,8)[4],(2,10)[5],(2,12)[6],
--          (3,1)[3],(3,6)[2],(3,9)[3],(3,12)[4],
--          (4,1)[4],(4,2)[2],(4,8)[2],(4,12)[3],
--          (5,1)[5],(5,10)[2],
--          (6,1)[6],(6,2)[3],(6,3)[2],(6,12)[2],
--          (7,1)[7],
--          (8,1)[8],(8,2)[4],(8,4)[2],
--          (9,1)[9],(9,3)[3],
--          (10,1)[10],(10,2)[5],(10,5)[2],
--          (11,1)[11],(12,1)[12],
--          (12,2)[6],(12,3)[4],(12,4)[3],(12,6)[2]}
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

grafoDivisibilidad :: Int -> Grafo Int Int
grafoDivisibilidad n = asignaPesos (creaGrafo ND (1,n) [(i,j) | i <- [1..n], j <- [1..n], mod i j == 0 || mod j i == 0, i /= j]) [((i,j), f (i,j)) | i <- [1..n], j <- [1..n], mod i j == 0 || mod j i == 0, i /= j]
                   where f (i,j) = div (max i j) (min i j)

-- ----------------------------------------------------------------------------
--
-- Ejercicio 5. Definir la función
--   eliminaUnitarias :: Char -> String -> String
-- tal que '(eliminaUnitarias c cs)' es la lista obtenida eliminando de la
-- cadena 'cs' las ocurrencias unitarias del carácter 'c' (es decir, aquellas
-- ocurrencias de 'c' tales que su elemento anterior y posterior es distinto de
-- 'c'). Por ejemplo,
--   eliminaUnitarias 'X' ""                  == ""
--   eliminaUnitarias 'X' "X"                 == ""
--   eliminaUnitarias 'X' "XX"                == "XX"
--   eliminaUnitarias 'X' "XXX"               == "XXX"
--   eliminaUnitarias 'X' "abcd"              == "abcd"
--   eliminaUnitarias 'X' "Xabcd"             == "abcd"
--   eliminaUnitarias 'X' "XXabcd"            == "XXabcd"
--   eliminaUnitarias 'X' "XXXabcd"           == "XXXabcd"
--   eliminaUnitarias 'X' "abcdX"             == "abcd"
--   eliminaUnitarias 'X' "abcdXX"            == "abcdXX"
--   eliminaUnitarias 'X' "abcdXXX"           == "abcdXXX"
--   eliminaUnitarias 'X' "abXcd"             == "abcd"
--   eliminaUnitarias 'X' "abXXcd"            == "abXXcd"
--   eliminaUnitarias 'X' "abXXXcd"           == "abXXXcd"
--   eliminaUnitarias 'X' "XabXcdX"           == "abcd"
--   eliminaUnitarias 'X' "XXabXXcdXX"        == "XXabXXcdXX"
--   eliminaUnitarias 'X' "XXXabXXXcdXXX"     == "XXXabXXXcdXXX"
--   eliminaUnitarias 'X' "XabXXcdXeXXXfXx"   == "abXXcdeXXXfx"
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

eliminaUnitarias :: Char -> String -> String
eliminaUnitarias c cs = if length cs == 1 then if [c] == cs then "" else cs
                           else filter (/= ' ') (map snd (A.assocs (v A.// [ f n | n <- [0..x], v A.! n == c])))
                      where v = A.array (0,x) [(i, cs !! i) | i <- [0..x]]
                            x = length cs - 1
                            f n | n == 0 = if v A.! 0 /= v A.! 1 then (0,' ') else (0, v A.! 0)
                                | n == x = if v A.! (x-1) /= v A.! x then (x,' ') else (x, v A.! x)
                                | otherwise = if (v A.! n /= v A.! (n-1)) && (v A.! n /= v A.! (n+1))  then (n,' ') else (n, v A.! n)
                           

-- ----------------------------------------------------------------------------
-- 
-- Ejercicio 6. La sucesión de Fibonacci es
--   0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,...
-- cuyos dos primeros términos son 0 y 1 y los restantes se obtienen sumando
-- los dos anteriores.
--
-- El árbol de computación de su 5º término es
--                  5
--                 / \
--                /   \
--               /     \
--              /       \
--             /         \
--            3           2  
--           / \         / \ 
--          /   \       1   1
--         2     1     / \   
--        / \   / \   1   0  
--       1   1 1   0
--      / \ 
--     1   0  
-- que, usando los árboles definidos por
--    data Arbol = H Int
--               | N Int Arbol Arbol
--      deriving (Eq, Show)
-- se puede representar por
--   N 5              
--     (N 3           
--        (N 2        
--           (N 1 (H 1) (H 0))
--           (H 1))   
--        (N 1 (H 1) (H 0)))  
--     (N 2           
--        (N 1 (H 1) (H 0))   
--        (H 1))     
--
-- Definir la función
--   arbolFib :: Int -> Arbol
-- tal que '(arbolFib n)' es el árbol de computación del 'n'-ésimo término de
-- la sucesión de Fibonacci. Por ejemplo,
--   arbolFib 5  ==>
--     N 5              
--       (N 3           
--          (N 2        
--             (N 1 (H 1) (H 0))
--             (H 1))   
--          (N 1 (H 1) (H 0)))  
--       (N 2           
--          (N 1 (H 1) (H 0))   
--          (H 1))
--   arbolFib 6  ==>
--     N 8
--       (N 5
--          (N 3
--             (N 2
--                (N 1 (H 1) (H 0))
--                (H 1))
--             (N 1 (H 1) (H 0)))
--          (N 2
--             (N 1 (H 1) (H 0))
--             (H 1)))
--       (N 3
--          (N 2
--             (N 1 (H 1) (H 0)) (H 1))
--          (N 1 (H 1) (H 0)))
--
-- ----------------------------------------------------------------------------

data Arbol2 = H2 Int
            | N2 Int Arbol2 Arbol2
            deriving (Eq, Show)


-- Álvaro Galisteo: 

arbolFib :: Int -> Arbol2
arbolFib 0 = H2 0
arbolFib 1 = H2 1 
arbolFib n = N2 (sumaNodos (arbolFib (n-1)) (arbolFib (n-2))) (arbolFib (n-1)) (arbolFib (n-2))

 
sumaNodos :: Arbol2 -> Arbol2 -> Int
sumaNodos (N2 a _ _) (N2 b _ _) = a+b
sumaNodos (N2 a _ _) (H2 b) = a+b
sumaNodos (H2 b) (N2 a _ _) = a+b
sumaNodos (H2 a) (H2 b) = a+b

-- ----------------------------------------------------------------------------
--
-- Ejercicio 7.1. Una matriz equis es una matriz en la que hay una
-- posición (i,j) tal que todos los elementos que están fuera de las diagonales
-- que pasan por dicha posición son nulos. Por ejemplo,
--
--   ( 0 2 0 2 )      ( 2 0 0 0 1 )      ( 3 0 0 0 5 )
--   ( 0 0 4 0 )      ( 0 0 0 3 0 )      ( 0 4 0 2 0 )
--   ( 0 3 0 7 )      ( 0 0 1 0 0 )      ( 0 0 1 0 0 )
--   ( 5 0 0 0 )      ( 0 7 0 6 0 )
--
-- Utilizaremos la librería Matrix para desarrollar este ejercicio.
--
-- Definir la función
--   esMatrizEquis :: M.Matrix Int -> Bool
-- tal que '(esMatrizEquis m)' comprueba si la matriz 'm' es una matriz equis.
-- Por ejemplo, dadas las matrices
--   m1 = M.matrix 3 3 (\ (i,j) -> (if (all odd [i,j]) then 1 else 0))
--   m2 = M.matrix 3 4 (\ (i,j) -> (i+j))
-- entonces
--   esMatrizEquis m1  ==  True
--   esMatrizEquis m2  ==  False
--
-- ----------------------------------------------------------------------------

m1, m2 :: M.Matrix Int
m1 = M.matrix 3 3 (\ (i,j) -> (if (all odd [i,j]) then 1 else 0))
m2 = M.matrix 3 4 (\ (i,j) -> (i+j))


-- Álvaro Galisteo: 

esMatrizEquis :: M.Matrix Int -> Bool
esMatrizEquis m = or [centroEquis (y,z) m | y <- [1..a], z <- [1..b]]
                where a = M.nrows m
                      b = M.ncols m 

centroEquis :: (Int, Int) -> M.Matrix Int -> Bool
centroEquis (i,j) m = all (==0) [m M.! (y,z) | y <- [1..a], z <- [1..b], y-z /= i-j, not (elem (y,z) (otraDiagonal (i,j) m))]
                    where a = M.nrows m
                          b = M.ncols m
                      
otraDiagonal :: (Int, Int) -> M.Matrix Int -> [(Int, Int)]
otraDiagonal (i,j) m = [(i+(1*k),j-(1*k)) | k <- [1..(max a b)], i+(1*k) <= a && j-(1*k) >= 1] ++ [(i-(1*k),j+(1*k)) | k <- [1..(max a b)], i-(1*k) >= 1 && j+(1*k) <= b]
                   where a = M.nrows m
                         b = M.ncols m 

-- ----------------------------------------------------------------------------
--
-- Ejercicio 7.2. Definir la función
--   matrizEquis :: Int -> Int -> Int -> Int -> M.Matrix Int
-- tal que '(matrizEquis p q f c)' es la matriz equis de dimensión '(p,q)' con
-- respecto a la posición '(f,c)', en la que el valor de cada elemento no nulo
-- es la distancia en línea recta a la posición '(f,c)', contando también esta
-- última. Por ejemplo,
--   matrizEquis 3 3 2 2  =>
--     ( 2 0 2 )
--     ( 0 1 0 )
--     ( 2 0 2 )
--   matrizEquis 4 5 2 3  =>
--     ( 0 2 0 2 0 )
--     ( 0 0 1 0 0 )
--     ( 0 2 0 2 0 )
--     ( 3 0 0 0 3 )
--   matrizEquis 5 3 2 3  =>
--     ( 0 2 0 )
--     ( 0 0 1 )
--     ( 0 2 0 )
--     ( 3 0 0 )
--     ( 0 0 0 )
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

matrizEquis :: Int -> Int -> Int -> Int -> M.Matrix Int
matrizEquis p q f c = M.matrix p q (putElem p q f c)

putElem :: Int -> Int -> Int -> Int -> (Int,Int) -> Int
putElem p q f c (i,j) | elem (i,j) (otraDiagonal (f,c) (M.zero p q)) = abs (i-f) + 1
                      | f-c == i-j = abs (i-f) +1 
                      | i == f && j == c = 1
                      | otherwise = 0
                      
-- ----------------------------------------------------------------------------
--
-- Ejercicio 8. El polinomio cromático de un grafo calcula el número
-- de maneras en las cuales puede ser coloreado el grafo usando un número de
-- colores dado, de forma que dos vértices adyacentes no tengan el mismo color.   
-- 
-- En el caso del grafo completo de n vértices, su polinomio cromático es
-- P(n)(x) = x(x-1)(x-2) ... (x-(n-1)). Por ejemplo, 
--   P(3)(x) = x(x-1)(x-2)      = x^3 - 3*x^2 + 2*x
--   P(4)(x) = x(x-1)(x-2)(x-3) = x^4 - 6*x^3 + 11*x^2 - 6*x
-- Lo que significa que P(4)(x) es el número de formas de colorear el grafo
-- completo de 4 vértices con x colores. Por tanto,
--   P(4)(2) =  0 (no se puede colorear con 2 colores)
--   P(4)(4) = 24 (hay 24 formas de colorearlo con 4 colores)
--
-- Ejercicio 3.1. Definir la función 
--   polGC :: Int -> Polinomio Int
-- tal que '(polGC n)' es el polinomio cromático del grafo completo de 'n'
-- vértices. Por ejemplo,
--   polGC 4  ==  x^4 + -6*x^3 + 11*x^2 + -6*x
--   polGC 5  ==  x^5 + -10*x^4 + 35*x^3 + -50*x^2 + 24*x
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

polGC :: Int -> Polinomio Int
polGC 1 = consPol 1 1 polCero
polGC n = multPol (n-1) (polGC (n-1))

multPol :: Int -> Polinomio Int -> Polinomio Int
multPol n p1 = dispersaToPol ((map (\ (a,b) -> (a,b*(-n))) (dispersa p1)) ++ (map (\ (a,b) -> (a+1,b)) (dispersa p1)))

dispersa :: Polinomio Int -> [(Int,Int)]
dispersa p1 | esPolCero p1 = []
            | otherwise = (grado p1, coefLider p1):(dispersa (restoPol p1))
                              
dispersaToPol :: [(Int,Int)] -> Polinomio Int
dispersaToPol [] = polCero
dispersaToPol (x:xs) = consPol (fst x) (snd x) (dispersaToPol xs)

-- ----------------------------------------------------------------------------
--
-- Ejercicio 9.1. En la aritmética lunar la suma se hace como en la
-- terrícola salvo que sus tablas de sumar son distintas. La suma lunar de dos
-- dígitos es su máximo (por ejemplo, 1 + 3 = 3 y 7 + 4 = 7). Por tanto,  
--      3 5 7    
--    +   6 4    
--    -------    
--      3 6 7    
--
-- Ejercicio 1.1. Definir la función
--   suma :: Integer -> Integer -> Integer
-- tal que '(suma x y)' es la suma lunar de los números 'x' e 'y'. Por ejemplo, 
--   suma 357 64  ==  367
--   suma 64 357  ==  367
--   suma 1 3     ==  3
--   suma 7 4     ==  7
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

suma :: Integer -> Integer -> Integer
suma x y = f (replicate (maxLen - (length (show x))) '0' ++ (show x)) (replicate (maxLen - (length (show y))) '0' ++ (show y))
         where maxLen = max (length (show x)) (length (show y))
               f xs ys = read (reverse (map (\ (a,b) -> max a b) (zip (reverse xs) (reverse ys)))) :: Integer

-- ----------------------------------------------------------------------------
--
-- Ejercicio 9.2. Comprobar con QuickCheck que la suma lunar es conmutativa.
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

prop_conmutativa :: Integer -> Integer -> Property
prop_conmutativa n m = n >= 0 && m >= 0 ==> n + m == m + n

-- *Main> quickCheck prop_conmutativa
-- +++ OK, passed 100 tests; 257 discarded.

-- ----------------------------------------------------------------------------
--
-- Ejercicio 10. 
--
-- El árbol binario de los divisores de 24 es
--    90
--    /\
--   2  45
--      /\
--     3  15
--        /\
--       3  5
--
-- Se puede representar por
--   N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))
-- usando el tipo de dato definido por
--
-- data Arbol = H Int
--            | N Int Arbol Arbol
--            deriving (Eq, Show)
-- Análogamente se obtiene el árbol binario de cualquier número x: se comienza
-- en x y en cada paso se tiene dos hijos (su menor divisor y su cociente)
-- hasta obtener números primos en las hojas.
--
-- Definir las funciones
--   arbolDivisores2     :: Int -> Arbol
--   hojasArbolDivisores :: Int -> [Int]
-- tales que
-- (arbolDivisores2 x) es el árbol binario de los divisores de x. Por ejemplo,
-- arbolDivisores2 90  == N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))
-- arbolDivisores2 24  == N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3)))
-- arbolDivisores2 300 == N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5))))
--
-- (hojasArbolDivisores x) es la lista de las hojas del árbol binario de los
-- divisores de x. Por ejemplo
-- hojasArbolDivisores 90   ==  [2,3,3,5]
-- hojasArbolDivisores 24   ==  [2,2,2,3]
-- hojasArbolDivisores 300  ==  [2,2,3,5,5]
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

arbolDivisores2 :: Int -> Arbol2
arbolDivisores2 x | (divisores' x) == [1] = H2 x
                  | otherwise = N2 x (arbolDivisores2 y) (arbolDivisores2 (div x y)) 
                 where y = head (tail (divisores' x)) 

divisores' :: Int -> [Int]
divisores' n = [x | x <- [1..(div n 2)], mod n x == 0]


hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores x = listaDivAux (arbolDivisores2 x)

listaDivAux :: Arbol2 -> [Int]
listaDivAux (N2 e l r) = listaDivAux l ++ listaDivAux r
listaDivAux (H2 e) = [e]

-- ----------------------------------------------------------------------------
-- 
-- Ejercicio 11.1. Sheldon Cooper tiene que pagar 10$ por el
-- aparcamiento, pero sólo tiene monedas de 1$, de 2$ y de 5$. Entonces dice:
-- "podría hacer esto de 128 formas distintas y necesitaría un total de 831
-- monedas para hacerlo de todas las formas posibles". Está contando las formas
-- de disponer las monedas en la máquina para pagar los 10$ y el número de
-- monedas que necesita para hacerlas todas. Por ejemplo, si tuviese que pagar
-- 4$ entonces habría 5 formas de pagar: [2,2], [2,1,1], [1,2,1], [1,1,2] y
-- [1,1,1,1] y el total de monedas que se necesitan para hacerlas todas es
-- 2 + 3 + 3 + 3 + 4 = 15.
--
-- Definir la función (mediante programación dinámica)
--   distribuciones :: Integer -> Integer
-- tal que '(distribuciones n)' es el número de formas distintas de distribuir
-- la cantidad 'n' como una secuencia de monedas de 1$, 2$ y 5$, con un valor
-- total igual a 'n'. Por ejemplo,
--   distribuciones 5    ==  9
--   distribuciones 10   ==  128
--   distribuciones 100  ==  91197869007632925819218
--   length (show (distribuciones 1000))  ==  232
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

distribuciones :: Integer -> Integer
distribuciones n = v A.! n
                 where v = A.array (1,n) [(i,f i) | i <- [1..n]]
                       f i | i == 1 = 1
                           | i == 2 = 2
                           | i == 3 = 3
                           | i == 4 = 5
                           | i == 5 = 9 
                           | otherwise = v A.! (i-1) + v A.! (i-2) + v A.! (i-5)

-- ----------------------------------------------------------------------------
--
-- Ejercicio 11.2 Definir la función
--   cuentaMonedas :: Integer -> Integer
-- tal que '(cuentaMonedas n)' es el número de monedas que le hacen falta a
-- Sheldon Cooper para construir todas las distribuciones de la cantidad 'n'
-- como una secuencia de monedas de 1$, 2$ y 5$, con un valor total igual a
-- 'n'. Por ejemplo,
--   cuentaMonedas 5    ==  31
--   cuentaMonedas 10   ==  841
--   cuentaMonedas 100  ==  5660554507743281845750870
--   length (show (cuentaMonedas 1000))  ==  235
--
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

cuentaMonedas :: Integer -> Integer
cuentaMonedas n = v A.! n
                 where v = A.array (1,n) [(i,f i) | i <- [1..n]]
                       f i | i == 1 = 1
                           | i == 2 = 3 
                           | i == 3 = 7 
                           | i == 4 = 15
                           | i == 5 = 31
                           | otherwise = v A.! (i-1) + v A.! (i-2) + v A.! (i-5) + distribuciones i


-- ----------------------------------------------------------------------------
-- 
-- Ejercicio 12. Un clique de un grafo no dirigido G es un conjunto de vértices
-- V tal que el subgrafo de G inducido por V es un grafo completo. Por ejemplo,
-- en el grafo,
--
--    6
--     \
--      4 ---- 5
--      |      | \
--      |      |  1
--      |      | /
--      3 ---- 2
--
-- el conjunto de vértices {1,2,5} es un clique y el conjunto {2,3,4,5} no lo
-- es.
--
-- En Haskell se puede representar el grafo anterior por
--    g1 :: Grafo Int Int
--    g1 = creaGrafo ND (1,6) [(1,2),(1,5),(2,3),(3,4),(5,2),(4,5),(4,6)]
--
-- Definir la función
--    esClique :: Grafo Int Int -> [Int] -> Bool
-- tal que '(esClique g xs)' se verifica si el conjunto de vértices 'xs' es un
-- clique del grafo 'g'. Por ejemplo,
--    esClique g1 [1,2,5]    ==  True
--    esClique g1 [2,3,4,5]  ==  False
--
-- ----------------------------------------------------------------------------

g1 :: Grafo Int Int
g1 = creaGrafo ND (1,6) [(1,2),(1,5),(2,3),(3,4),(5,2),(4,5),(4,6)]


-- Álvaro Galisteo: 

esClique :: Grafo Int Int -> [Int] -> Bool
esClique g xs = (intersect (filter (\ (a,b) -> elem a xs && elem b xs) (aristas g)) [(i,j) | i <- xs, j <- xs, i /= j]) == [(i,j) | i <- xs, j <- xs, i /= j]