Ir al contenido principal

Actualización de «Elemento más cercano que cumple una propiedad»

Actualización

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

Actualización de «Representación de Zeckendorf»

Actualización

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]

Actualización de «Ventana deslizante»

Actualización

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

Actualización de «Divide si todos son múltiplos»

Actualización

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

Actualización de «Renombramiento de un árbol»

Actualización

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

Actualización de «Límite de sucesiones»

Actualización

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

Actualización de «Eliminación de n elementos»

Actualización

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

Actualización de «Intercalación de n copias»

Actualización

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

Actualización de «Sopa de letras»

Actualización

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

Actualización de «N gramas»

Actualización

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

Actualización de «Entero positivo de la cadena»

Actualización

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

Actualización de «Filtro booleano»

Actualización

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]

Actualización de «Mayor sucesión del problema 3n+1»

Actualización

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

Actualización de «Buscaminas»

Actualización

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 )

Actualización de «Selección hasta el primero que falla inclusive»

Actualización

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]

Actualización de «Descomposiciones como sumas de n sumandos»

Actualización

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]]

Actualización de «Órbita prima»

Actualización

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.

Actualización de «Ordenada cíclicamente»

Actualización

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.

Actualización de «Eliminación de las ocurrencias aisladas»

Actualización

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"

Actualización de «Emparejamiento de árboles»

Actualización

He actualizado las soluciones del ejercicio Emparejamiento de árboles cuyo enunciado es

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
  deriving (Show, Eq)

Por ejemplo, los árboles

  1               3
 / \             /|\
6   3           / | \
    |          5  4  7
    5          |     /\
               6    2  1

se representan por

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 6 [],N 3 [N 5 []]]
ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]

Definir la función

emparejaArboles :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c

tal que (emparejaArboles f a1 a2) es el árbol obtenido aplicando la función f a los elementos de los árboles a1 y a2 que se encuentran en la misma posición. Por ejemplo,

λ> emparejaArboles (+) (N 1 [N 2 [], N 3[]]) (N 1 [N 6 []])
N 2 [N 8 []]
λ> emparejaArboles (+) ej1 ej2
N 4 [N 11 [],N 7 []]
λ> emparejaArboles (+) ej1 ej1
N 2 [N 12 [],N 6 [N 10 []]]

Actualización de «Separación por posición»

Actualización

He actualizado las soluciones del ejercicio Separación por posición cuyo enunciado es

Definir la función

particion :: [a] -> ([a],[a])

tal que (particion xs) es el par cuya primera componente son los elementos de xs en posiciones pares y su segunda componente son los restantes elementos. Por ejemplo,

particion [3,5,6,2]    ==  ([3,6],[5,2])
particion [3,5,6,2,7]  ==  ([3,6,7],[5,2])
particion "particion"  ==  ("priin","atco")

Actualización de «Número de inversiones»

Actualización

He actualizado las soluciones del ejercicio Número de inversiones cuyo enunciado es

Se dice que en una sucesión de números x(1), x(2), ..., x(n) hay una inversión cuando existe un par de números x(i) > x(j), siendo i < j. Por ejemplo, en la permutación 2, 1, 4, 3 hay dos inversiones (2 antes que 1 y 4 antes que 3) y en la permutación 4, 3, 1, 2 hay cinco inversiones (4 antes 3, 4 antes 1, 4 antes 2, 3 antes 1, 3 antes 2).

Definir la función

numeroInversiones :: Ord a => [a] -> Int

tal que (numeroInversiones xs) es el número de inversiones de xs. Por ejemplo,

numeroInversiones [2,1,4,3]  ==  2
numeroInversiones [4,3,1,2]  ==  5

Actualización de «Descomposiciones triangulares»

Actualización

He actualizado las soluciones del ejercicio Descomposiciones triangulares cuyo enunciado es

Los números triangulares se forman como sigue

*     *      *
     * *    * *
           * * *
1     3      6

La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

Definir la función

descomposicionesTriangulares :: Int -> [(Int, Int, Int)]

tal que descomposicionesTriangulares n es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos, como máximo, formados por números triangulares. Por ejemplo,

λ> descomposicionesTriangulares 4
[]
λ> descomposicionesTriangulares 5
[(1,1,3)]
λ> descomposicionesTriangulares 12
[(1,1,10),(3,3,6)]
λ> descomposicionesTriangulares 30
[(1,1,28),(3,6,21),(10,10,10)]
λ> descomposicionesTriangulares 61
[(1,15,45),(3,3,55),(6,10,45),(10,15,36)]
λ> descomposicionesTriangulares 52
[(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]
λ> descomposicionesTriangulares 82
[(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]
λ> length (descomposicionesTriangulares (5*10^6))
390

Actualización de «Índices de valores verdaderos»

Actualización

He actualizado las soluciones del ejercicio Índices de valores verdaderos cuyo enunciado es

Definir la función

indicesVerdaderos :: [Int] -> [Bool]

tal que (indicesVerdaderos xs) es la lista infinita de booleanos tal que sólo son verdaderos los elementos cuyos índices pertenecen a la lista estrictamente creciente xs. Por ejemplo,

λ> take 6 (indicesVerdaderos [1,4])
[False,True,False,False,True,False]
λ> take 6 (indicesVerdaderos [0,2..])
[True,False,True,False,True,False]
λ> take 3 (indicesVerdaderos [])
[False,False,False]
λ> take 6 (indicesVerdaderos [1..])
[False,True,True,True,True,True]
λ> last (take (8*10^7) (indicesVerdaderos [0,5..]))
False

Actualización de «Código de las alergias»

Actualización

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

Para la determinación de las alergia se utiliza los siguientes códigos para los alérgenos:

Huevos ........   1
Cacahuetes ....   2
Mariscos ......   4
Fresas ........   8
Tomates .......  16
Chocolate .....  32
Polen .........  64
Gatos ......... 128

Así, si Juan es alérgico a los cacahuetes y al chocolate, su puntuación es 34 (es decir, 2+32).

Los alérgenos se representan mediante el siguiente tipo de dato

data Alergeno = Huevos
              | Cacahuetes
              | Mariscos
              | Fresas
              | Tomates
              | Chocolate
              | Polen
              | Gatos
  deriving (Enum, Eq, Show, Bounded)

Definir la función

alergias :: Int -> [Alergeno]

tal que (alergias n) es la lista de alergias correspondiente a una puntuación n. Por ejemplo,

λ> alergias 1
[Huevos]
λ> alergias 2
[Cacahuetes]
λ> alergias 3
[Huevos,Cacahuetes]
λ> alergias 5
[Huevos,Mariscos]
λ> alergias 255
[Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos]

Actualización de «Pim, Pam, Pum y divisibilidad»

Actualización

He actualizado las soluciones del ejercicio Pim, Pam, Pum y divisibilidad cuyo enunciado es

Definir la función

sonido :: Int -> String

tal que (sonido n) escribe "Pim" si n es divisible por 3, además escribe "Pam" si n es divisible por 5 y también escribe "Pum" si n es divisible por 7. Por ejemplo,

sonido   3  ==  "Pim"
sonido   5  ==  "Pam"
sonido   7  ==  "Pum"
sonido   8  ==  ""
sonido   9  ==  "Pim"
sonido  15  ==  "PimPam"
sonido  21  ==  "PimPum"
sonido  35  ==  "PamPum"
sonido 105  ==  "PimPamPum"

Actualización de «Elementos de una matriz con algún vecino menor»

Actualización

He actualizado las soluciones del ejercicio Elementos de una matriz con algún vecino menor cuyo enunciado es

Las matrices puede representarse mediante tablas cuyos índices son pares de números naturales. Su tipo se define por

type Matriz = Array (Int,Int) Int

Por ejemplo, la matriz

|9 4 6 5|
|8 1 7 3|
|4 2 5 4|

se define por

ej :: Matriz
ej = listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,4,2,5,4]

Los vecinos de un elemento son los que están a un paso en la misma fila, columna o diagonal. Por ejemplo, en la matriz anterior, el 1 tiene 8 vecinos (el 9, 4, 6, 8, 7, 4, 2 y 5) pero el 9 sólo tiene 3 vecinos (el 4, 8 y 1).

Definir la función

algunoMenor :: Matriz -> [Int]

tal que (algunoMenor p) es la lista de los elementos de p que tienen algún vecino menor que él. Por ejemplo,

algunoMenor ej == [9,4,6,5,8,7,4,2,5,4]

pues sólo el 1 y el 3 no tienen ningún vecino menor en la matriz.

Actualización de «Enumeración de árboles binarios»

Actualización

He actualizado las soluciones del ejercicio Enumeración de árboles binarios cuyo enunciado es

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

data Arbol a = H a
             | N (Arbol a) a (Arbol a)
   deriving Show

Por ejemplo, el árbol

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

se puede definir por

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

Definir la función

enumeraArbol :: Arbol t -> Arbol Int

tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,

λ> enumeraArbol ej1
N (N (H 0) 1 (H 2)) 3 (N (H 4) 5 (H 6))

Gráficamente,

      3
     / \
    /   \
   /     \
  1       5
 / \     / \
0   2   4   6

Actualización de «Biparticiones de una lista»

Actualización

He actualizado las soluciones del ejercicio Biparticiones de una lista cuyo enunciado es

Definir la función

biparticiones :: [a] -> [([a],[a])]

tal que (biparticiones xs) es la lista de pares formados por un prefijo de xs y el resto de xs. Por ejemplo,

λ> biparticiones [3,2,5]
[([],[3,2,5]),([3],[2,5]),([3,2],[5]),([3,2,5],[])]
λ> biparticiones "Roma"
[("","Roma"),("R","oma"),("Ro","ma"),("Rom","a"),("Roma","")]

Actualización de «Mayor producto de las ramas de un árbol»

Actualización

He actualizado las soluciones del ejercicio Mayor producto de las ramas de un árbol cuyo enunciado es

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
  deriving Show

Por ejemplo, los árboles

  1              3
 / \            /|\
2   3          / | \
    |         5  4  7
    4         |     /\
              6    2  1

se representan por

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]

