Relación 4 extra 2

-- Definiciones por recursión y por comprensión 
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------

-- En esta relación se presentan ejercicios con dos definiciones (una
-- por recursión y otra por comprensión) y la comprobación de la
-- equivalencia de las dos definiciones con QuickCheck. Los ejercicios
-- corresponden a los temas 5 y 6 
-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import Test.QuickCheck
import Data.List

-- ---------------------------------------------------------------------
-- Ejercicio 1. Se quiere formar una escalera con bloques cuadrados,
-- de forma que tenga un número determinado de escalones. Por ejemplo,
-- una escalera con tres escalones tendría la siguiente forma:
--        XX
--      XXXX
--    XXXXXX
-- Definir, por recursión, la función 
--    numeroBloquesR :: Integer -> Integer    
-- tal que (numeroBloquesR n) es el número de bloques necesarios para
-- construir una escalera con n escalones. Por ejemplo,
--    numeroBloquesR 1   == 2
--    numeroBloquesR 3   == 12
--    numeroBloquesR 10  == 110
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
numeroBloquesR :: Integer -> Integer    
numeroBloquesR 1 = 2
numeroBloquesR n = numeroBloquesR (n-1) + 2 

-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir, por comprensión, la función 
--    numeroBloquesC :: Integer -> Integer    
-- tal que (numeroBloquesC n) es el número de bloques necesarios para
-- construir una escalera con n escalones. Por ejemplo,
--    numeroBloquesC 1   == 2
--    numeroBloquesC 3   == 12
--    numeroBloquesC 10  == 110
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
numeroBloquesC :: Integer -> Integer    
numeroBloquesC n = sum [2*x | x <- [1..n]]

-- ---------------------------------------------------------------------
-- Ejercicio 1.3. Comprobar con QuickCheck que (numeroBloquesC n) es
-- igual a n+n^2.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_numeroBloquesR :: Integer -> Property
prop_numeroBloquesR n = n>0 ==> numeroBloquesC n == n+n^2

-- La comprobación es

-- *Main> quickCheck prop_numeroBloquesR
-- +++ OK, passed 100 tests; 107 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Definir, por recursión, la función
--    digitosR :: Integer -> [Integer]
-- tal que (digitosR n) es la lista de los dígitos del número n. Por
-- ejemplo, 
--    digitosR 320274  ==  [3,2,0,2,7,4]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
digitosR :: Integer -> [Integer]
digitosR n = if n == mod n 10 then [n] else digitosR (div n 10) ++ [(mod n 10)]

-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Definir, por comprensión, la función
--    digitosC :: Integer -> [Integer]
-- tal que (digitosC n) es la lista de los dígitos del número n. Por
-- ejemplo, 
--    digitosC 320274  ==  [3,2,0,2,7,4]
-- Indicación: Usar las funciones show y read.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
digitosC :: Integer -> [Integer]
digitosC n = [read [x] :: Integer | x <- (show n) ]

-- ---------------------------------------------------------------------
-- Ejercicio 2.3. Comprobar con QuickCheck que las funciones digitosR y
-- digitosC son equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es

prop_digitos :: Integer -> Property 
prop_digitos n = n>=0 ==> digitosR n == digitosC n
  
-- La comprobación es
-- *Main> quickCheck prop_digitos
-- +++ OK, passed 100 tests; 81 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Definir, por recursión, la función 
--    sumaDigitosR :: Integer -> Integer
-- tal que (sumaDigitosR n) es la suma de los dígitos de n. Por ejemplo,
--    sumaDigitosR 3     ==  3
--    sumaDigitosR 2454  == 15
--    sumaDigitosR 20045 == 11
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaDigitosR :: Integer -> Integer
sumaDigitosR n = if n == mod n 10 then n else sumaDigitosR (div n 10) + (mod n 10)

-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Definir, sin usar recursión, la función 
--    sumaDigitosNR :: Integer -> Integer
-- tal que (sumaDigitosNR n) es la suma de los dígitos de n. Por ejemplo,
--    sumaDigitosNR 3     ==  3
--    sumaDigitosNR 2454  == 15
--    sumaDigitosNR 20045 == 11
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum [read [x] :: Integer | x <- (show n) ]

-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Comprobar con QuickCheck que las funciones sumaDigitosR
-- y sumaDigitosNR son equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_sumaDigitos :: Integer -> Property 
prop_sumaDigitos n = n>=0  ==> sumaDigitosR n == sumaDigitosNR n 

-- La comprobación es
-- *Main> quickCheck prop_sumaDigitos 
-- +++ OK, passed 100 tests; 90 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función 
--    esDigito :: Integer -> Integer -> Bool
-- tal que (esDigito x n) se verifica si x es un dígito de n. Por
-- ejemplo, 
--    esDigito 4 1041  ==  True
--    esDigito 3 1041  ==  False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
esDigito :: Integer -> Integer -> Bool
esDigito x n = elem x [read [x] :: Integer | x <- (show n) ]

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función
--    numeroDeDigitos :: Integer -> Integer
-- tal que (numeroDeDigitos x) es el número de dígitos de x. Por ejemplo,
--    numeroDeDigitos 34047  ==  5
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
numeroDeDigitos :: Integer -> Int
numeroDeDigitos x = if x == mod x 10 then 1 else numeroDeDigitos (div x 10) + 1

