Examen 21/06/21

-- Informática (1º del Grado en Matemáticas)
-- 4º examen de evaluación continua (21 de junio de 2021)       Grupos A, B y C
-- ============================================================================

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

-- ============================================================================

import qualified Data.Vector as V
import qualified Data.Array as A
import Data.Numbers.Primes
-- Selecciona de estas dos librerías la que hayas utilizado en clase
import GrafoConMatrizDeAdyacencia
-- import I1M.Grafo

import Data.List

-- ============================================================================
-- Ejercicio 1. (2.5 ptos) El complemento de un número positivo N se calcula
-- por el siguiente rocedimiento:
--   Si N es mayor que 9, se toma cada dígito por su valor posicional y se
--   resta del mayor los otros dígitos. Por ejemplo, el complemento de 1448 es
--   1000 - 400 - 40 - 8 = 552. Cuando N es menor que 10, su complemento es N.
--
-- Definir las funciones
--   cadena    :: Integer -> [Integer]
--   conCadena :: Int -> [Integer]
-- tales que
-- + '(cadena n)' es la cadena de primos a partir del número 'n' tal que cada
--   uno es el complemento del anterior. Por ejemplo,
--      cadena 8         == []
--      cadena 7         == [7]
--      cadena 13        == [13,7]
--      cadena 643       == [643,557,443]
--      cadena 18127     == [18127,1873,127,73,67,53,47]
--      cadena 18181213  == [18181213,1818787,181213,18787,1213,787,613,587]
-- + '(conCadena n)' es la lista de números cuyas cadenas tienen 'n'
--   elementos. Por ejemplo,
--      take 6 (conCadena 3)                == [23,31,61,67,103,307]
--      [head (conCadena n) | n <- [4..8]]  == [37,43,157,18127,181873]
-- ----------------------------------------------------------------------------

complemento :: Integer -> Integer
complemento n =
  let c = 10^(length (show n)-1)
  in (div n c)*c - (mod n c)

cadena :: Integer -> [Integer]
cadena n
  | n < 10 && isPrime n = [n]
  | isPrime n = n : cadena (complemento n)
  | otherwise = []

conCadena :: Int -> [Integer]
conCadena n =
  filter ((==n).length.cadena) primes