Definir la función

mayorProducto :: (Ord a, Num a) => Arbol a -> a

tal que (mayorProducto a) es el mayor producto de las ramas del árbol a. Por ejemplo,

λ> mayorProducto (N 1 [N 2 [], N  3 []])
3
λ> mayorProducto (N 1 [N 8 [], N  4 [N 3 []]])
12
λ> mayorProducto (N 1 [N 2 [],N 3 [N 4 []]])
12
λ> mayorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
90
λ> mayorProducto (N (-8) [N 0 [N (-9) []],N 6 []])
0
λ> a = N (-4) [N (-7) [],N 14 [N 19 []],N (-1) [N (-6) [],N 21 []],N (-4) []]
λ> mayorProducto a
84

Actualización de «Número de pares de elementos adyacentes iguales en una matriz»

Actualización

He actualizado las soluciones del ejercicio Número de pares de elementos adyacentes iguales en una matriz cuyo enunciado es

Una matriz se puede representar mediante una lista de listas. Por ejemplo, la matriz

|2 1 5|
|4 3 7|

se puede representar mediante la lista

[[2,1,5],[4,3,7]]

Definir la función

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

tal que (numeroParesAdyacentesIguales xss) es el número de pares de elementos consecutivos (en la misma fila o columna) iguales de la matriz xss. Por ejemplo,

numeroParesAdyacentesIguales [[0,1],[0,2]]              ==  1
numeroParesAdyacentesIguales [[0,0],[1,2]]              ==  1
numeroParesAdyacentesIguales [[0,1],[0,0]]              ==  2
numeroParesAdyacentesIguales [[1,2],[1,4],[4,4]]        ==  3
numeroParesAdyacentesIguales ["ab","aa"]                ==  2
numeroParesAdyacentesIguales [[0,0,0],[0,0,0],[0,0,0]]  ==  12
numeroParesAdyacentesIguales [[0,0,0],[0,1,0],[0,0,0]]  ==  8

Actualización de «Elemento más repetido de manera consecutiva»

Actualización

He actualizado las soluciones del ejercicio Elemento más repetido de manera consecutiva cuyo enunciado es

Definir la función

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

tal que (masRepetido xs) es el elemento de xs que aparece más veces de manera consecutiva en la lista junto con el número de sus apariciones consecutivas; en caso de empate, se devuelve el mayor de dichos elementos. Por ejemplo,

masRepetido [1,1,4,4,1]  ==  (4,2)
masRepetido [4,4,1,1,5]  ==  (4,2)
masRepetido "aadda"      ==  ('d',2)
masRepetido "ddaab"      ==  ('d',2)
masRepetido (show (product [1..5*10^4]))  ==  ('0',12499)

Actualización de «Regiones determinadas por n rectas del plano»

Actualización

He actualizado las soluciones del ejercicio Regiones determinadas por n rectas del plano cuyo enunciado es

En los siguientes dibujos se observa que el número máximo de regiones en el plano generadas con 1, 2 ó 3 líneas son 2, 4 ó 7, respectivamente.

                   \  |
                    \5|
                     \|
                      \
                      |\
                      | \
            |         |  \
 1        1 | 3     1 | 3 \  6
------   ---|---   ---|----\---
 2        2 | 4     2 | 4   \ 7
            |         |      \

Definir la función

regiones :: Integer -> Integer

tal que (regiones n) es el número máximo de regiones en el plano generadas con n líneas. Por ejemplo,

regiones 1     ==  2
regiones 2     ==  4
regiones 3     ==  7
regiones 100   ==  5051
regiones 1000  ==  500501
regiones 10000 ==  50005001
length (show (regiones (10^(10^5)))) ==  200000
length (show (regiones (10^(10^6)))) ==  2000000
length (show (regiones (10^(10^7)))) ==  20000000

Actualización de «Ampliación de matrices por columnas»

Actualización

He actualizado las soluciones del ejercicio Ampliación de matrices por columnas cuyo enunciado es

Las matrices enteras se pueden representar mediante tablas con índices enteros:

type Matriz = Array (Int,Int) Int

Definir la función

ampliaColumnas :: Matriz -> Matriz -> Matriz

tal que (ampliaColumnas p q) es la matriz construida añadiendo las columnas de la matriz q a continuación de las de p (se supone que tienen el mismo número de filas). Por ejemplo, si p y q representa las dos primeras matrices, entonces (ampliaColumnas p q) es la tercera

|0 1|    |4 5 6|    |0 1 4 5 6|
|2 3|    |7 8 9|    |2 3 7 8 9|

En Haskell, se definen las dos primeras matrices se definen por

