He actualizado las soluciones del ejercicio «Permutación de elementos consecutivos» cuyo enunciado es

Definir la función

permutaConsecutivos :: [a] -> [a]

tal que (permutaConsecutivos xs) es la lista obtenida permutando los elementos consecutivos de xs. Por ejemplo,

permutaConsecutivos [1..8]         ==  [2,1,4,3,6,5,8,7]
permutaConsecutivos [1..9]         ==  [2,1,4,3,6,5,8,7,9]
permutaConsecutivos "simplemente"  ==  "ispmelemtne"

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio «Juego de bloques con letras» cuyo enunciado es

Para el juego de los bloques se dispone de un conjunto de bloques con una letra en cada una de sus dos caras. El objetivo del juego consiste en formar palabras sin que se pueda usar un bloque más de una vez y sin diferenciar mayúsculas de minúsculas. Por ejemplo, si se tiene tres bloques de forma que el 1º tiene las letras A y B, el 2ª la N y la O y el 3º la O y la A entonces se puede obtener la palabra ANA de dos formas: una con los bloques 1, 2 y 3 y otra con los 3, 2 y 1.

Definir la función

soluciones :: [String] -> String -> [[String]]

tal que (soluciones bs cs) es la lista de las soluciones del juego de los bloque usando los bloques bs (cada bloque es una cadena de dos letras mayúsculas) para formar la palabra cs. Por ejemplo,

λ> soluciones ["AB","NO","OA"] "ANA"
[["AB","NO","OA"],["OA","NO","AB"]]
λ> soluciones ["AB","NE","OA"] "Bea"
[["AB","NE","OA"]]
λ> soluciones ["AB","NE","OA"] "EvA"
[]
λ> soluciones ["AB","NO","OA","NC"] "ANA"
[["AB","NO","OA"],["AB","NC","OA"],["OA","NO","AB"],["OA","NC","AB"]]
λ> soluciones ["AB","NO","OA","NC"] "Anca"
[["AB","NO","NC","OA"],["OA","NO","NC","AB"]]

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio «Números que sumados a su siguiente primo dan primos» cuyo enunciado es

La Enciclopedia electrónica de sucesiones de enteros (OEIS por sus siglas en inglés, de On-Line Encyclopedia of Integer Sequences) es una base de datos que registra sucesiones de números enteros. Está disponible libremente en Internet, en la dirección http://oeis.org.

La semana pasada Antonio Roldán añadió una nueva sucesión a la OEIS, la A249624 que sirve de base para el problema de hoy.

Definir la sucesión

a249624 :: [Integer]

tal que sus elementos son los números x tales que la suma de x y el primo que le sigue es un número primo. Por ejemplo,

λ> take 20 a249624
[0,1,2,6,8,14,18,20,24,30,34,36,38,48,50,54,64,68,78,80]

El número 8 está en la sucesión porque su siguiente primo es 11 y 8+11=19 es primo. El 12 no está en la sucesión porque su siguiente primo es 13 y 12+13=25 no es primo.

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio «Normalización de expresiones aritméticas» cuyo enunciado es

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

data Expr = V String
          | S Expr Expr
          | P Expr Expre
  deriving (Eq, Show)

Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z")))

Una expresión es un término si es un producto de variables. Por ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x*(y*z) y x+(y*z) están en forma normal; pero x*(y+z) y (x+y)*(x+z) no lo están.

Definir la función

esTermino :: Expr -> Bool
esNormal  :: Expr -> Bool
normal    :: Expr -> Expr

tales que

• (esTermino a) se verifica si a es un término. Por ejemplo,

esTermino (V "x")                         == True
esTermino (P (V "x") (P (V "y") (V "z"))) == True
esTermino (P (V "x") (S (V "y") (V "z"))) == False
esTermino (S (V "x") (P (V "y") (V "z"))) == False

• (esNormal a) se verifica si a está en forma normal. Por ejemplo,

esNormal (V "x")                                     == True
esNormal (P (V "x") (P (V "y") (V "z")))             == True
esNormal (S (V "x") (P (V "y") (V "z")))             == True
esNormal (P (V "x") (S (V "y") (V "z")))             == False
esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False
esNormal (S (P (V "x") (V "y")) (S (V "z") (V "x"))) == True

• (normal e) es la forma normal de la expresión e obtenida aplicando, mientras que sea posible, las propiedades distributivas ((a+b)·c = a·c+b·c y c·(a+b) = c·a+c·b). Por ejemplo,

λ> normal (P (S (V "x") (V "y")) (V "z"))
S (P (V "x") (V "z")) (P (V "y") (V "z"))
λ> normal (P (V "z") (S (V "x") (V "y")))
S (P (V "z") (V "x")) (P (V "z") (V "y"))
λ> normal (P (S (V "x") (V "y")) (S (V "u") (V "v")))
S (S (P (V "x") (V "u")) (P (V "x") (V "v")))
   (S (P (V "y") (V "u")) (P (V "y") (V "v")))
λ> normal (S (P (V "x") (V "y")) (V "z"))
S (P (V "x") (V "y")) (V "z")
λ> normal (V "x")
V "x"

Comprobar con QuickCheck que para cualquier expresión e, (normal e) está en forma normal y que (normal (normal e)) es igual a (normal e).

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio «Sin consecutivos repetidos» cuyo enunciado es

Definir la función

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

tal que (sinConsecutivosRepetidos xs) es la lista obtenida a partir de xs de forma que si hay dos o más elementos idénticos consecutivos, borra las repeticiones y deja un elemento. Por ejemplo,

λ> sinConsecutivosRepetidos "eesssooo essss   toodddooo"
"eso es todo"

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio «Búsqueda en lista de listas de pares» cuyo enunciado es