-- ============================================================================
-- Ejercicio 2. (2.5 puntos) Un número es innombrable si es divisible por 7 o
-- alguno de sus dígitos es un 7. Un juego infantil consiste en contar
-- saltándose los números innombrables:
--   1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...
--
-- La sucesión de Cantor se obtiene llenando los huecos de la sucesión
-- anterior con la propia sucesión:
--   1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
--   24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
--   44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
--   (2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
--   (25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
--   (30) 99 100
--
-- Definir la lista
--   sucCantor :: [Integer]
-- cuyo valor es la sucesión de Cantor. Por ejemplo,
--   take 100 sucCantor  ==
--     [1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2 ,15,16, 3 ,18,19,20, 4 ,22,23,
--      24,25,26, 5,6 ,29,30,31,32,33,34, 1 ,36, 8 ,38,39,40,41, 9 ,43,44,
--      45,46, 10 ,48, 11 ,50,51,52,53,54,55, 12,13 ,58,59,60,61,62, 2 ,64,
--      65,66, 15 ,68,69, 16,3,18,19,20,4,22,23,24,25, 80,81,82,83, 26 ,85,
--      86, 5 ,88,89,90, 6 ,92,93,94,95,96, 29,30 ,99,100]
--    sucCantor !! (5+10^6)  ==  544480
--    sucCantor !! (6+10^6)  ==  266086
-- ============================================================================

sucCantor :: [Integer]
sucCantor =
  mezclaCantor [1..] sucCantor

mezclaCantor :: [Integer] -> [Integer] -> [Integer]
mezclaCantor (x:xs) ys =
  if x`mod`7 == 0 || elem '7' (show x)
  then (head ys) : mezclaCantor xs (tail ys)
  else x : mezclaCantor xs ys

-- ============================================================================
-- Ejercicio 3. (2.5 ptos) Consideremos grafos en los que cada arista está
-- etiquetada con un valor que representa un color (en lugar de un peso). Un
-- camino alternado en este tipo de grafos es un camino que no pasa por dos
-- aristas consecutivas del mismo color.
--
-- Definir la función
--   caminoAlternado :: (A.Ix v, Num p, Eq p) => Grafo v p -> [v] -> Bool
-- tal que '(caminoAlternado g vs)' comprueba que la secuencia de nodos 'vs'
-- del grafo 'g', forma un camino alternado en el grafo. Por ejemplo,
--   caminoAlternado grafo [1,2,4,3,5]  ==  True
--   caminoAlternado grafo [3,1,2,4,6]  ==  False
-- donde 'grafo' es el grafo que se define a continuación (selecciona de las
-- siguientes definiciones de grafos la que hayas utilizado en clase):

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

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

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

caminoAlternado :: (A.Ix v, Num p, Eq p) => Grafo v p -> [v] -> Bool
caminoAlternado g vs =
  let as = zip vs (tail vs)
  in (all (aristaEn g) as) && -- vs es un camino en g
     (and [peso g a1 /= peso g a2 | (a1,a2) <- zip as (tail as)])

-- ============================================================================
-- Ejercicio 4. (2.5 ptos) En una rejilla de 2xN cuadros de longitud se pueden
-- colocar de distintas formas piezas de 2 cuadros de longitud, en horizontal y
-- vertical, de forma que no quede espacio libre en la rejilla. Por ejemplo,
-- una rejilla de 2x12 cuadros de longitud se puede rellenar de la siguiente
-- forma: 
--
--    ╔═══╦═╦═╦═╦═══╦═══╦═╦═══╗
--    ╠═══╣ ║ ║ ╠═══╬═══╣ ╠═══╣
--    ╚═══╩═╩═╩═╩═══╩═══╩═╩═══╝
--
-- Definir la función
--   rejillas2N :: Int -> Integer -> Integer
-- tal que '(rejillas2N n m)' es el número de formas distintas de rellenar una
-- rejilla de '2xn' cuadros de longitud con piezas de 2 cuadros de longitud de
-- 'm' colores distintos, calculado mediante la técnica de programación
-- dinámica. Tened en cuenta que no hay ninguna restricción acerca de cómo
-- colocar las piezas de distintos colores. Por ejemplo, 
--   rejillas2N 2 2   ==  8
--   rejillas2N 2 3   ==  18
--   rejillas2N 3 2   ==  24
--   rejillas2N 3 3   ==  81
--   rejillas2N 20 5  ==  1043891906738281250
--   length (show (rejillas2N 100 7))   ==  106
--   length (show (rejillas2N 1000 9))  ==  1164
-- ----------------------------------------------------------------------------

-- rejillas2N n m =
--   m * (rejillas2N (n-1) m) + m^2 * (rejillas2N (n-2) m)

-- Versión recursiva

rejillas2NR :: Int -> Integer -> Integer
rejillas2NR 0 m = 1
rejillas2NR 1 m = m
rejillas2NR n m =
  m * (rejillas2NR (n-1) m) + m^2 * (rejillas2NR (n-2) m)

-- Versión usando programación dinámica
    
rejillas2N :: Int -> Integer -> Integer
rejillas2N n m =
  let v = V.generate (n+1) (\ i -> generaRejillas2N v m i)
  in v V.! n

generaRejillas2N :: V.Vector Integer -> Integer -> Int -> Integer
generaRejillas2N v m 0 = 1
generaRejillas2N v m 1 = m
generaRejillas2N v m i =
  m * (v V.! (i-1)) + m^2 * (v V.! (i-2))

-- ============================================================================