ej1 = listArray ((1,1),(2,2)) [0..3]
ej2 = listArray ((1,1),(2,3)) [4..9]

y el cálculo de la tercera es

λ> ampliaColumnas ej1 ej2
array ((1,1),(2,5)) [((1,1),0),((1,2),1),((1,3),4),((1,4),5),((1,5),6),
                     ((2,1),2),((2,2),3),((2,3),7),((2,4),8),((2,5),9)]
λ> elems (ampliaColumnas ej1 ej2)
[0,1,4,5,6,2,3,7,8,9]

Actualización de «Trenzado de listas»

Actualización

He actualizado las soluciones del ejercicio Trenzado de listas cuyo enunciado es

Definir la función

trenza :: [a] -> [a] -> [a]

tal que (trenza xs ys) es la lista obtenida intercalando los elementos de xs e ys. Por ejemplo,

trenza [5,1] [2,7,4]             ==  [5,2,1,7]
trenza [5,1,7] [2..]             ==  [5,2,1,3,7,4]
trenza [2..] [5,1,7]             ==  [2,5,3,1,4,7]
take 8 (trenza [2,4..] [1,5..])  ==  [2,1,4,5,6,9,8,13]

Actualización de «Emparejamiento binario»

Actualización

He actualizado las soluciones del ejercicio Emparejamiento binario cuyo enunciado es

Definir la función

zipBinario :: [a -> b -> c] -> [a] -> [b] -> [c]

tal que (zipBinario fs xs ys) es la lista obtenida aplicando cada una de las operaciones binarias de fs a los correspondientes elementos de xs e ys. Por ejemplo,

zipBinario [(+), (*), (*)] [2,2,2] [4,4,4]    == [6,8,8]
zipBinario [(+)] [2,2,2] [4,4,4]              == [6]
zipBinario [(<), (==), (==)] "coloca" "lobo"  == [True,True,False]

Actualización de «Ordenación de estructuras»

Actualización

He actualizado las soluciones del ejercicio Ordenación de estructuras cuyo enunciado es

Las notas de los dos primeros exámenes se pueden representar mediante el siguiente tipo de dato

data Notas = Notas String Int Int
  deriving (Read, Show, Eq)

Por ejemplo, (Notas "Juan" 6 5) representar las notas de un alumno cuyo nombre es Juan, la nota del primer examen es 6 y la del segundo es 5.

Definir la función

ordenadas :: [Notas] -> [Notas]

tal que (ordenadas ns) es la lista de las notas ns ordenadas considerando primero la nota del examen 2, a continuación la del examen 1 y finalmente el nombre. Por ejemplo,

λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 3 7]
[Notas "Juan" 6 5,Notas "Luis" 3 7]
λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 3 4]
[Notas "Luis" 3 4,Notas "Juan" 6 5]
λ> ordenadas [Notas "Juan" 6 5, Notas "Luis" 7 4]
[Notas "Luis" 7 4,Notas "Juan" 6 5]
λ> ordenadas [Notas "Juan" 6 4, Notas "Luis" 7 4]
[Notas "Juan" 6 4,Notas "Luis" 7 4]
λ> ordenadas [Notas "Juan" 6 4, Notas "Luis" 5 4]
[Notas "Luis" 5 4,Notas "Juan" 6 4]
λ> ordenadas [Notas "Juan" 5 4, Notas "Luis" 5 4]
[Notas "Juan" 5 4,Notas "Luis" 5 4]
λ> ordenadas [Notas "Juan" 5 4, Notas "Eva" 5 4]
[Notas "Eva" 5 4,Notas "Juan" 5 4]

Actualización de «Numeración de las ternas de números naturales»

Actualización

He actualizado las soluciones del ejercicio Numeración de las ternas de números naturales cuyo enunciado es

Las ternas de números naturales se pueden ordenar como sigue

(0,0,0),
(0,0,1),(0,1,0),(1,0,0),
(0,0,2),(0,1,1),(0,2,0),(1,0,1),(1,1,0),(2,0,0),
(0,0,3),(0,1,2),(0,2,1),(0,3,0),(1,0,2),(1,1,1),(1,2,0),(2,0,1),...
...

Definir la función

posicion :: (Int,Int,Int) -> Int

tal que posicion (x,y,z) es la posición de la terna de números naturales (x,y,z) en la ordenación anterior. Por ejemplo,

posicion (0,1,0)  ==  2
posicion (0,0,2)  ==  4
posicion (0,1,1)  ==  5

Comprobar con QuickCheck que

  • la posición de (x,0,0) es x(x²+6x+11)/6
  • la posición de (0,y,0) es y(y²+3y+ 8)/6
  • la posición de (0,0,z) es z(z²+3z+ 2)/6
  • la posición de (x,x,x) es x(9x²+14x+7)/2

Actualización de «Alfabeto comenzando en un carácter»

Actualización

He actualizado las soluciones del ejercicio Alfabeto comenzando en un carácter cuyo enunciado es

Definir la función

alfabetoDesde :: Char -> String

tal que (alfabetoDesde c) es el alfabeto, en minúscula, comenzando en el carácter c, si c es una letra minúscula y comenzando en 'a', en caso contrario. Por ejemplo,

alfabetoDesde 'e'  ==  "efghijklmnopqrstuvwxyzabcd"
alfabetoDesde 'a'  ==  "abcdefghijklmnopqrstuvwxyz"
alfabetoDesde '7'  ==  "abcdefghijklmnopqrstuvwxyz"
alfabetoDesde '{'  ==  "abcdefghijklmnopqrstuvwxyz"
alfabetoDesde 'B'  ==  "abcdefghijklmnopqrstuvwxyz"

Actualización de «Números triangulares con n cifras distintas»

Actualización

He actualizado las soluciones del ejercicio Números triangulares con n cifras distintas cuyo enunciado es

Los números triangulares se forman como sigue

*     *      *
     * *    * *
           * * *
1     3      6

La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

Definir la función

triangularesConCifras :: Int -> [Integer]

tal que triangularesConCifras n es la lista de los números triangulares con n cifras distintas. Por ejemplo,

take 6 (triangularesConCifras 1)   ==  [1,3,6,55,66,666]
take 6 (triangularesConCifras 2)   ==  [10,15,21,28,36,45]
take 6 (triangularesConCifras 3)   ==  [105,120,136,153,190,210]
take 5 (triangularesConCifras 4)   ==  [1035,1275,1326,1378,1485]
take 2 (triangularesConCifras 10)  ==  [1062489753,1239845706]

Actualización de «Ramas de un árbol»

Actualización

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

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
  deriving Show

Por ejemplo, los árboles

  1               3
 / \             /|\
2   3           / | \
    |          5  4  7
    4          |     /\
               6    2  1

se representan por

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]

Definir la función

ramas :: Arbol b -> [[b]]

tal que (ramas a) es la lista de las ramas del árbol a. Por ejemplo,

ramas ej1  ==  [[1,2],[1,3,4]]
ramas ej2  ==  [[3,5,6],[3,4],[3,7,2],[3,7,1]]

Actualización de «Valores de polinomios representados con vectores»

Actualización

He actualizado las soluciones del ejercicio Valores de polinomios representados con vectores cuyo enunciado es

Los polinomios se pueden representar mediante vectores usando la librería Data.Array. En primer lugar, se define el tipo de los polinomios (con coeficientes de tipo a) mediante

