He actualizado las soluciones del ejercicio Evaluación de árboles de expresiones aritméticas cuyo enunciado es

Las expresiones aritméticas se pueden representar como árboles con números en las hojas y operaciones en los nodos. Por ejemplo, la expresión 9-2*4 se puede representar por el árbol

  -
 / \
9   *
   / \
  2   4

Definiendo el tipo de dato Arbol por

data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

la representación del árbol anterior es

N (-) (H 9) (N (*) (H 2) (H 4))

Definir la función

valor :: Arbol -> Int

tal que (valor a) es el valor de la expresión aritmética correspondiente al árbol a. Por ejemplo,

valor (N (-) (H 9) (N (*) (H 2) (H 4)))  ==  1
valor (N (+) (H 9) (N (*) (H 2) (H 4)))  ==  17
valor (N (+) (H 9) (N div (H 4) (H 2)))  ==  11
valor (N (+) (H 9) (N max (H 4) (H 2)))  ==  13

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Aplicaciones alternativas cuyo enunciado es

Definir la función

alternativa :: (a -> b) -> (a -> b) -> [a] -> [b]

tal que (alternativa f g xs) es la lista obtenida aplicando alternativamente las funciones f y g a los elementos de xs. Por ejemplo,

alternativa (+1)  (+10) [1,2,3,4]    ==  [2,12,4,14]
alternativa (+10) (*10) [1,2,3,4,5]  ==  [11,20,13,40,15]

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Repetición cíclica cuyo enunciado es

Definir la función

ciclica :: [a] -> [a]

tal que (ciclica xs) es la lista obtenida repitiendo cíclicamente los elementos de la lista no vacía xs. Por ejemplo,

take 10 (ciclica [3,5])    ==  [3,5,3,5,3,5,3,5,3,5]
take 10 (ciclica [3,5,7])  ==  [3,5,7,3,5,7,3,5,7,3]
take 10 (ciclica [3,5..])  ==  [3,5,7,9,11,13,15,17,19,21]

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Elemento común en menor posición cuyo enunciado es

Definir la función

elemento :: Eq a => [a] -> [a] -> [a]

tal que (elemento xs ys) es la lista formada por el elemento común a xs e ys con la menor posición global (considerando su posición en ambas listas). Por ejemplo.

elemento [3,7,6,9,8,0] [5,4,2,7,8,6,9]  ==  [7]
elemento [3,7,6,9] [9,5,6]              ==  [9]
elemento [5,3,6] [7,6,3]                ==  [3]
elemento [0,1,3] [3,1]                  ==  [3]
elemento [0,3,2] [1,2,3]                ==  [3]
elemento [3,7,6,3,8,0] [5,4,9,1,4,2,1]  ==  []
elemento [2,3,5] [7,4]                  ==  []

Nota: Como se observa en el 3ª ejemplo, en el caso de que un elemento x de xs pertenezca a ys y el elemento de ys en la misma posición que x pertenezca a xs, se elige como el de menor posición el de xs.

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Cuantificadores sobre listas cuyo enunciado es

Definir la función

verificaP :: (a -> Bool) -> [[a]] -> Bool

tal que (verificaP p xs) se verifica si cada elemento de la lista xss contiene algún elemento que cumple el predicado p. Por ejemplo,

verificaP odd [[1,3,4,2], [4,5], [9]] == True
verificaP odd [[1,3,4,2], [4,8], [9]] == False

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Inversa a trozos cuyo enunciado es

Definir la función

inversa :: Int -> [a] -> [a]

tal que (inversa k xs) es la lista obtenida invirtiendo elementos de xs, k elementos cada vez. Si el número de elementos de xs no es un múltiplo de k, entonces los finales elementos de xs se dejen sin invertir. Por ejemplo,

inversa 3 [1..11]  ==  [3,2,1,6,5,4,9,8,7,10,11]
inversa 4 [1..11]  ==  [4,3,2,1,8,7,6,5,9,10,11]

Comprobar con QuickCheck que la función inversa es involutiva; es decir, para todo número k > 0 y toda lista xs, se tiene que (inversa k (inversa k xs)) es igual a xs.

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Mínimos locales cuyo enunciado es

Un mínimo local de una lista es un elemento de la lista que es menor que su predecesor y que su sucesor en la lista. Por ejemplo, 1 es un mínimo local de [3,2,1,3,7,7,1,0,2] ya que es menor que 2 (su predecesor) y que 3 (su sucesor).

Definir la función

minimosLocales :: Ord a => [a] -> [a]

tal que (minimosLocales xs) es la lista de los mínimos locales de la lista xs. Por ejemplo,

minimosLocales [3,2,1,3,7,7,9,6,8]  ==  [1,6]
minimosLocales [1..100]             ==  []
minimosLocales "mqexvzat"           ==  "eva"

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Pequeño test de inteligencia cuyo enunciado es

Recientemente se publicó en la Red un pequeño test de inteligencia cuyo objetivo consistía en descubrir una función a partir de una colección de ejemplos. Los ejemplos eran los siguientes

f 6  4 == 210
f 9  2 == 711
f 8  5 == 313
f 5  2 == 37
f 7  6 == 113
f 9  8 == 117
f 10 6 == 416
f 15 3 == 1218

Definir la función

f :: Int -> Int -> Int

tal que f cubra los ejemplos anteriores y la definición de f sea lo más corta posible (en número de palabras).

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Mayores elementos de una matriz cuyo enunciado es

Las matrices se pueden representar mediante listas de listas. Por ejemplo, la matriz

|3 2 5|
|4 9 7|

