Examen 11/12/20

-- ==================================================================
-- Informática (1º del Grado en Matemáticas), Grupo 2
-- 1º examen de evaluación continua 1 de diciembre de 2020)
-- ------------------------------------------------------------------
-- Nombre: 
--
-- Apellidos: 
-- 
-- Usuario Virtual de la Universidad(UVUS):
-- ==================================================================
-- Nota 1: Todos los ejercicios valen igual.

-- Nota 2: Recordad que en cualquier momento podéis consultar la funciones
--         predefinidas en Haskell en la siguiente página si pensáis que os
--         hacen falta.
--         http://www.cs.us.es/~mjoseh/cursos/i1m-20/doc/Funciones_basicas.html

import Data.List

-- ---------------------------------------------------------------------
-- Ejercicio 1 Define la función
--   alza :: Int -> [Int] -> Bool
-- tal que (alza n xs) comprueba si los últimos n elementos de la sucesión
-- xs están en orden creciente; es decir, cada elemento es mayor estricto
-- que el anterior. Por ejemplo,
-- > alza 3 [1..10]
-- True
-- > alza 3 [12,3,4,2,1]
-- False
-- > alza 4 [2,6,13,45,743,3445,3442,3443,3444]
-- False
-- > alza 3 [2,6,13,45,743,3445,3442,3443,3444]
-- True
-- ---------------------------------------------------------------------

alza :: Int -> [Int] -> Bool
alza n xs = and [ x < y | (x,y) <- zip xs' (tail xs')]
    where xs' = drop (length xs - n) xs

-- ---------------------------------------------------------------------
-- Ejercicio 2. (Problema 343 del proyecto Euler)
-- Para cualquier entero positivo k, se puede calcular la siguiente secuencia 
-- finita cuyos términos ai se calculan con la fracción reducida xi/yi, siendo:
-- a1 = 1/k (donde x1 = 1 e y1 = k) 
-- a2 = fraccionReducida (x1+1)/(y1-1) = fraccionReducida 2/(k-1) 
-- ai = fraccionReducida (x{i-1}+1)/(y{i-1}-1), para los términos con i>1.
-- Cuando ai es un entero n, la secuencia termina (es decir, cuando yi=1)
-- Por ejemplo, 
--  para k = 2, la sucesión es: 1/2 → 2/1 
--  para k = 4, la sucesión es: 1/4 → 2/3 → 3/2 → 4/1
--  para k = 3, la sucesión es: 1/3 → 2/2 = 1/1  (2/2 se reduce a 1/1, el cual es un entero)
--  para k = 20, la sucesión es: 1/20 → 2/19 → (3/18 que se reduce a 1/6) → 2/5 → 3/4 → 4/3 → 5/2 → 6/1 
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Define la función 
--     suc :: Int -> [(Int,Int)] 
-- tal que (suc k) devuelva la sucesión finita para k, representando las fracciones como 
-- pares de números enteros (numerador,denominador).
-- Por ejemplo:
-- > suc 2 
-- [(1,2),(2,1)]
-- > suc 4
-- [(1,4),(2,3),(3,2),(4,1)]
-- > suc 20
-- [(1,20),(2,19),(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)]
-- ---------------------------------------------------------------------

suc :: Int -> [(Int,Int)]
suc k = f' 1 k 

f' :: Int -> Int -> [(Int,Int)]
f' x y 
    | b == 1 = [(a,b)]
    | otherwise = (a,b):f' (a+1) (b-1)
    where a = div x (gcd x y)
          b = div y (gcd x y)

-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Se define la función f (k) = n, siendo n el entero final
-- en la sucesión para k. Por ejemplo:
-- f (2) = 2
-- f (4) = 4
-- f (3) = 1
-- f (20) = 6
-- Define la función
--   f :: Int -> Int
-- tal que (f k) devuelva el entero n. Usa la función para calcular la
-- suma de f(k^3) para 1 <= k <= 100, cuyo resultado es 118937.
-- ---------------------------------------------------------------------

f :: Int -> Int
f k = fst (last (suc k))

suma :: Int
suma = sum [ f (k^3) | k <- [1..100]]

-- ---------------------------------------------------------------------
-- Ejercicio 3. Decimos que un número contiene un primo si eliminando cifras,
-- de derecha a izquierda, encontramos un número primo. Por ejemplo,
-- 59912 no es primo, 5991 no es primo, 599 es primo.
-- Definir la función
--    contienePrimo :: Int -> Bool
-- tal que (contienePrimo x) se verifica si x contiene un primo.
-- Por ejemplo,
--    contienePrimo 5992  ==  True
--    contienePrimo 11    ==  True
--    contienePrimo 245   ==  True
--    contienePrimo 645   ==  False
-- ---------------------------------------------------------------------

contienePrimo :: Int -> Bool
contienePrimo x
  | x < 10    = primo x
  | otherwise = primo x || contienePrimo (x `div` 10)

-- (primo x) se verifica si x es primo.
primo :: Int -> Bool
primo x = factores x == [1,x]

-- (factores x) es la lista de los factores de x.
factores :: Int -> [Int]
factores x = [y | y <- [1..x], x `rem` y == 0]

-- ---------------------------------------------------------------------
-- Ejercicio 4. A continuación se pedirá definir la función 
--    separa :: (b -> a) -> (a -> Bool) -> [b] -> ([b], [b])
-- tal que (separa f p xs) devuelve un par donde en el primero elemento
-- se encuentran los elementos de xs que cumplen la propiedad p tras 
-- aplicar la función f, y en el segundo elemento el resto de elementos
-- de la lista xs (los que no cumplen p tras aplicarles f). 
-- Por ejemplo,
--  > separa length (>3) ["hola","que","tal"]
--  (["hola"],["que","tal"])     
--  > separa head (=='t') ["trastear","tambor","animo","claro"]
--  (["trastear","tambor"],["animo","claro"])
--  > separa (*2) even [1..10]
--  ([1,2,3,4,5,6,7,8,9,10],[])
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 4.1 Define la función por comprensión.
-- ---------------------------------------------------------------------

separaC :: (b -> a) -> (a -> Bool) -> [b] -> ([b], [b])
separaC f p xs = ([x | x <- xs, p (f x)],[x | x <- xs, not (p (f x))])

-- ---------------------------------------------------------------------
-- Ejercicio 4.2 Define la función por orden superior (sin recurrir a
--  listas por comprensión ni recursión)
-- Nota: Puede resultarte útil hacer uso de la función predefinida partition.
-- Ejemplo de su utilidad:
--  > partition even [3,2,8,9,1,4] == ([2,8,4],[3,9,1])
-- ---------------------------------------------------------------------

-- 1ª Solución
separaO :: (b -> a) -> (a -> Bool) -> [b] -> ([b], [b])
separaO f p xs = (map snd ys, map snd zs) 
    where valores = zip (map f xs) xs 
          p' (x,_) = p x
          (ys,zs) = partition p' valores

-- 2ª Solución
separaO' :: (b -> a) -> (a -> Bool) -> [b] -> ([b], [b])
separaO' f p xs = (ys, zs) 
    where ys = filter (p.f) xs
          zs = filter (not.p.f) xs