type Polinomio a = Array Int a

Como ejemplos, definimos el polinomio

ej_pol1 :: Array Int Int
ej_pol1 = array (0,4) [(1,2),(2,-5),(4,7),(0,6),(3,0)]

que representa a \(2x - 5x^2 + 7x^4 + 6\) y el polinomio

ej_pol2 :: Array Int Double
ej_pol2 = array (0,4) [(1,2),(2,-5.2),(4,7),(0,6.5),(3,0)]

que representa a \(2x - 5.2x^2 + 7x^4 + 6.5\).

Definir la función

valor :: Num a => Polinomio a -> a -> a

tal que (valor p b) es el valor del polinomio p en el punto b. Por ejemplo,

valor ej_pol1 0  ==  6
valor ej_pol1 1  ==  10
valor ej_pol1 2  ==  102
valor ej_pol2 0  ==  6.5
valor ej_pol2 1  ==  10.3
valor ej_pol2 3  ==  532.7

Actualización de «Segmentos maximales con elementos consecutivos»

Actualización

He actualizado las soluciones del ejercicio Segmentos maximales con elementos consecutivos cuyo enunciado es

Definir la función

segmentos :: (Enum a, Eq a) => [a] -> [[a]]

tal que (segmentos xss) es la lista de los segmentos de xss formados por elementos consecutivos. Por ejemplo,

segmentos [1,2,5,6,4]     ==  [[1,2],[5,6],[4]]
segmentos [1,2,3,4,7,8,9] ==  [[1,2,3,4],[7,8,9]]
segmentos "abbccddeeebc"  ==  ["ab","bc","cd","de","e","e","bc"]

Actualización de «Lista cuadrada»

Actualización

He actualizado las soluciones del ejercicio Lista cuadrada cuyo enunciado es

Definir la función

listaCuadrada :: Int -> a -> [a] -> [[a]]

tal que (listaCuadrada n x xs) es una lista de n listas de longitud n formadas con los elementos de xs completada con x, si no xs no tiene suficientes elementos. Por ejemplo,

listaCuadrada 3 7 [0,3,5,2,4]  ==  [[0,3,5],[2,4,7],[7,7,7]]
listaCuadrada 3 7 [0..]        ==  [[0,1,2],[3,4,5],[6,7,8]]
listaCuadrada 2 'p' "eva"      ==  ["ev","ap"]
listaCuadrada 2 'p' ['a'..]    ==  ["ab","cd"]

Actualización de «Máximos locales»

Actualización

He actualizado las soluciones del ejercicio Máximos locales cuyo enunciado es

Un máximo local de una lista es un elemento de la lista que es que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).

Definir la función

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

tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,

maximosLocales [3,2,5,3,7,7,1,6,2]  ==  [5,6]
maximosLocales [1..100]             ==  []
maximosLocales "adbpmqexyz"         ==  "dpq"

Actualización de «Matrices de Toepliz»

Actualización

He actualizado las soluciones del ejercicio Matrices de Toepliz cuyo enunciado es

Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,

|2 5 1 6|       |2 5 1 6|
|4 2 5 1|       |4 2 6 1|
|7 4 2 5|       |7 4 2 5|
|9 7 4 2|       |9 7 4 2|

la primera es una matriz de Toeplitz y la segunda no lo es.

Las anteriores matrices se pueden definir por

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2]
ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]

Definir la función

esToeplitz :: Eq a => Array (Int,Int) a -> Bool

tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por ejemplo,

esToeplitz ej1  ==  True
esToeplitz ej2  ==  False

Actualización de «Suma si todos los valores son justos»

Actualización

He actualizado las soluciones del ejercicio Suma si todos los valores son justos cuyo enunciado es

Definir la función

sumaSiTodosJustos :: (Num a, Eq a) => [Maybe a] -> Maybe a

tal que (sumaSiTodosJustos xs) es justo la suma de todos los elementos de xs si todos son justos (es decir, si Nothing no pertenece a xs) y Nothing en caso contrario. Por ejemplo,

sumaSiTodosJustos [Just 2, Just 5]           == Just 7
sumaSiTodosJustos [Just 2, Just 5, Nothing]  == Nothing

Actualización de «Primos equidistantes»

Actualización

He actualizado las soluciones del ejercicio Primos equidistantes cuyo enunciado es

Definir la función

primosEquidistantes :: Integer -> [(Integer,Integer)]

tal que (primosEquidistantes k) es la lista de los pares de primos cuya diferencia es k. Por ejemplo,

take 3 (primosEquidistantes 2)  ==  [(3,5),(5,7),(11,13)]
take 3 (primosEquidistantes 4)  ==  [(7,11),(13,17),(19,23)]
take 3 (primosEquidistantes 6)  ==  [(23,29),(31,37),(47,53)]
take 3 (primosEquidistantes 8)  ==  [(89,97),(359,367),(389,397)]

Actualización de «Anagramas»

Actualización

He actualizado las soluciones del ejercicio Anagramas cuyo enunciado es

Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, mora y roma son anagramas de amor.

Definir la función

anagramas :: String -> [String] -> [String]

tal que (anagramas x ys) es la lista de los elementos de ys que son anagramas de x. Por ejemplo,

λ> anagramas "amor" ["Roma","mola","loma","moRa", "rama"]
["Roma","moRa"]
λ> anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"]
["aMar","aRma"]

Actualización de «Primos consecutivos con media capicúa»

Actualización

He actualizado las soluciones del ejercicio Primos consecutivos con media capicúa cuyo enunciado es

Definir la función

primosConsecutivosConMediaCapicua :: [(Int,Int,Int)]

formada por las ternas (x,y,z) tales que x e y son primos consecutivos cuya media, z, es capicúa. Por ejemplo,

λ> take 5 primosConsecutivosConMediaCapicua
[(3,5,4),(5,7,6),(7,11,9),(97,101,99),(109,113,111)]

Calcular cuántos hay anteriores a 2014.

Actualización de «Mastermind»

Actualización

He actualizado las soluciones del ejercicio Mastermind cuyo enunciado es

El Mastermind es un juego que consiste en deducir un numérico formado por una lista de números distintos. Cada vez que se empieza una partida, el programa debe elegir un código, que será lo que el jugador debe adivinar en la menor cantidad de intentos posibles. Cada intento consiste en una propuesta de un código posible que propone el jugador, y una respuesta del programa. Las respuestas le darán pistas al jugador para que pueda deducir el código.

Estas pistas indican cuán cerca estuvo el número propuesto de solución a través de dos valores: la cantidad de aciertos es la cantidad de dígitos que propuso el jugador que también están en el código en la misma posición. La cantidad de coincidencias es la cantidad de digitos que propuso el jugador que también están en el código pero en una posición distinta.

Por ejemplo, si el código que eligió el programa es el [2,6,0,7], el jugador propone el [1,4,0,6], el programa le debe responder acierto (el 0, que está en el código original en el mismo lugar, tercero), y una coincidencia (el 6, que también está en el original, pero en la segunda posición, no en el cuarto como fue propuesto). Si el jugador hubiera propuesto el [3,5,9,1], habría obtenido como respuesta ningún acierto y ninguna coincidencia, ya que no hay números en común con el código original, y si se obtienen cuatro aciertos es porque el jugador adivinó el código y ganó el juego.

Definir la función