se puede representar por [[3,2,5],[4,9,7]].

Definir la función

mayores :: Ord a => Int -> [[a]] -> [(a,Int)]

tal que (mayores n xss) es la lista de los n mayores elementos de la matriz xss junto con sus correspondientes número de fila. Por ejemplo,

λ> mayores 4 [[4,26,9],[2,37,53],[41,1,8]]
[(53,2),(41,3),(37,2),(26,1)]

Comprobar con QuickCheck que todos los elementos de (mayores n xss) son mayores o iguales que los restantes elementos de xss.

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Último dígito no nulo del factorial cuyo enunciado es

El factorial de 7 es

7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040

por tanto, el último dígito no nulo del factorial de 7 es 4.

Definir la función

ultimoNoNuloFactorial :: Integer -> Integer

tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,

ultimoNoNuloFactorial  7  == 4
ultimoNoNuloFactorial 10  == 8
ultimoNoNuloFactorial 12  == 6
ultimoNoNuloFactorial 97  == 2
ultimoNoNuloFactorial  0  == 1

Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Repetición de elementos cuyo enunciado es

Definir la función

repiteElementos :: Int -> [a] -> [a]

tal que (repiteElementos k xs) es la lista obtenida repitiendo k veces cada elemento de xs. Por ejemplo,

repiteElementos 3 [5,2,7,4]  ==  [5,5,5,2,2,2,7,7,7,4,4,4]

Comprobar con QuickCheck que, para todo número natural k y toda lista xs, el número de elementos de (repiteElementos k xs) es k veces el número de elementos de xs.

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Conjunto de primos relativos cuyo enunciado es

Dos números enteros son primos relativos si no tienen ningún factor primo en común, o, dicho de otra manera, si no tienen otro divisor común más que 1 y -1. Equivalentemente son primos entre sí, si y sólo si, su máximo común divisor es igual a 1.

Por ejemplo, 6 y 35 son primos entre sí, pero 6 y 27 no lo son porque ambos son divisibles por 3

Definir la función

primosRelativos :: [Int] -> Bool

tal que (primosRelativos xs) se verifica si los elementos de xs son primos relativos dos a dos. Por ejemplo,

primosRelativos [6,35]         ==  True
primosRelativos [6,27]         ==  False
primosRelativos [2,3,4]        ==  False
primosRelativos [6,35,11]      ==  True
primosRelativos [6,35,11,221]  ==  True
primosRelativos [6,35,11,231]  ==  False

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Precio total cuyo enunciado es

Una función de precio determina el precio de cada elemento; por ejemplo,

precioCI :: String -> Int
precioCI "leche"       = 10
precioCI "mantequilla" = 18
precioCI "patatas"     = 22
precioCI "chocolate"   = 16

Definir la función

precioTotal :: (String -> Int) -> [String] -> Int

tal que (precioTotal f xs) es el precio total de los elementos de xs respecto de la función de precio f. Por ejemplo,

precioTotal precioCI ["leche", "leche", "mantequilla"]  ==  38
precioTotal precioCI ["chocolate", "mantequilla"]       ==  34

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Extensión de un fichero cuyo enunciado es

La extensión de un fichero es la palabra a continuación del último punto en el nombre del fichero. Por ejemplo, la extensión de "documento.txt" es "txt"

Definir la función

extension :: String -> String

tal que (extension cs) es la extensión del fichero cs. Por ejemplo,

extension "ejercicio.hs"       ==  "hs"
extension "documento.txt"      ==  "txt"
extension "documento.txt.pdf"  ==  "pdf"
extension "resumen"            ==  ""

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Distancia de Hamming cuyo enunciado es

La distancia de Hamming entre dos listas es el número de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba" es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1ª y la 3ª).

Definir la función

distancia :: Eq a => [a] -> [a] -> Int

tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,

distancia "romano" "comino"  ==  2
distancia "romano" "camino"  ==  3
distancia "roma"   "comino"  ==  2
distancia "roma"   "camino"  ==  3
distancia "romano" "ron"     ==  1
distancia "romano" "cama"    ==  2
distancia "romano" "rama"    ==  1

Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad

distancia(xs,ys) = 0 si, y sólo si, xs = ys

y, en el caso de que no se verifique, modificar ligeramente propiedad para obtener una condición necesaria y suficiente de distancia(xs,ys) = 0.

He actualizado las soluciones del ejercicio Rompecabeza matemático cuyo enunciado es

Definir una función

f :: Int -> Int

tal que para todo n, f(f(n)) = -n y comprobar con QuickCheck que se cumple la propiedad

prop_f :: Int -> Bool
prop_f n = f (f n) == -n

es decir,

λ> quickCheck prop_f
+++ OK, passed 100 tests.

He actualizado las soluciones del ejercicio Suma de todos los anteriores cuyo enunciado es

Definir la función

sumaAnteriores :: [Integer] -> Bool

tal que (sumaAnteriores xs) se verifica si cada elemento de la lista xs (excepto el primero) es la suma de sus anteriores elementos en la lista. Por ejemplo,

sumaAnteriores [3,3,6,12]  ==  True
sumaAnteriores [3,3,7,10]  ==  False
sumaAnteriores [3]         ==  True
sumaAnteriores []          ==  True

He actualizado las soluciones del ejercicio Máximo de una función cuyo enunciado es

Se considera la siguiente función

g :: Integer -> Integer
g n = if n < 10 then n*n else n

Definir la función

max_g :: Integer -> Integer

tal que (max_g n) es el punto i del intervalo [0,n] donde g alcanza el máximo de sus valores, si n es positivo y 0 en caso contrario. Por ejemplo,