-- ---------------------------------------------------------------------
-- Ejercicio 6.1 Definir, por recursión, la función 
--    listaNumeroR :: [Integer] -> Integer
-- tal que (listaNumeroR xs) es el número formado por los dígitos xs. Por
-- ejemplo, 
--    listaNumeroR [5]        == 5
--    listaNumeroR [1,3,4,7]  == 1347
--    listaNumeroR [0,0,1]    == 1
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
listaNumeroR :: [Integer] -> Integer
listaNumeroR [] = 0 
listaNumeroR (x:xs) = x*10^(length xs) + listaNumeroR xs

-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Definir, por comprensión, la función 
--    listaNumeroC :: [Integer] -> Integer
-- tal que (listaNumeroC xs) es el número formado por los dígitos xs. Por
-- ejemplo, 
--    listaNumeroC [5]        == 5
--    listaNumeroC [1,3,4,7]  == 1347
--    listaNumeroC [0,0,1]    == 1
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = sum [x*10^y | (x,y) <- zip xs (reverse [0..(length xs - 1)])]

-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Definir, por recursión, la función 
--    pegaNumerosR :: Integer -> Integer -> Integer
-- tal que (pegaNumerosR x y) es el número resultante de "pegar" los
-- números x e y. Por ejemplo, 
--    pegaNumerosR 12 987   ==  12987
--    pegaNumerosR 1204 7   ==  12047
--    pegaNumerosR 100 100  ==  100100
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
pegaNumerosR :: Integer -> Integer -> Integer
pegaNumerosR x y = listaNumeroR (digitosR x ++ digitosR y)

-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Definir, sin usar recursión, la función 
--    pegaNumerosNR :: Integer -> Integer -> Integer
-- tal que (pegaNumerosNR x y) es el número resultante de "pegar" los
-- números x e y. Por ejemplo, 
--    pegaNumerosNR 12 987   ==  12987
--    pegaNumerosNR 1204 7   ==  12047
--    pegaNumerosNR 100 100  ==  100100
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
pegaNumerosNR :: Integer -> Integer -> Integer
pegaNumerosNR x y = listaNumeroC (digitosC x ++ digitosC y) 

-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que las funciones
-- pegaNumerosR y pegaNumerosNR son equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_pegaNumeros :: Integer -> Integer -> Property
prop_pegaNumeros x y = x>=0 && y>=0 ==> pegaNumerosR x y == pegaNumerosNR x y 

-- La comprobación es

-- *Main> quickCheck prop_pegaNumeros
-- +++ OK, passed 100 tests; 291 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Definir, por recursión, la función 
--    primerDigitoR :: Integer -> Integer
-- tal que (primerDigitoR n) es el primer dígito de n. Por ejemplo, 
--    primerDigitoR 425  ==  4
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
primerDigitoR :: Integer -> Integer
primerDigitoR n = if n == mod n 10 then n else primerDigitoR (div n 10)
  
-- ---------------------------------------------------------------------
-- Ejercicio 8.2. Definir, sin usar recursión, la función 
--    primerDigitoNR :: Integer -> Integer
-- tal que (primerDigitoNR n) es la primera digito de n. Por ejemplo, 
--    primerDigitoNR 425  ==  4
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
primerDigitoNR :: Integer -> Integer
primerDigitoNR n = head [read [x] :: Integer | x <- (show n) ]

-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que las funciones
-- primerDigitoR y primerDigitoNR son equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_primerDigito :: Integer -> Property
prop_primerDigito x = x>=0 ==> primerDigitoR x == primerDigitoNR x 

-- La comprobación es
-- *Main> quickCheck prop_primerDigito
-- +++ OK, passed 100 tests; 86 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir la función 
--    ultimoDigito :: Integer -> Integer 
-- tal que (ultimoDigito n) es el último dígito de n. Por ejemplo, 
--    ultimoDigito 425  ==  5
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
ultimoDigito :: Integer -> Integer 
ultimoDigito n = mod n 10 

-- ---------------------------------------------------------------------
-- Ejercicio 10.1. Definir la función 
--    inverso :: Integer -> Integer
-- tal que (inverso n) es el número obtenido escribiendo los dígitos de n
-- en orden inverso. Por ejemplo, 
--    inverso 42578  ==  87524
--    inverso 203    ==    302
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
inverso :: Integer -> Integer
inverso n = sum [x*10^y | (x,y) <- zip (digitosR n) [0..]]