mastermind :: [Int] -> [Int] -> (Int,Int)

tal que (mastermind xs ys) es el par formado por los números de aciertos y de coincidencias entre xs e ys. Por ejemplo,

mastermind [2,6,0,7] [1,4,0,6]  ==  (1,1)
mastermind [2,6,0,7] [3,5,9,1]  ==  (0,0)
mastermind [2,6,0,7] [1,6,0,4]  ==  (2,0)
mastermind [2,6,0,7] [2,6,0,7]  ==  (4,0)

Actualización de «Determinación de los elementos minimales»

Actualización

He actualizado las soluciones del ejercicio Determinación de los elementos minimales cuyo enunciado es

Definir la función

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

tal que (minimales xss) es la lista de los elementos de xss que no están contenidos en otros elementos de xss. Por ejemplo,

minimales [[1,3],[2,3,1],[3,2,5]]        ==  [[2,3,1],[3,2,5]]
minimales [[1,3],[2,3,1],[3,2,5],[3,1]]  ==  [[2,3,1],[3,2,5]]

Actualización de «La bandera tricolor»

Actualización

He actualizado las soluciones del ejercicio La bandera tricolor cuyo enunciado es

El problema de la bandera tricolor consiste en lo siguiente: Dada un lista de objetos xs que pueden ser rojos, amarillos o morados, se pide devolver una lista ys que contiene los elementos de xs, primero los rojos, luego los amarillos y por último los morados.

Definir el tipo de dato Color para representar los colores con los constructores R, A y M correspondientes al rojo, azul y morado y la función

banderaTricolor :: [Color] -> [Color]

tal que (banderaTricolor xs) es la bandera tricolor formada con los elementos de xs. Por ejemplo,

bandera [M,R,A,A,R,R,A,M,M]  ==  [R,R,R,A,A,A,M,M,M]
bandera [M,R,A,R,R,A]        ==  [R,R,R,A,A,M]

Actualizaciones de ejercicios

Actualización

He iniciado el proceso de actualización de los ejercicios de programación funcional con Haskell publicados con el fin de que, además del enunciado y sus soluciones, incorporen los siguientes elementos:

  • la verificación mediante Hspec,
  • la comprobación de la equivalencia de las soluciones utilizando QuickCheck, y
  • el análisis comparativo de la eficiencia de las distintas soluciones.

Asimismo, los ejercicios se irán integrando en el proyecto Exercitium en GitHub, desarrollado con stack, con el propósito de asegurar la compatibilidad con las versiones de Haskell y de las bibliotecas empleadas.

Iré anunciando las actualizaciones a través de este blog y de mis cuentas en Bluesky, Mastodon y Twitter.

Duplicación de cada elemento

Misceláneas

Definir la función

duplicaElementos :: [a] -> [a]

tal que (duplicaElementos xs) es la lista obtenida duplicando cada elemento de xs. Por ejemplo,

duplicaElementos [3,2,5]    ==  [3,3,2,2,5,5]
duplicaElementos "Haskell"  ==  "HHaasskkeellll"

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Sistema factorádico de numeración

Misceláneas

El sistema factorádico es un sistema numérico basado en factoriales en el que el n-ésimo dígito, empezando desde la derecha, debe ser multiplicado por n! Por ejemplo, el número "341010" en el sistema factorádico es 463 en el sistema decimal ya que

3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! = 463

En este sistema numérico, el dígito de más a la derecha es siempre 0, el segundo 0 o 1, el tercero 0,1 o 2 y así sucesivamente.

Con los dígitos del 0 al 9 el mayor número que podemos codificar es el 10!-1 = 3628799. En cambio, si lo ampliamos con las letras A a Z podemos codificar hasta 36!-1 = 37199332678990121746799944815083519999999910.

Definir las funciones

factoradicoAdecimal :: String -> Integer
decimalAfactoradico :: Integer -> String

tales que

  • (factoradicoAdecimal cs) es el número decimal correspondiente al número factorádico cs. Por ejemplo,
λ> factoradicoAdecimal "341010"
463
λ> factoradicoAdecimal "2441000"
2022
λ> factoradicoAdecimal "A0000000000"
36288000
λ> map factoradicoAdecimal ["10","100","110","200","210","1000","1010","1100","1110","1200"]
[1,2,3,4,5,6,7,8,9,10]
λ> factoradicoAdecimal "3KXWVUTSRQPONMLKJIHGFEDCBA9876543210"
37199332678990121746799944815083519999999
  • (decimalAfactoradico n) es el número factorádico correpondiente al número decimal n. Por ejemplo,
λ> decimalAfactoradico 463
"341010"
λ> decimalAfactoradico 2022
"2441000"
λ> decimalAfactoradico 36288000
"A0000000000"
λ> map decimalAfactoradico [1..10]
["10","100","110","200","210","1000","1010","1100","1110","1200"]
λ> decimalAfactoradico 37199332678990121746799944815083519999999
"3KXWVUTSRQPONMLKJIHGFEDCBA9876543210"

Comprobar con QuickCheck que, para cualquier entero positivo n,

factoradicoAdecimal (decimalAfactoradico n) == n

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Suma de cadenas

Misceláneas

Definir la función

sumaCadenas :: String -> String -> String

tal que (sumaCadenas xs ys) es la cadena formada por el número entero que es la suma de los números enteros cuyas cadenas que lo representan son xs e ys; además, se supone que la cadena vacía representa al cero. Por ejemplo,

sumaCadenas "2"   "6"  == "8"
sumaCadenas "14"  "2"  == "16"
sumaCadenas "14"  "-5" == "9"
sumaCadenas "-14" "-5" == "-19"
sumaCadenas "5"   "-5" == "0"
sumaCadenas ""    "5"  == "5"
sumaCadenas "6"   ""   == "6"
sumaCadenas ""    ""   == "0"

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Cuadrado más cercano

Misceláneas

Definir la función

cuadradoCercano :: Integer -> Integer

tal que (cuadradoCercano n) es el número cuadrado más cercano a n, donde n es un entero positivo. Por ejemplo,

cuadradoCercano 2       == 1
cuadradoCercano 6       == 4
cuadradoCercano 8       == 9
cuadradoCercano (10^46) == 10000000000000000000000000000000000000000000000

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Órbita prima

Misceláneas

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

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.

Leer más…

Ordenada cíclicamente

Misceláneas

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.

Leer más…

Eliminación de las ocurrencias aisladas

Misceláneas

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"

Leer más…

Emparejamiento de árboles

Misceláneas

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
  deriving (Show, Eq)

Por ejemplo, los árboles

  1               3
 / \             /|\
6   3           / | \
    |          5  4  7
    5          |     /\
               6    2  1

se representan por

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 6 [],N 3 [N 5 []]]
ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]

Definir la función

emparejaArboles :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c

tal que (emparejaArboles f a1 a2) es el árbol obtenido aplicando la función f a los elementos de los árboles a1 y a2 que se encuentran en la misma posición. Por ejemplo,

λ> emparejaArboles (+) (N 1 [N 2 [], N 3[]]) (N 1 [N 6 []])
N 2 [N 8 []]
λ> emparejaArboles (+) ej1 ej2
N 4 [N 11 [],N 7 []]
λ> emparejaArboles (+) ej1 ej1
N 2 [N 12 [],N 6 [N 10 []]]

Leer más…