max_g (-7)  ==  0
max_g 7  ==  7
max_g 14  ==  9
max_g 84  ==  84

Comprobar con QuickCheck que la función max_g es equivalente a la función f definida por

f :: Integer -> Integer
f n | n < 0             = 0
    | n >= 10 && n < 81 = 9
    | otherwise         = n

He actualizado las soluciones del ejercicio Poner en mayúscula la primera letra y las restantes en minúsculas cuyo enunciado es

Definir la función

mayusculaInicial :: String -> String

tal que (mayusculaInicial xs) es la palabra xs con la letra inicial en mayúscula y las restantes en minúsculas. Por ejemplo,

mayusculaInicial "sEviLLa"  ==  "Sevilla"

He actualizado las soluciones del ejercicio Parte impar de un número cuyo enunciado es

Todo número entero \(n\) se puede escribir como \(m \times 2^k\), con \(m\) impar. Se dice que \(m\) es la parte impar de \(n\). Por ejemplo, la parte impar de 40 es 5 porque 40 = \(5 \times 2^3\).

Definir la función

parteImpar :: Int -> Int

tal que (parteImpar n) es la parte impar de n. Por ejemplo,

parteImpar 40  ==  5

He actualizado las soluciones del ejercicio Elementos no repetidos cuyo enunciado es

Definir la función

noRepetidos :: Eq a => [a] -> [a]

tal que (noRepetidos xs) es la lista de los elementos no repetidos de la lista xs. Por ejemplo,

noRepetidos [3,2,5,2,4,7,3]  ==  [5,4,7]
noRepetidos "noRepetidos"  ==  "nRptids"
noRepetidos "Roma"  ==  "Roma"

He actualizado las soluciones del ejercicio Listas equidigitales cuyo enunciado es

Una lista de números naturales es equidigital si todos sus elementos tienen el mismo número de dígitos.

Definir la función

equidigital :: [Int] -> Bool

tal que (equidigital xs) se verifica si xs es una lista equidigital. Por ejemplo,

equidigital [343,225,777,943]   ==  True
equidigital [343,225,777,94,3]  ==  False

He actualizado las soluciones del ejercicio Divisibles por el primero cuyo enunciado es

Definir la función

divisiblesPorPrimero :: [Int] -> Bool

tal que (divisibles xs) se verifica si todos los elementos positivos de xs son divisibles por el primero. Por ejemplo,

divisiblesPorPrimero [2,6,-3,0,18,-17,10]  ==  True
divisiblesPorPrimero [-13]                 ==  True
divisiblesPorPrimero [-3,6,1,-3,9,18]      ==  False
divisiblesPorPrimero [5,-2,-6,3]           ==  False
divisiblesPorPrimero []                    ==  True
divisiblesPorPrimero [0,2,4]               ==  False
divisiblesPorPrimero [0,-2,-4]             ==  True

Con la próxima entrada se inicia la actualización de los ejercicios del curso 2014-15.

¿En qué consiste la actualización?

Cada ejercicio será mejorado mediante las siguientes acciones:

• Ampliación de soluciones: se incorporarán nuevos enfoques y alternativas para resolver cada problema.
• Integración en Stack: se integrarán los ejercicios en el proyecto Stack disponible en el repositorio Exercitium.
• Comprobaciones con Hspec: se añadirán tests automatizados para validar las soluciones.
• Verificación con QuickCheck: se comprobará la equivalencia entre las distintas soluciones propuestas
• Análisis de eficiencia: se comparará el rendimiento de cada solución.

Estructura del curso

Los ejercicios están diseñados para incorporar conceptos de forma progresiva, siguiendo el desarrollo natural del curso. El material completo (temas, apuntes, ejercicios y exámenes) se encuentra disponible en Informática (2014-15).

Con el ejercicio anterior se completan los propuestos durante el curso 2013-14. Todos los ejercicios del curso, junto con sus soluciones, se recopilan en el libro Exercitium (Vol. 1).

He actualizado las soluciones del ejercicio Laberinto numérico cuyo enunciado es

El problema del laberinto numérico consiste en, dados un par de números, encontrar la longitud del camino más corto entre ellos usando sólo las siguientes operaciones:

• multiplicar por 2,
• dividir por 2 (sólo para los pares) y
• sumar 2.

Por ejemplo, un camino mínimo

• de 3 a 12 es [3,6,12],
• de 12 a 3 es [12,6,3],
• de 9 a 2 es [9,18,20,10,12,6,8,4,2] y
• de 2 a 9 es [2,4,8,16,18,9].

Definir la función

longitudCaminoMinimo :: Int -> Int -> Int

tal que (longitudCaminoMinimo x y) es la longitud del camino mínimo desde x hasta y en el laberinto numérico.

longitudCaminoMinimo 3 12  ==  2
longitudCaminoMinimo 12 3  ==  2
longitudCaminoMinimo 9 2   ==  8
longitudCaminoMinimo 2 9   ==  5

He actualizado las soluciones del ejercicio Sustitución en una expresión aritmética cuyo enunciado es

La expresiones aritméticas se pueden representar mediante el siguiente tipo

data Expr = C Int
          | V Char
          | S Expr Expr
          | P Expr Expr
  deriving (Eq, Show)

por ejemplo, la expresión "z*(3+x)" se representa por (P (V 'z') (S (C 3) (V 'x'))).

Definir la función

sustitucion :: Expr -> [(Char, Int)] -> Expr

tal que (sustitucion e s) es la expresión obtenida sustituyendo las variables de la expresión e según se indica en la sustitución s. Por ejemplo,