Definir la función

busca :: Eq a => a -> [[(a,b)]] -> [b]

tal que (busca x pss) es la lista de los segundos componentes de los pares de la lista de listas de pares pss cuya primera componentes es x. Por ejemplo,

busca 3 [[(3,4)],[(5,4),(3,2),(3,5)],[(4,1),(7,3)]] == [4,2,5]

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio «Problema de las puertas» cuyo enunciado es

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puestas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:

• Inicialmente todas las puertas están cerradas.
• El primer camarero cambia de estado las puertas de todas las habitaciones.
• El segundo cambia de estado de las puertas de las habitaciones pares.
• El tercero cambia de estado todas las puertas que son múltiplos de 3.
• El cuarto cambia de estado todas las puertas que son múltiplos de 4
• Así, hasta que ha pasado el último camarero.

Por ejemplo, para n = 5

Pase    | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5
--------+----------+----------+----------+----------+---------
Inicial | Cerrada  | Cerrada  | Cerrada  | Cerrada  | Cerrada
Pase 1  | Abierta  | Abierta  | Abierta  | Abierta  | Abierta
Pase 2  | Abierta  | Cerrada  | Abierta  | Cerrada  | Abierta
Pase 3  | Abierta  | Cerrada  | Cerrada  | Cerrada  | Abierta
Pase 4  | Abierta  | Cerrada  | Cerrada  | Abierta  | Abierta
Pase 5  | Abierta  | Cerrada  | Cerrada  | Abierta  | Cerrada

Los estados de las puertas se representan por el siguiente tipo de datos

data Estado = Abierta | Cerrada
  deriving (Eq, Show)

Definir la función

final :: Int -> [Estado]

tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,

λ> final 5
[Abierta,Cerrada,Cerrada,Abierta,Cerrada]
λ> final 7
[Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio «Llanuras de longitud dada» cuyo enunciado es

Una llanura de longitud n de una lista xs es una sublista de xs formada por n elementos iguales.

Definir la función

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

tal que (llanuras n xs) es la lista de las llanuras de xs que tienen n elementos como mínimo. Por ejemplo,

llanuras 3 "aabbbcddddffxffxx"  ==  ["bbb","dddd"]

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Expresiones vectoriales cuyo enunciado es

El siguiente tipo de dato define las expresiones vectoriales formadas por un vector, la suma de dos expresiones vectoriales o el producto de un entero por una expresión vectorial.

data ExpV = Vec Int Int
          | Sum ExpV ExpV
          | Mul Int ExpV
  deriving Show

Definir la función

valor :: ExpV -> (Int,Int)

tal que (valor e) es el valor de la expresión vectorial e. Por ejemplo,

valor (Vec 1 2)                                  ==  (1,2)
valor (Sum (Vec 1 2 ) (Vec 3 4))                 ==  (4,6)
valor (Mul 2 (Vec 3 4))                          ==  (6,8)
valor (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4)))         ==  (8,12)
valor (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4)))  ==  (8,12)

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Expresiones aritmética normalizadas cuyo enunciado es

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

data Expr = Var String
          | S Expr Expr
          | P Expr Expre
  deriving Show

Por ejemplo, x.(y+z) se representa por (P (V "x") (S (V "y") (V "z"))).

Una expresión es un término si es un producto de variables. Por ejemplo, x.(y.z) es un término pero x+(y.z) ni x.(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x.(y,z) y x+(y.z) está en forma normal; pero x.(y+z) y (x+y).(x+z) no lo están.

Definir las funciones

esTermino :: Expr -> Bool
esNormal  :: Expr -> Bool

tales que

• (esTermino a) se verifica si a es un término. Por ejemplo,

esTermino (V "x")                                    == True
esTermino (P (V "x") (P (V "y") (V "z")))            == True
esTermino (P (V "x") (S (V "y") (V "z")))            == False
esTermino (S (V "x") (P (V "y") (V "z")))            == False

• (esNormal a) se verifica si a está en forma normal. Por ejemplo,

esNormal (V "x")                                     == True
esNormal (P (V "x") (P (V "y") (V "z")))             == True
esNormal (S (V "x") (P (V "y") (V "z")))             == True
esNormal (P (V "x") (S (V "y") (V "z")))             == False
esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Acrónimos cuyo enunciado es

A partir de una palabra de puede formar un acrónimo uniendo un prefijo de la primera con un sufijo de la segunda. Por ejemplo,

• "ofimática" es un acrónimo de "oficina" e "informática"
• "informática" es un acrónimo de "información" y "automática"
• "teleñeco" es un acrónimo de "televisión" y "muñeco"

Definir la función

esAcronimo :: String -> String -> String -> Bool

tal que (esAcronimo xs ys zs) se verifica si xs es un acrónimo de ys y zs. Por ejemplo,

esAcronimo "ofimatica" "oficina" "informatica"       ==  True
esAcronimo "informatica" "informacion" "automatica"  ==  True

Nota: Puedes consultar las soluciones aquí.

He actualizado las soluciones del ejercicio Particiones de longitud fija cuyo enunciado es

Definir la función

particionesFijas :: Int -> Int -> [[Int]]

tal que (particionesFijas n k) es la lista de listas de k números enteros positivos no crecientes cuya suma es el número entero positivo n. Por ejemplo,

λ> particionesFijas 8 2
[[4,4],[5,3],[6,2],[7,1]]
λ> particionesFijas 8 3
[[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]
λ> particionesFijas 9 3
[[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]]
λ> length (particionesFijas 67 5)
8056

Nota: Puedes consultar las soluciones aquí.

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"  ==  []