Separación por posición

Misceláneas

Definir la función

particion :: [a] -> ([a],[a])

tal que (particion xs) es el par cuya primera componente son los elementos de xs en posiciones pares y su segunda componente son los restantes elementos. Por ejemplo,

particion [3,5,6,2]    ==  ([3,6],[5,2])
particion [3,5,6,2,7]  ==  ([3,6,7],[5,2])
particion "particion"  ==  ("priin","atco")

Leer más…

Número de inversiones

Misceláneas

Se dice que en una sucesión de números x(1), x(2), ..., x(n) hay una inversión cuando existe un par de números x(i) > x(j), siendo i < j. Por ejemplo, en la permutación 2, 1, 4, 3 hay dos inversiones (2 antes que 1 y 4 antes que 3) y en la permutación 4, 3, 1, 2 hay cinco inversiones (4 antes 3, 4 antes 1, 4 antes 2, 3 antes 1, 3 antes 2).

Definir la función

numeroInversiones :: Ord a => [a] -> Int

tal que (numeroInversiones xs) es el número de inversiones de xs. Por ejemplo,

numeroInversiones [2,1,4,3]  ==  2
numeroInversiones [4,3,1,2]  ==  5

Leer más…

Descomposiciones triangulares

Teoría de números

Los números triangulares se forman como sigue

*     *      *
     * *    * *
           * * *
1     3      6

La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

Definir la función

descomposicionesTriangulares :: Int -> [(Int, Int, Int)]

tal que descomposicionesTriangulares n es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos, como máximo, formados por números triangulares. Por ejemplo,

λ> descomposicionesTriangulares3 4
[]
λ> descomposicionesTriangulares3 5
[(1,1,3)]
λ> descomposicionesTriangulares3 12
[(1,1,10),(3,3,6)]
λ> descomposicionesTriangulares3 30
[(1,1,28),(3,6,21),(10,10,10)]
λ> descomposicionesTriangulares3 61
[(1,15,45),(3,3,55),(6,10,45),(10,15,36)]
λ> descomposicionesTriangulares3 52
[(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)]
λ> descomposicionesTriangulares3 82
[(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]
λ> length (descomposicionesTriangulares3 (5*10^5))
124

Leer más…

Índices de valores verdaderos

Misceláneas

Definir la función

indicesVerdaderos :: [Int] -> [Bool]

tal que (indicesVerdaderos xs) es la lista infinita de booleanos tal que sólo son verdaderos los elementos cuyos índices pertenecen a la lista estrictamente creciente xs. Por ejemplo,

λ> take 6 (indicesVerdaderos [1,4])
[False,True,False,False,True,False]
λ> take 6 (indicesVerdaderos [0,2..])
[True,False,True,False,True,False]
λ> take 3 (indicesVerdaderos [])
[False,False,False]
λ> take 6 (indicesVerdaderos [1..])
[False,True,True,True,True,True]
λ> last (take (8*10^7) (indicesVerdaderos [0,5..]))
False

Leer más…

Código de las alergias

Misceláneas

Para la determinación de las alergia se utiliza los siguientes códigos para los alérgenos:

Huevos ........   1
Cacahuetes ....   2
Mariscos ......   4
Fresas ........   8
Tomates .......  16
Chocolate .....  32
Polen .........  64
Gatos ......... 128

Así, si Juan es alérgico a los cacahuetes y al chocolate, su puntuación es 34 (es decir, 2+32).

Los alérgenos se representan mediante el siguiente tipo de dato

data Alergeno = Huevos
              | Cacahuetes
              | Mariscos
              | Fresas
              | Tomates
              | Chocolate
              | Polen
              | Gatos
  deriving (Enum, Eq, Show, Bounded)

Definir la función

alergias :: Int -> [Alergeno]

tal que (alergias n) es la lista de alergias correspondiente a una puntuación n. Por ejemplo,

λ> alergias 1
[Huevos]
λ> alergias 2
[Cacahuetes]
λ> alergias 3
[Huevos,Cacahuetes]
λ> alergias 5
[Huevos,Mariscos]
λ> alergias 255
[Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos]

Leer más…

Lista cuadrada

Misceláneas

Definir la función

listaCuadrada :: Int -> a -> [a] -> [[a]]

tal que (listaCuadrada n x xs) es una lista de n listas de longitud n formadas con los elementos de xs completada con x, si no xs no tiene suficientes elementos. Por ejemplo,

listaCuadrada 3 7 [0,3,5,2,4]  ==  [[0,3,5],[2,4,7],[7,7,7]]
listaCuadrada 3 7 [0..]        ==  [[0,1,2],[3,4,5],[6,7,8]]
listaCuadrada 2 'p' "eva"      ==  ["ev","ap"]
listaCuadrada 2 'p' ['a'..]    ==  ["ab","cd"]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Máximos locales

Misceláneas

Un máximo local de una lista es un elemento de la lista que es que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).

Definir la función

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

tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,

maximosLocales [3,2,5,3,7,7,1,6,2]  ==  [5,6]
maximosLocales [1..100]             ==  []
maximosLocales "adbpmqexyz"         ==  "dpq"

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Matrices de Toepliz

Misceláneas

Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,

|2 5 1 6|       |2 5 1 6|
|4 2 5 1|       |4 2 6 1|
|7 4 2 5|       |7 4 2 5|
|9 7 4 2|       |9 7 4 2|

la primera es una matriz de Toeplitz y la segunda no lo es.

Las anteriores matrices se pueden definir por

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2]
ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]

Definir la función

esToeplitz :: Eq a => Array (Int,Int) a -> Bool

tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por ejemplo,

esToeplitz ej1  ==  True
esToeplitz ej2  ==  False

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Primos equidistantes

Misceláneas

Definir la función

primosEquidistantes :: Integer -> [(Integer,Integer)]

tal que (primosEquidistantes k) es la lista de los pares de primos cuya diferencia es k. Por ejemplo,

take 3 (primosEquidistantes 2)  ==  [(3,5),(5,7),(11,13)]
take 3 (primosEquidistantes 4)  ==  [(7,11),(13,17),(19,23)]
take 3 (primosEquidistantes 6)  ==  [(23,29),(31,37),(47,53)]
take 3 (primosEquidistantes 8)  ==  [(89,97),(359,367),(389,397)]
primosEquidistantes 4 !! (10^5) ==  (18467047,18467051)

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Anagramas

Misceláneas

Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, "mora" y "roma" son anagramas de "amor".

Definir la función

anagramas :: String -> [String] -> [String]

tal que (anagramas x ys) es la lista de los elementos de ys que son anagramas de x. Por ejemplo,

λ> anagramas "amor" ["Roma","mola","loma","moRa", "rama"]
["Roma","moRa"]
λ> anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"]
["aMar","aRma"]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Diagonales principales

Misceláneas

La lista de las diagonales principales de la matriz

1  2  3  4
5  6  7  8
9 10 11 12

es

[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

Definir la función

diagonalesPrincipales :: Array (Int,Int) a -> [[a]]

tal que (diagonalesPrincipales p) es la lista de las diagonales principales de p. Por ejemplo,

λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12])
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Posiciones de las diagonales principales

Misceláneas

Las posiciones de una matriz con 3 filas y 4 columnas son

(1,1) (1,2) (1,3) (1,4)
(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)

Las posiciones de sus 6 diagonales principales son