λ> sustitucion (P (V 'z') (S (C 3) (V 'x'))) [('x',7),('z',9)]
P (C 9) (S (C 3) (C 7))
λ> sustitucion (P (V 'z') (S (C 3) (V 'y'))) [('x',7),('z',9)]
P (C 9) (S (C 3) (V 'y'))

He actualizado las soluciones del ejercicio Clausura de un conjunto respecto de una función cuyo enunciado es

Un conjunto A está cerrado respecto de una función f si para todo elemento x de A se tiene que f(x) pertenece a A. La clausura de un conjunto B respecto de una función f es el menor conjunto A que contiene a B y es cerrado respecto de f. Por ejemplo, la clausura de {0,1,2} respecto del opuesto es {0,1,2,-1,-2}.

Definir la función

clausura :: Eq a => (a -> a) -> [a] -> [a]

tal que (clausura f xs) es la clausura de xs respecto de f. Por ejemplo,

clausura (\x -> -x) [0,1,2]         ==  [0,1,2,-1,-2]
clausura (\x -> (x+1) `mod` 5) [0]  ==  [0,1,2,3,4]

He actualizado las soluciones del ejercicio Cadenas de ceros y unos cuyo enunciado es

Definir la constante

cadenasCerosUnos :: [String]

tal que cadenasCerosUnos es la lista de cadenas de ceros y unos, ordenada lexicográficamente. Por ejemplo,

λ> take 15 cadenasCerosUnos1
["","0","1","00","01","10","11","000","001","010","011","100",
 "101","110","111"]

He actualizado las soluciones del ejercicio Números con todos sus dígitos primos cuyo enunciado es

Definir la lista

numerosConDigitosPrimos :: [Integer]

cuyos elementos son los números con todos sus dígitos primos. Por ejemplo,

λ> take 22 numerosConDigitosPrimos
[2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223]
λ> numerosConDigitosPrimos !! (10^7)
322732232572

He actualizado las soluciones del ejercicio Inserción en árboles binarios de búsqueda cuyo enunciado es

Un árbol binario de búsqueda (ABB) es un árbol binario tal que el cada nodo es mayor que los valores de su subárbol izquierdo y menor que los valores de su subárbol derecho y, además, ambos subárboles son árboles binarios de búsqueda. Por ejemplo, al almacenar los valores de [8,4,2,6,3] en un ABB se puede obtener el siguiente ABB:

   3
  / \
 /   \
2     6
     / \
    4   8

Los ABB se pueden representar como tipo de dato algebraico:

data ABB = V
  | N Int ABB ABB
  deriving (Eq, Show)

Por ejemplo, la definición del ABB anteriore es

ej :: ABB
ej = N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

Definir la función

inserta :: Int -> ABB -> ABB

tal que (inserta v a) es el árbol obtenido añadiendo el valor v al ABB a, si no es uno de sus valores. Por ejemplo,

λ>  inserta 5 ej
N 3 (N 2 V V) (N 6 (N 4 V (N 5 V V)) (N 8 V V))
λ>  inserta 1 ej
N 3 (N 2 (N 1 V V) V) (N 6 (N 4 V V) (N 8 V V))
λ>  inserta 2 ej
N 3 (N 2 V V) (N 6 (N 4 V V) (N 8 V V))

Comprobar con QuickCheck que al insertar un valor en un ABB se obtiene otro ABB.

He actualizado las soluciones del ejercicio Producto de matrices como listas de listas cuyo enunciado es

Las matrices pueden representarse mediante una lista de listas donde cada una de las lista representa una fila de la matriz. Por ejemplo, la matriz

|1 0 -2|
|0 3 -1|

puede representarse por [[1,0,-2],[0,3,-1]].

Definir la función

producto :: Num a => [[a]] -> [[a]] -> [[a]]

tal que (producto p q) es el producto de las matrices p y q. Por ejemplo,

λ> producto [[1,0,-2],[0,3,-1]] [[0,3],[-2,-1],[0,4]]
[[0,-5],[-6,-7]]

He actualizado las soluciones del ejercicio Sucesiones pucelanas cuyo enunciado es

En la Olimpiada de Matemática del 2010 se planteó el siguiente problema:

Una sucesión pucelana es una sucesión creciente de 16 números impares positivos consecutivos, cuya suma es un cubo perfecto. ¿Cuántas sucesiones pucelanas tienen solamente números de tres cifras?

Para resolverlo se propone el siguiente ejercicio.

Definir la función

pucelanasConNcifras :: Int -> [[Int]]

tal que (pucelanasConNcifras n) es la lista de las sucesiones pucelanas que tienen solamente números de n cifras. Por ejemplo,

λ> pucelanasConNcifras 2
[[17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47]]

Calcular cuántas sucesiones pucelanas tienen solamente números de tres cifras.

He actualizado las soluciones del ejercicio Todas tienen par cuyo enunciado es

Definir la función

todasTienenPar :: [[Int]] -> Bool

tal que tal que todasTienenPar xss se verifica si cada elemento de la lista de listas xss contiene algún número par. Por ejemplo,

todasTienenPar [[1,2],[3,4,5],[8]]  ==  True
todasTienenPar [[1,2],[3,5]]        ==  False

He actualizado las soluciones del ejercicio Producto cartesiano de una familia de conjuntos cuyo enunciado es

Definir la función

producto :: [[a]] -> [[a]]

tal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,