-- ---------------------------------------------------------------------
-- Ejercicio 10.2. Definir, usando show y read, la función 
--    inverso' :: Integer -> Integer
-- tal que (inverso' n) es el número obtenido escribiendo los dígitos de n
-- en orden inverso'. Por ejemplo, 
--    inverso' 42578  ==  87524
--    inverso' 203    ==    302
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
inverso' :: Integer -> Integer
inverso' n = read (reverse (show n)) :: Integer

-- ---------------------------------------------------------------------
-- Ejercicio 10.3. Comprobar con QuickCheck que las funciones
-- inverso e inverso' son equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_inverso :: Integer -> Property
prop_inverso n = n>=0 ==> inverso n == inverso' n

-- La comprobación es
-- *Main> quickCheck prop_inverso
-- +++ OK, passed 100 tests; 93 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 11. Definir la función 
--    capicua :: Integer -> Bool
-- tal que (capicua n) se verifica si si los dígitos que n son las mismas
-- de izquierda a derecha que de derecha a izquierda. Por ejemplo,
--    capicua 1234  =  False
--    capicua 1221  =  True
--    capicua 4     =  True
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
capicua :: Integer -> Bool
capicua n = and [x==y | (x,y) <- zip (digitosR n) (reverse (digitosR n))]

-- ---------------------------------------------------------------------
-- Ejercicio 12. (Problema 16 del proyecto Euler) El problema se
-- encuentra en http://goo.gl/4uWh y consiste en calcular la suma de los
-- dígitos de 2^1000. Lo resolveremos mediante los distintos apartados de
-- este ejercicio.  
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 13.1. Definir la función
--    euler16 :: Integer -> Integer
-- tal que (euler16 n) es la suma de los dígitos de 2^n. Por ejemplo,
--    euler16 4  ==  7
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
euler16 :: Integer -> Integer
euler16 n = sumaDigitosR (2^n)

-- ---------------------------------------------------------------------
-- Ejercicio 13.2. Calcular la suma de los dígitos de 2^1000.
-- ---------------------------------------------------------------------

-- El cálculo es
--    *Main> euler16 1000
--    1366

-- ---------------------------------------------------------------------
-- Ejercicio 14. En el enunciado de uno de los problemas de las
-- Olimpiadas matemáticas de Brasil se define el primitivo de un número
-- como sigue: 
--    Dado un número natural N, multiplicamos todos sus dígitos,
--    repetimos este procedimiento hasta que quede un solo dígito al
--    cual llamamos primitivo de N. Por ejemplo para 327: 3x2x7 = 42 y 
--    4x2 = 8. Por lo tanto, el primitivo de 327 es 8.
--
-- Definir la función 
--    primitivo :: Integer -> Integer
-- tal que (primitivo n) es el primitivo de n. Por ejemplo.
--    primitivo 327  ==  8
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
primitivo :: Integer -> Integer
primitivo n = if productoDeDigitos n == mod (productoDeDigitos n) 10 then productoDeDigitos n  else primitivo (productoDeDigitos n)
            where productoDeDigitos n = product (digitosR n)

-- ---------------------------------------------------------------------
-- Ejercicio 15. Dos números son equivalentes si la media de sus dígitos
-- son iguales. Por ejemplo, 3205 y 41 son equvalentes ya que 
-- (3+2+0+5)/4 = (4+1)/2. Definir la función 
--    equivalentes :: Integer -> Integer -> Bool
-- tal que (equivalentes x y) se verifica si los números x e y son
-- equivalentes. Por ejemplo,
--    equivalentes 3205 41  ==  True
--    equivalentes 3205 25  ==  False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
equivalentes :: Integer -> Integer -> Bool
equivalentes x y = fromIntegral((sumaDigitosR x)) / fromIntegral(numeroDigitos x) == fromIntegral((sumaDigitosR y)) / fromIntegral(numeroDigitos y)
                 where numeroDigitos n = sum [1 | _ <- (digitosR n)]  

-- ---------------------------------------------------------------------
-- Ejercicio 16. Un número x es especial si el número de ocurrencia de
-- cada dígito d de x en x^2 es el doble del número de ocurrencia de d
-- en x. Por ejemplo, 72576 es especial porque tiene un 2, un 5, un 6 y
-- dos 7 y su cuadrado es 5267275776 que tiene exactamente dos 2, dos 5,
-- dos 6 y cuatro 7.
-- 
-- Definir la función
--    especial :: Integer -> Bool
-- tal que (especial x) se verifica si x es un número especial. Por
-- ejemplo,
--    especial 72576  ==  True
--    especial 12     ==  False
-- Calcular el menor número especial mayor que 72576.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
especial :: Integer -> Bool
especial x = intersect (union (digitosR x) (digitosR x)) (digitosR (x^2)) == union (digitosR x) (digitosR x)

-- El cálculo es

calculoEspecial = head [x | x <- [72577..], especial x]

-- *Main> calculoEspecial 
-- 72577