Examen 07/09/2021

-- Informática (1º del Grado en Matemáticas)
-- 2ª convocatoria

-- =====================================================================
-- Nombre: 
-- Apellidos: 
-- UVUS:
-- =====================================================================

-- ---------------------------------------------------------------------
-- Importación de librerías                                           --
-- ---------------------------------------------------------------------

import Data.Matrix
import qualified Data.Set as S
import qualified Data.Vector as V
import Data.List
import Data.Numbers.Primes
import I1M.Cola

-- ---------------------------------------------------------------------
-- Ejercicio 1. Una permutación de n se representa como una lista de los
-- elementos 1..n. Por ejemplo, la lista [3,1,2,4] representa la
-- permutación tal que corresponde con la transformación:
--      1 -> 3
--      2 -> 1
--      3 -> 2
--      4 -> 4

-- Definir la función
--   compPermutaciones :: [Int] -> [Int]
-- tal que (compPermutaciones p q) es composición de las permutaciones p
-- y q. Por ejemplo, si p = [1,3,4,2] y q = [3,1,2,4], la composición
-- es:
--     1 -> 1 -> 3
--     2 -> 3 -> 2
--     3 -> 4 -> 4
--     4 -> 2 -> 1

--   compPermutaciones [1,3,4,2] [3,1,2,4] == [3,2,4,1]

compPermutaciones :: [Int] -> [Int] -> [Int]
compPermutaciones p q = 
    map snd (comp (zip [1..n] p) (zip [1..n] q))
        where n = length p
              comp r s = [(x,z) | (x,y) <- r, (y',z) <-s, y == y']


-- ---------------------------------------------------------------------
-- Ejercicio 2. Se tienen n cartas numeradas en un único montón en orden
-- creciente desde arriba hacia abajo; es decir, la carta de más arriba
-- es la número 1, luego sigue la número 2, ...
-- 
-- Se hace lo siguiente: 
-- + se coloca la carta número 1 debajo de todas, 
-- + se quita de arriba la carta número 2, 
-- + se coloca la carta número 3 debajo de todas, 
-- + se quita de arriba la carta número 4, 
-- + ...  
-- 
-- El proceso continúa siempre de la misma manera: se coloca la carta de
-- más arriba debajo de todas y se quita la que ha quedado arriba, hasta
-- que quede una única carta.
-- 
-- Definir la función 
--    cartaFinal :: Int -> Int
-- tal que (cartaFinal n) es la carta final que queda en el montón. Por
-- ejemplo, 
--    cartaFinal 4   == 1
--    cartaFinal 7   == 7
--    cartaFinal 10  == 5
--    cartaFinal 20  == 9
--    cartaFinal 100 == 73
-- ---------------------------------------------------------------------

-- Usando listas:

cartaFinal :: Int -> Int
cartaFinal n = head (until pred paso [1..n])
  where paso (x:xs) = tail (xs++[x])
        pred (x:xs) = null xs


-- Usando colas:

cartaFinalC :: Int -> Int
cartaFinalC n = primero (until pred paso cInicial)
  where cInicial = foldr inserta vacia [n,n-1..1]
        pred c = not (esVacia c) && esVacia (resto c)
        paso c = resto (inserta (primero c) (resto c))


-- ---------------------------------------------------------------------
-- Ejercicio 3. Dada una matriz A, de dimensión n×n , sea X_i el
-- conjunto de elementos de la fila i, e Y_j el conjunto de elementos de
-- la columna j, 1 ≤ i, j ≤ n. Decimos que A es dorada si
-- X_1,...,X_n,Y_1,...,Y_n son conjuntos distintos.

-- Definir la función
--     esMatrizDorada :: Ord a => Matrix a -> Bool
-- tal que (esMatrizDorada A) verifique si A es dorada. Por ejemplo,
--     esMatrizDorada (fromLists [[1,2,1],[1,1,1],[2,2,2]]) == False
--     esMatrizDorada (fromLists [[1,2,1],[1,1,1],[3,3,4]]) == True
-- ---------------------------------------------------------------------

esMatrizDorada :: Ord a => Matrix a -> Bool
esMatrizDorada p =  
  conjDistintosLista (filas p ++ columnas p)
  where n = nrows p
        filas p = [S.fromList (V.toList (getRow i p)) | i <-[1..n]]
        columnas p = [S.fromList (V.toList (getCol i p)) | i <-[1..n]]

conjDistintosLista :: Ord a => [S.Set a] -> Bool
conjDistintosLista []       = True
conjDistintosLista (xs:xss) = 
  all (not . ((==) xs)) xss && conjDistintosLista xss

-- ---------------------------------------------------------------------
-- Ejercicio 4. Consideremos el problema de construir los árboles
-- etiquetados en las hojas, a partir de una lista xs, de forma que el
-- borde del árbol consista en los elementos de esta lista. Por ejemplo,
-- si xs = [1,2,3], los árboles que se obtienen son los siguientes:

--          .              .
--         / \            / \
--        1   .          .   3
--           / \        / \
--          2   3      1   2

-- Definir la función
--     arboles:: [Int] -> [Arbol]
-- tal que (arboles xs) es la lista de los árboles que se pueden
-- construir de forma que los elementos que constituyen su borde es la
-- lista xs. Por ejemplo,
--      arboles [1..3] = [Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3)),
--                        Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3)]
-- ----------------------------------------------------------------------------

data Arbol = Hoja Int | Nodo Arbol Arbol 
             deriving Show


-- Definimos la función arboles, de forma recursiva

arboles:: [Int] -> [Arbol]
arboles [x] = [Hoja x]
arboles (x:xs) = concatMap (prefijos x) (arboles xs)

-- (prefijos x a) es la lista de todas las formas en la que x puede ser
-- insertada como la hoja más a la izquierda en el árbol a. Por ejemplo,
-- si el árbol es 
--      .
--     / \
--    2   3
--
-- hay dos formas de insertar 1 de forma que sea la hoja más a la
-- izquierda:

--          .              .
--         / \            / \
--        1   .          .   3
--           / \        / \
--          2   3      1   2

prefijos:: Int -> Arbol -> [Arbol]
prefijos x a@(Hoja y) = [Nodo (Hoja x) a]
prefijos x a@(Nodo i d) = 
    (Nodo (Hoja x) a):[Nodo i' d | i' <- prefijos x i]

-- prefijos 1 (Nodo (Hoja 2) (Hoja 3))
-- [Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3)),
--  Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3)]

-- arboles [1..3]
-- [Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3)),
--  Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3)]


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