λ> producto [[2,5],[6,4]]
[[2,6],[2,4],[5,6],[5,4]]
λ> producto [[1,3],[2,5],[6,4]]
[[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
λ> producto [[1,3,5],[2,4]]
[[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]]
λ> producto []
[[]]

Comprobar con QuickCheck que para toda lista de listas de enteros, xss, se verifica que el número de elementos de (producto xss) es igual al producto de los números de elementos de cada una de las listas de xss.

He actualizado las soluciones del ejercicio Código Morse cuyo enunciado es

El código Morse es un sistema de representación de letras y números mediante señales emitidas de forma intermitente.

A los signos (letras mayúsculas o dígitos) se le asigna un código como se muestra a continuación

+---+-------+---+-------+---+-------+---+-------+
| A | .-    | J | .---  | S | ...   | 1 | ..--- |
| B | -...  | K | -.-   | T | -     | 2 | ...-- |
| C | -.-.  | L | .-..  | U | ..-   | 3 | ....- |
| D | -..   | M | --    | V | ...-  | 4 | ..... |
| E | .     | N | -.    | W | .--   | 5 | -.... |
| F | ..-.  | O | ---   | X | -..-  | 6 | --... |
| G | --.   | P | .--.  | Y | -.--  | 7 | ---.. |
| H | ....  | Q | --.-  | Z | --..  | 8 | ----. |
| I | ..    | R | .-.   | 0 | .---- | 9 | ----- |
+---+-------+---+-------+---+-------+---+-------+

El código Morse de las palabras se obtiene a partir del de sus caracteres insertando un espacio entre cada uno. Por ejemplo, el código de "todo" es "- --- -.. ---"

El código Morse de las frase se obtiene a partir del de sus palabras insertando un espacio entre cada uno. Por ejemplo, el código de "todo o nada" es "- --- -.. --- --- -. .- -.. .-"

Definir las funciones

fraseAmorse :: String -> String
morseAfrase :: String -> String

tales que

• (fraseAmorse cs) es la traducción de la frase cs a Morse. Por ejemplo,

λ> fraseAmorse "En todo la medida"
". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"

• (morseAfrase cs) es la frase cuya traducción a Morse es cs. Por ejemplo,

λ> morseAfrase ". -.  - --- -.. ---  .-.. .-  -- . -.. .. -.. .-"
"EN TODO LA MEDIDA"

Nota: La lista de los códigos Morse de A, B, ..., Z, 0, 1, ..., 9 es

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---",
 "-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",
 "..-","...-",".--","-..-","-.--","--..",".----","..---","...--",
 "....-",".....","-....","--...","---..","----.","-----"]

He actualizado las soluciones del ejercicio Elemento más cercano que cumple una propiedad cuyo enunciado es

Definir la función

cercano :: (a -> Bool) -> Int -> [a] -> Maybe a

tal que (cercano p n xs) es el elemento de xs cuya posición es la cercana a la posición n que verifica la propiedad p. La búsqueda comienza en n y los elementos se analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo,

cercano (`elem` "aeiou") 6 "Sevilla"     ==  Just 'a'
cercano (`elem` "aeiou") 1 "Sevilla"     ==  Just 'e'
cercano (`elem` "aeiou") 2 "Sevilla"     ==  Just 'i'
cercano (`elem` "aeiou") 5 "Sevilla"     ==  Just 'a'
cercano (`elem` "aeiou") 9 "Sevilla"     ==  Just 'a'
cercano (`elem` "aeiou") (-3) "Sevilla"  ==  Just 'e'
cercano (>100) 4 [200,1,150,2,4]         ==  Just 150
cercano even 5 [1,3..99]                 ==  Nothing

He actualizado las soluciones del ejercicio Representación de Zeckendorf cuyo enunciado es

Los primeros números de Fibonacci son

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

tales que los dos primeros son iguales a 1 y los siguientes se obtienen sumando los dos anteriores.

El teorema de Zeckendorf establece que todo entero positivo n se puede representar, de manera única, como la suma de números de Fibonacci no consecutivos decrecientes. Dicha suma se llama la representación de Zeckendorf de n. Por ejemplo, la representación de Zeckendorf de 100 es

100 = 89 + 8 + 3

Hay otras formas de representar 100 como sumas de números de Fibonacci; por ejemplo,

100 = 89 +  8 + 2 + 1
100 = 55 + 34 + 8 + 3

pero no son representaciones de Zeckendorf porque 1 y 2 son números de Fibonacci consecutivos, al igual que 34 y 55.

Definir la función

zeckendorf :: Integer -> [Integer]

tal que (zeckendorf n) es la representación de Zeckendorf de n. Por ejemplo,

zeckendorf 100       == [89,8,3]
zeckendorf 2014      == [1597,377,34,5,1]
zeckendorf 28656     == [17711,6765,2584,987,377,144,55,21,8,3,1]
zeckendorf 14930396  == [14930352,34,8,2]

He actualizado las soluciones del ejercicio Ventana deslizante cuyo enunciado es

Definir la función

ventanas :: Int -> Int -> [a] -> [[a]]

tal que (ventanas x y zs) es la lista de ventanas de zs de tamaño x y deslizamiento y; es decir, listas de x elementos consecutivos de zs (salvo, posiblemente, la última que puede ser menor) tales que la diferencia de posiciones entre los primeros elementos de ventanas consecutivas es y. Por ejemplo,

ventanas 3 2 [5,1,9,2] == [[5,1,9],[9,2]]
ventanas 3 3 [5,1,9,2] == [[5,1,9],[2]]
ventanas 3 4 [5,1,9,2] == [[5,1,9]]
ventanas 4 1 [1..7]    == [[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7]]
ventanas 4 2 [1..7]    == [[1,2,3,4],[3,4,5,6],[5,6,7]]
ventanas 4 3 [1..7]    == [[1,2,3,4],[4,5,6,7]]
ventanas 4 4 [1..7]    == [[1,2,3,4],[5,6,7]]
ventanas 4 5 [1..7]    == [[1,2,3,4],[6,7]]
ventanas 4 6 [1..7]    == [[1,2,3,4],[7]]
ventanas 4 7 [1..7]    == [[1,2,3,4]]
ventanas 4 8 [1..7]    == [[1,2,3,4]]
ventanas 3 2 "abcdef"  == ["abc","cde","ef"]
ventanas 3 3 "abcdef"  == ["abc","def"]
ventanas 3 4 "abcdef"  == ["abc","ef"]
ventanas 3 5 "abcdef"  == ["abc","f"]
ventanas 3 6 "abcdef"  == ["abc"]
ventanas 3 7 "abcdef"  == ["abc"]
ventanas 1 5 "abcdef"  == ["a","f"]

He actualizado las soluciones del ejercicio Divide si todos son múltiplos cuyo enunciado es

Definir la función

divideSiTodosMultiplos :: Integral a => a -> [a] -> Maybe [a]

tal que (divideSiTodosMultiplos x ys) es justo la lista de los cocientes de los elementos de ys entre x si todos son múltiplos de de número no nulo x y Nothing en caso contrario. Por ejemplo,

divideSiTodosMultiplos 2 [6,10,4]  ==  Just [3,5,2]
divideSiTodosMultiplos 2 [6,10,5]  ==  Nothing

He actualizado las soluciones del ejercicio Renombramiento de un árbol cuyo enunciado es

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq, Foldable, Functor)