[(3,1)]
[(2,1),(3,2)]
[(1,1),(2,2),(3,3)]
[(1,2),(2,3),(3,4)]
[(1,3),(2,4)]
[(1,4)]

Definir la función

posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]]

tal que (posicionesdiagonalesprincipales m n) es la lista de las posiciones de las diagonales principales de una matriz con m filas y n columnas. Por ejemplo,

λ> mapM_ print (posicionesDiagonalesPrincipales 3 4)
[(3,1)]
[(2,1),(3,2)]
[(1,1),(2,2),(3,3)]
[(1,2),(2,3),(3,4)]
[(1,3),(2,4)]
[(1,4)]
λ> mapM_ print (posicionesDiagonalesPrincipales 4 4)
[(4,1)]
[(3,1),(4,2)]
[(2,1),(3,2),(4,3)]
[(1,1),(2,2),(3,3),(4,4)]
[(1,2),(2,3),(3,4)]
[(1,3),(2,4)]
[(1,4)]
λ> mapM_ print (posicionesDiagonalesPrincipales 4 3)
[(4,1)]
[(3,1),(4,2)]
[(2,1),(3,2),(4,3)]
[(1,1),(2,2),(3,3)]
[(1,2),(2,3)]
[(1,3)]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

La bandera tricolor

Misceláneas

El problema de la bandera tricolor consiste en lo siguiente: Dada un lista de objetos xs que pueden ser rojos, amarillos o morados, se pide devolver una lista que contiene los elementos de xs, primero los rojos, luego los amarillos y por último los morados.

Definir el tipo de dato Color para representar los colores con los constructores R, A y M correspondientes al rojo, azul y morado y la función

banderaTricolor :: [Color] -> [Color]

tal que (banderaTricolor xs) es la bandera tricolor formada con los elementos de xs. Por ejemplo,

banderaTricolor [M,R,A,A,R,R,A,M,M]  ==  [R,R,R,A,A,A,M,M,M]
banderaTricolor [M,R,A,R,R,A]        ==  [R,R,R,A,A,M]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Ordenación por el máximo

Misceláneas

Definir la función

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

tal que (ordenadosPorMaximo xss) es la lista de los elementos de xss ordenada por sus máximos (se supone que los elementos de xss son listas no vacía) y cuando tiene el mismo máximo se conserva el orden original. Por ejemplo,

λ> ordenadosPorMaximo [[0,8],[9],[8,1],[6,3],[8,2],[6,1],[6,2]]
[[6,3],[6,1],[6,2],[0,8],[8,1],[8,2],[9]]
λ> ordenadosPorMaximo ["este","es","el","primero"]
["el","primero","es","este"]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Leer más…

Iguales al siguiente

Misceláneas

Definir la función

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

tal que (igualesAlSiguiente xs) es la lista de los elementos de xs que son iguales a su siguiente. Por ejemplo,

igualesAlSiguiente [1,2,2,2,3,3,4]  ==  [2,2,3]
igualesAlSiguiente [1..10]          ==  []

Nota: Escribir las soluciones en Haskell y en Python.

Leer más…

Primos consecutivos con media capicúa

Misceláneas

Definir la list

primosConsecutivosConMediaCapicua :: [(Int,Int,Int)]

formada por las ternas (x,y,z) tales que x e y son primos consecutivos cuya media, z, es capicúa. Por ejemplo,

λ> take 5 primosConsecutivosConMediaCapicua
[(3,5,4),(5,7,6),(7,11,9),(97,101,99),(109,113,111)]
λ> primosConsecutivosConMediaCapicua !! 500
(5687863,5687867,5687865)

Nota: Escribir las soluciones en Haskell y en Python.

Leer más…

Mastermind

Misceláneas

El Mastermind es un juego que consiste en deducir un código numérico formado por una lista de números. Cada vez que se una partida, el programa debe elegir un código, que será lo que el jugador debe adivinar en la menor cantidad de intentos posibles. Cada intento consiste en una propuesta de un código posible que propone el jugador, y una respuesta del programa. Las respuestas le darán pistas al jugador para que pueda deducir el código.

Estas pistas indican lo cerca que estuvo el número propuesto de la solución a través de dos valores: la cantidad de aciertos es la cantidad de dígitos que propuso el jugador que también están en el código en la misma posición. La cantidad de coincidencias es la cantidad de dígitos que propuso el jugador que también están en el código pero en una posición distinta.

Por ejemplo, si el código que eligió el programa es el [2,6,0,7] y el jugador propone el [1,4,0,6], el programa le debe responder un acierto (el 0, que está en el código original en el mismo lugar, el tercero), y una coincidencia (el 6, que también está en el código original, pero en la segunda posición, no en el cuarto como fue propuesto). Si el jugador hubiera propuesto el [3,5,9,1], habría obtenido como respuesta ningún acierto y ninguna coincidencia, ya que no hay números en común con el código original. Si se obtienen cuatro aciertos es porque el jugador adivinó el código y ganó el juego.

Definir la función

mastermind :: [Int] -> [Int] -> (Int,Int)

tal que (mastermind xs ys) es el par formado por los números de aciertos y de coincidencias entre xs e ys. Por ejemplo,

mastermind [3,3] [3,2]          ==  (1,0)
mastermind [3,5,3] [3,2,5]      ==  (1,1)
mastermind [3,5,3,2] [3,2,5,3]  ==  (1,3)
mastermind [3,5,3,3] [3,2,5,3]  ==  (2,1)
mastermind [1..10^6] [1..10^6]  ==  (1000000,0)

Nota: Escribir las soluciones en Haskell y en Python.

Leer más…

Determinación de los elementos minimales

Misceláneas

Definir la función

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

tal que (minimales xss) es la lista de los elementos de xss que no están contenidos en otros elementos de xss. Por ejemplo,

minimales [[1,3],[2,3,1],[3,2,5]]        ==  [[2,3,1],[3,2,5]]
minimales [[1,3],[2,3,1],[3,2,5],[3,1]]  ==  [[2,3,1],[3,2,5]]
map sum (minimales [[1..n] | n <- [1..300]])  ==  [45150]

Nota: Escribir las soluciones en Haskell y en Python.

Leer más…

Suma de los números amigos menores que n

Misceláneas

Dos números amigos son dos números enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.

Definir la función

sumaAmigosMenores :: Integer -> Integer

tal que (sumaAmigosMenores n) es la suma de los números amigos menores que n. Por ejemplo,

sumaAmigosMenores 2000   == 2898
sumaAmigosMenores (10^5) == 852810

Leer más…

Sucesión de números amigos

Misceláneas

Dos números amigos son dos números enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.

Definir la lista

sucesionAmigos :: [(Integer,Integer)]

cuyos elementos son los pares de números amigos con la primera componente menor que la segunda. Por ejemplo,

take 4 sucesionAmigos == [(220,284),(1184,1210),(2620,2924),(5020,5564)]
sucesionAmigos6 !! 20 == (185368,203432)

Leer más…

Números amigos

Misceláneas

Dos números amigos son dos números enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.

Definir la función

amigos :: Integer -> Integer -> Bool

tal que (amigos x y) se verifica si los números x e y son amigos. Por ejemplo,

amigos 220 284 == True
amigos 220 23  == False
amigos 42262694537514864075544955198125 42405817271188606697466971841875 == True

Leer más…

Máxima suma de caminos en un triángulo