Por ejemplo, el árbol

      "C"
      / \
     /   \
    /     \
  "B"     "A"
  / \     / \
"A" "B" "B" "C"

se puede definir por

ej1 :: Arbol String
ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

Definir la función

renombraArbol :: Arbol t -> Arbol Int

tal que (renombraArbol a) es el árbol obtenido sustituyendo el valor de los nodos y hojas por números tales que tengan el mismo valor si y sólo si coincide su contenido. Por ejemplo,

λ> renombraArbol ej1
N 2 (N 1 (H 0) (H 1)) (N 0 (H 1) (H 2))

Gráficamente,

      2
     / \
    /   \
   /     \
  1       0
 / \     / \
0   1   1   2

He actualizado las soluciones del ejercicio Empiezan con mayúscula cuyo enunciado es

Definir la función

conMayuscula :: String -> Int

tal que (conMayuscula cs) es el número de palabras de cs que empiezan con mayúscula. Por ejemplo.

conMayuscula "Juan vive en Sevilla o en Huelva"  ==  3

He actualizado las soluciones del ejercicio Límite de sucesiones cuyo enunciado es

Definir la función

limite :: (Double -> Double) -> Double -> Double

tal que (limite f a) es el valor de f en el primer término x tal que, para todo y entre x+1 y x+100, el valor absoluto de la diferencia entre f(y) y f(x) es menor que a. Por ejemplo,

limite (\n -> (2*n+1)/(n+5)) 0.001  ==  1.9900110987791344
limite (\n -> (1+1/n)**n) 0.001     ==  2.714072874546881

He actualizado las soluciones del ejercicio Eliminación de n elementos cuyo enunciado es

Definir la función

elimina :: Int -> [a] -> [[a]]

tal que (elimina n xs) es la lista de las listas obtenidas eliminando n elementos de xs. Por ejemplo,

elimina 0 "abcd"  ==  ["abcd"]
elimina 1 "abcd"  ==  ["bcd","acd","abd","abc"]
elimina 2 "abcd"  ==  ["cd","bd","bc","ad","ac","ab"]
elimina 3 "abcd"  ==  ["d","c","b","a"]
elimina 4 "abcd"  ==  [""]
elimina 5 "abcd"  ==  []
elimina 6 "abcd"  ==  []

He actualizado las soluciones del ejercicio Intercalación de n copias cuyo enunciado es

Definir la función

intercala :: Int -> a -> [a] -> [[a]]

tal que (intercala n x ys) es la lista de la listas obtenidas intercalando n copias de x en ys. Por ejemplo,

intercala 2 'a' "bc" == ["bcaa","baca","baac","abca","abac","aabc"]
intercala 2 'a' "c"  == ["caa","aca","aac"]
intercala 1 'a' "c"  == ["ca","ac"]
intercala 0 'a' "c"  == ["c"]

He actualizado las soluciones del ejercicio Sopa de letras cuyo enunciado es

Las matrices se puede representar mediante tablas cuyos índices son pares de números naturales:

type Matriz a = Array (Int,Int) a

Definir la función

enLaSopa :: Eq a => [a] -> Matriz a -> Bool

tal que (enLaSopa c p) se verifica si c está en la matriz p en horizontal o en vertical. Por ejemplo, si ej1 es la matriz siguiente:

ej1 :: Matriz Char
ej1 = listaMatriz ["mjtholueq",
                   "juhoolauh",
                   "dariouhyj",
                   "rngkploaa"]

donde la función listaMatriz está definida por

listaMatriz :: [[a]] -> Matriz a
listaMatriz xss = listArray ((1,1),(m,n)) (concat xss)
  where m = length xss
        n = length (head xss)

entonces,

enLaSopa "dar"  p  ==  True   -- En horizontal a la derecha en la 3ª fila
enLaSopa "oir"  p  ==  True   -- En horizontal a la izquierda en la 3ª fila
enLaSopa "juan" p  ==  True   -- En vertical descendente en la 2ª columna
enLaSopa "kio"  p  ==  True   -- En vertical ascendente en la 3ª columna
enLaSopa "Juan" p  ==  False
enLaSopa "hola" p  ==  False

He actualizado las soluciones del ejercicio N gramas cuyo enunciado es

Un n-grama de una sucesión es una subsucesión contigua de n elementos.

Definir la función

nGramas :: Int -> [a] -> [[a]]

tal que (nGramas k xs) es la lista de los n-gramas de xs de longitud k. Por ejemplo,

nGramas 0 "abcd"  ==  []
nGramas 1 "abcd"  ==  ["a","b","c","d"]
nGramas 2 "abcd"  ==  ["ab", "bc", "cd"]
nGramas 3 "abcd"  ==  ["abc", "bcd"]
nGramas 4 "abcd"  ==  ["abcd"]
nGramas 5 "abcd"  ==  []

He actualizado las soluciones del ejercicio Entero positivo de la cadena cuyo enunciado es

Definir la función

enteroPositivo :: String -> Maybe Int

tal que (enteroPositivo cs) es justo el contenido de la cadena cs, si dicho contenido es un entero positivo, y Nothing en caso contrario. Por ejemplo,

enteroPositivo "235"    ==  Just 235
enteroPositivo "-235"   ==  Nothing
enteroPositivo "23.5"   ==  Nothing
enteroPositivo "235 "   ==  Nothing
enteroPositivo "cinco"  ==  Nothing
enteroPositivo ""       ==  Nothing

He actualizado las soluciones del ejercicio Filtro booleano cuyo enunciado es

Definir la función

filtroBooleano :: [Bool] -> [a] -> [Maybe a]

tal que (filtroBooleano xs ys) es la lista de los elementos de ys tales que el elemento de xs en la misma posición es verdadero. Por ejemplo,

λ> filtroBooleano [True,False,True] "Sevilla"
[Just 'S',Nothing,Just 'v']
λ> filtroBooleano (repeat True) "abc"
[Just 'a',Just 'b',Just 'c']
λ> take 3 (filtroBooleano (repeat True) [1..])
[Just 1,Just 2,Just 3]
λ> take 3 (filtroBooleano (repeat False) [1..])
[Nothing,Nothing,Nothing]
λ> take 3 (filtroBooleano (cycle [True,False]) [1..])
[Just 1,Nothing,Just 3]

He actualizado las soluciones del ejercicio Mayor sucesión del problema 3n+1 cuyo enunciado es

La sucesión 3n+1 generada por un número entero positivo x es sucesión generada por el siguiente algoritmo: Se empieza con el número x. Si x es par, se divide entre 2. Si x es impar, se multiplica por 3 y se le suma 1. El proceso se repite con el número obtenido hasta que se alcanza el valor 1. Por ejemplo, la sucesión de números generadas cuando se empieza en 22 es

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Se ha conjeturado (aunque no demostrado) que este algoritmo siempre alcanza el 1 empezando en cualquier entero positivo.

Definir la función

mayorLongitud :: Integer -> Integer -> Integer

tal que (mayorLongitud i j) es el máximo de las longitudes de las sucesiones 3n+1 para todos los números comprendidos entre i y j, ambos inclusives. Por ejemplo,

mayorLongitud   1   10  ==  20
mayorLongitud 100  200  ==  125
mayorLongitud 201  210  ==  89
mayorLongitud 900 1000  ==  174

He actualizado las soluciones del ejercicio Buscaminas cuyo enunciado es

El buscaminas es un juego cuyo objetivo es despejar un campo de minas sin detonar ninguna.

El campo de minas se representa mediante un cuadrado con NxN casillas. Algunas casillas tienen un número, este número indica las minas que hay en todas las casillas vecinas. Cada casilla tiene como máximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda contiene dos minas, cada una representada por el número 9, y a la derecha se muestra el campo obtenido anotando las minas vecinas de cada casilla

9 0 0 0       9 1 0 0
0 0 0 0       2 2 1 0
0 9 0 0       1 9 1 0
0 0 0 0       1 1 1 0

de la misma forma, la anotación del siguiente a la izquierda es el de la derecha

9 9 0 0 0     9 9 1 0 0
0 0 0 0 0     3 3 2 0 0
0 9 0 0 0     1 9 1 0 0

Utilizando la librería Data.Matrix, los campos de minas se representan mediante matrices:

type Campo = Matrix Int

Por ejemplo, los anteriores campos de la izquierda se definen por

ejCampo1, ejCampo2 :: Campo
ejCampo1 = fromLists [[9,0,0,0],
                      [0,0,0,0],
                      [0,9,0,0],
                      [0,0,0,0]]
ejCampo2 = fromLists [[9,9,0,0,0],
                      [0,0,0,0,0],
                      [0,9,0,0,0]]

Definir la función

buscaminas :: Campo -> Campo

tal que buscaminas c es el campo obtenido anotando las minas vecinas de cada casilla. Por ejemplo,

λ> buscaminas ejCampo1
( 9 1 0 0 )
( 2 2 1 0 )
( 1 9 1 0 )
( 1 1 1 0 )

λ> buscaminas ejCampo2
( 9 9 1 0 0 )
( 3 3 2 0 0 )
( 1 9 1 0 0 )

He actualizado las soluciones del ejercicio Selección hasta el primero que falla inclusive cuyo enunciado es

Definir la función

seleccionConFallo :: (a -> Bool) -> [a] -> [a]

tal que (seleccionConFallo p xs) es la lista de los elementos de xs que cumplen el predicado p hasta el primero que no lo cumple inclusive. Por ejemplo,