Misceláneas

Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo

   3
  7 4
 2 4 6
8 5 9 3

se representa por

[[3],[7,4],[2,4,6],[8,5,9,3]]

Definir la función

maximaSuma :: [[Integer]] -> Integer

tal que (maximaSuma xss) es el máximo de las sumas de los elementos de los caminos en el triángulo xss donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,

maximaSuma [[3],[7,4]]                    ==  10
maximaSuma [[3],[7,4],[2,4,6]]            ==  14
maximaSuma [[3],[7,4],[2,4,6],[8,5,9,3]]  ==  23
maximaSuma [[n..n+n] | n <- [0..100]]     ==  10100
maximaSuma [[n..n+n] | n <- [0..1000]]    ==  1001000
maximaSuma [[n..n+n] | n <- [0..2000]]    ==  4002000
maximaSuma [[n..n+n] | n <- [0..3000]]    ==  9003000
maximaSuma [[n..n+n] | n <- [0..4000]]    ==  16004000

Leer más…

Caminos en un triángulo

Misceláneas

Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo

      3
     7 4
    2 4 6
   8 5 9 3

se representa por

[[3],[7,4],[2,4,6],[8,5,9,3]]

Definir la función

caminos :: [[a]] -> [[a]]

tal que (caminos xss) es la lista de los caminos en el triángulo xss donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,

λ> caminos [[3],[7,4]]
[[3,7],[3,4]]
λ> caminos [[3],[7,4],[2,4,6]]
[[3,7,2],[3,7,4],[3,4,4],[3,4,6]]
λ> caminos [[3],[7,4],[2,4,6],[8,5,9,3]]
[[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],[3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]

Leer más…

Mayor órbita de la sucesión de Collatz

Misceláneas

Se considera la siguiente operación, aplicable a cualquier número entero positivo:

  • Si el número es par, se divide entre 2.
  • Si el número es impar, se multiplica por 3 y se suma 1.

Dado un número cualquiera, podemos calcular su órbita; es decir, las imágenes sucesivas al iterar la función. Por ejemplo, la órbita de 13 es

   13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...

Si observamos este ejemplo, la órbita de 13 es periódica, es decir, se repite indefinidamente a partir de un momento dado). La conjetura de Collatz dice que siempre alcanzaremos el 1 para cualquier número con el que comencemos. Ejemplos:

  • Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.
  • Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
  • Empezando en n = 27, la sucesión tiene 112 pasos, llegando hasta 9232 antes de descender a 1: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Definir la función

   mayoresGeneradores :: Integer -> [Integer]

tal que (mayoresGeneradores n) es la lista de los números menores o iguales que n cuyas órbitas de Collatz son las de mayor longitud. Por ejemplo,

   mayoresGeneradores 20      ==  [18,19]
   mayoresGeneradores (10^6)  ==  [837799]

Leer más…

Ternas pitagóricas con suma dada

Misceláneas

Una terna pitagórica es una terna de números naturales \((a,b,c)\) tal que \(a<b<c\) y \(a^2+b^2=c^2\). Por ejemplo (3,4,5) es una terna pitagórica.

Definir la función

ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]

tal que (ternasPitagoricas x) es la lista de las ternas pitagóricas cuya suma es x. Por ejemplo,

ternasPitagoricas 12     == [(3,4,5)]
ternasPitagoricas 60     == [(10,24,26),(15,20,25)]
ternasPitagoricas (10^6) == [(218750,360000,421250),(200000,375000,425000)]

Leer más…

Suma de múltiplos de 3 o de 5

Misceláneas

Los números naturales menores que 10 que son múltiplos de 3 ó 5 son 3, 5, 6 y 9. La suma de estos múltiplos es 23.

Definir la función

sumaMultiplos :: Integer -> Integer

tal que (sumaMultiplos n) es la suma de todos los múltiplos de 3 ó 5 menores que n. Por ejemplo,

sumaMultiplos 10      ==  23
sumaMultiplos (10^2)  ==  2318
sumaMultiplos (10^3)  ==  233168
sumaMultiplos (10^4)  ==  23331668
sumaMultiplos (10^5)  ==  2333316668
sumaMultiplos (10^6)  ==  233333166668
sumaMultiplos (10^7)  ==  23333331666668

Leer más…

Sumas de dos abundantes

Misceláneas

Un número n es abundante si la suma de divisores propios de n es mayor que n. El primer número abundante es el 12 (cuyos divisores propios son 1, 2, 3, 4 y 6 cuya suma es 16). Por tanto, el menor número que es la suma de dos números abundantes es el 24.

Definir la sucesión

   sumasDeDosAbundantes :: [Integer]

cuyos elementos son los números que se pueden escribir como suma de dos números abundantes. Por ejemplo,

   take 10 sumasDeDosAbundantes  ==  [24,30,32,36,38,40,42,44,48,50]

Leer más…

Número de divisores

Misceláneas

Definir la función

   numeroDivisores :: Integer -> Integer

tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,

   numeroDivisores 12  ==  6
   numeroDivisores 25  ==  3
   length (show (numeroDivisores (product [1..3*10^4])))  ==  1948

Leer más…

Conjunto de divisores

Misceláneas

Definir la función

   divisores :: Integer -> [Integer]

tal que (divisores x) es el conjunto de divisores de los x. Por ejemplo,

  divisores 30  ==  [1,2,3,5,6,10,15,30]
  length (divisores (product [1..10]))  ==  270
  length (divisores (product [1..25]))  ==  340032

Leer más…

Reconocimiento de potencias de 2

Misceláneas

Definir la función

   esPotenciaDeDos :: Integer -> Bool

tal que esPotenciaDeDos n se verifica si n es una potencia de dos (suponiendo que n es mayor que 0). Por ejemplo.

   esPotenciaDeDos    1        == True
   esPotenciaDeDos    2        == True
   esPotenciaDeDos    6        == False
   esPotenciaDeDos    8        == True
   esPotenciaDeDos 1024        == True
   esPotenciaDeDos 1026        == False
   esPotenciaDeDos (2^(10^8))  == True

Leer más…

Particiones de enteros positivos

Misceláneas

Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.

Definir la función

   particiones :: Int -> [[Int]]

tal que particiones n es la lista de las particiones del número n. Por ejemplo,

   particiones 4  ==  [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
   particiones 5  ==  [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
   length (particiones 50)  ==  204226

Leer más…

Mínimo producto escalar

Misceláneas

El producto escalar de los vectores \([a_1,a_2,...,a_n]\) y \([b_1,b_2,..., b_n]\) es \[ a_1·b_1 + a_2·b_2 + ··· + a_n·b_n \]

Definir la función

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

tal que (menorProductoEscalar xs ys) es el mínimo de los productos escalares de las permutaciones de xs y de las permutaciones de ys. Por ejemplo,

   menorProductoEscalar [3,2,5]  [1,4,6]    == 29
   menorProductoEscalar [3,2,5]  [1,4,-6]   == -19
   menorProductoEscalar [1..10^2] [1..10^2] == 171700
   menorProductoEscalar [1..10^3] [1..10^3] == 167167000
   menorProductoEscalar [1..10^4] [1..10^4] == 166716670000
   menorProductoEscalar [1..10^5] [1..10^5] == 166671666700000
   menorProductoEscalar [1..10^6] [1..10^6] == 166667166667000000

Leer más…