seleccionConFallo (<5) [3,2,5,7,1,0]  ==  [3,2,5]
seleccionConFallo odd [1..4]          ==  [1,2]
seleccionConFallo odd [1,3,5]         ==  [1,3,5]
seleccionConFallo (<5) [10..20]       ==  [10]

He actualizado las soluciones del ejercicio Descomposiciones como sumas de n sumandos cuyo enunciado es

Definir la función

sumas :: (Num a, Ord a) => Int -> [a] -> a -> [[a]]

tal que (sumas n ys x) es la lista de las descomposiciones de x como sumas de n sumandos en la lista ys. Por ejemplo,

sumas 2 [1,2] 3     == [[1,2]]
sumas 2 [-1] (-2)   == [[-1,-1]]
sumas 2 [-1,3,-1] 2 == [[-1,3]]
sumas 2 [1,2] 4     == [[2,2]]
sumas 2 [1,2] 5     == []
sumas 3 [1,2] 5     == [[1,2,2]]
sumas 3 [1,2] 6     == [[2,2,2]]
sumas 2 [1,2,5] 6   == [[1,5]]
sumas 2 [1,2,3,5] 4 == [[1,3],[2,2]]
sumas 2 [1..5] 6    == [[1,5],[2,4],[3,3]]
sumas 3 [1..5] 7    == [[1,1,5],[1,2,4],[1,3,3],[2,2,3]]
sumas 3 [1..200] 4  == [[1,1,2]]

He actualizado las soluciones del ejercicio Divisores de un número con final dado cuyo enunciado es

Definir la función

divisoresConFinal :: Integer -> Integer -> [Integer]

tal que (divisoresConFinal n m) es la lista de los divisores de n cuyos dígitos finales coincide con m. Por ejemplo,

divisoresConFinal 84 4    ==  [4,14,84]
divisoresConFinal 720 20  ==  [20,120,720]

He actualizado las soluciones del ejercicio Órbita prima cuyo enunciado es

La órbita prima de un número n es la sucesión construida de la siguiente forma:

• si n es compuesto su órbita no tiene elementos
• si n es primo, entonces n está en su órbita; además, sumamos n y sus dígitos, si el resultado es un número primo repetimos el proceso hasta obtener un número compuesto.

Por ejemplo, con el 11 podemos repetir el proceso dos veces

13 = 11+1+1
17 = 13+1+3
25 = 17+1+7

Así, la órbita prima de 11 es 11, 13, 17.

Definir la función

orbita :: Integer -> [Integer]

tal que (orbita n) es la órbita prima de n. Por ejemplo,

orbita 11 == [11,13,17]
orbita 59 == [59,73,83]

Calcular el menor número cuya órbita prima tiene más de 3 elementos.

He actualizado las soluciones del ejercicio Ordenada cíclicamente cuyo enunciado es

Se dice que una sucesión x(1), ..., x(n) está ordenada cíclicamente si existe un índice i tal que la sucesión

x(i), x(i+1), ..., x(n), x(1), ..., x(i-1)

está ordenada creciente de forma estricta.

Definir la función

ordenadaCiclicamente :: Ord a => [a] -> Maybe Int

tal que (ordenadaCiclicamente xs) es el índice a partir del cual está ordenada, si la lista está ordenado cíclicamente y Nothing en caso contrario. Por ejemplo,

ordenadaCiclicamente [1,2,3,4]      ==  Just 0
ordenadaCiclicamente [5,8,1,3]      ==  Just 2
ordenadaCiclicamente [4,6,7,5,1,3]  ==  Nothing
ordenadaCiclicamente [1,0,3,2]      ==  Nothing
ordenadaCiclicamente [1,2,0]        ==  Just 2
ordenadaCiclicamente "cdeab"        ==  Just 3

Nota: Se supone que el argumento es una lista no vacía sin elementos repetidos.

He actualizado las soluciones del ejercicio Eliminación de las ocurrencias aisladas cuyo enunciado es

Definir la función

eliminaAisladas :: Eq a => a -> [a] -> [a]

tal que (eliminaAisladas x ys) es la lista obtenida eliminando de ys las ocurrencias aisladas de x (es decir, aquellas ocurrencias de x tales que su elemento anterior y posterior son distintos de x). Por ejemplo,

eliminaAisladas 'X' ""                  == ""
eliminaAisladas 'X' "X"                 == ""
eliminaAisladas 'X' "XX"                == "XX"
eliminaAisladas 'X' "XXX"               == "XXX"
eliminaAisladas 'X' "abcd"              == "abcd"
eliminaAisladas 'X' "Xabcd"             == "abcd"
eliminaAisladas 'X' "XXabcd"            == "XXabcd"
eliminaAisladas 'X' "XXXabcd"           == "XXXabcd"
eliminaAisladas 'X' "abcdX"             == "abcd"
eliminaAisladas 'X' "abcdXX"            == "abcdXX"
eliminaAisladas 'X' "abcdXXX"           == "abcdXXX"
eliminaAisladas 'X' "abXcd"             == "abcd"
eliminaAisladas 'X' "abXXcd"            == "abXXcd"
eliminaAisladas 'X' "abXXXcd"           == "abXXXcd"
eliminaAisladas 'X' "XabXcdX"           == "abcd"
eliminaAisladas 'X' "XXabXXcdXX"        == "XXabXXcdXX"
eliminaAisladas 'X' "XXXabXXXcdXXX"     == "XXXabXXXcdXXX"
eliminaAisladas 'X' "XabXXcdXeXXXfXx"   == "abXXcdeXXXfx"