Un conjunto de números enteros se pueden representar mediante una lista ordenada de intervalos tales que la diferencia entre el menor elemento de un intervalo y el mayor elemento de su intervalo anterior es mayor que uno.

Por ejemplo, el conjunto {2, 7, 4, 3, 9, 6} se puede representar mediante la lista de intervalos [(2,4),(6,7),(9,9)] de forma que en el primer intervalo se agrupan los números 2, 3 y 4; en el segundo, los números 6 y 7 y el tercero, el número 9.

Definir la función

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

tal que (intervalos xs) es lista ordenada de intervalos que representa al conjunto xs. Por ejemplo,

intervalos [2,7,4,3,9,6]  ==  [(2,4),(6,7),(9,9)]

Nota: Este ejercicio está basado en el problema Bus numbers de Kattis

Leer más…

El procedimiento de codificación matricial se puede entender siguiendo la codificación del mensaje "todoparanada" como se muestra a continuación:

• Se calcula la longitud L del mensaje. En el ejemplo es L es 12.
• Se calcula el menor entero positivo N cuyo cuadrado es mayor o igual que L. En el ejemplo N es 4.
• Se extiende el mensaje con N²-L puntos. En el ejemplo, el mensaje extendido es "todoparanada····"
• Con el mensaje extendido se forma una matriz cuadrada NxN. En el ejemplo la matriz es

| t o d o |
| p a r a |
| n a d a |
| · · · · |

• Se rota 90º la matriz del mensaje extendido. En el ejemplo, la matriz rotada es

| · n p t |
| · a a o |
| · d r d |
| · a a o |

• Se calculan los elementos de la matriz rotada. En el ejemplo, los elementos son "·npt·aap·drd·aao"
• El mensaje codificado se obtiene eliminando los puntos de los elementos de la matriz rotada. En el ejemplo, "nptaapdrdaao".

Definir la función

codificado :: String -> String

tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,

codificado "todoparanada"    ==  "nptaaodrdaao"
codificado "nptaaodrdaao"    ==  "danaopadtora"
codificado "danaopadtora"    ==  "todoparanada"
codificado "entodolamedida"  ==  "dmdeaeondltiao"

Nota: Este ejercicio está basado en el problema Secret Message de Kattis.

Leer más…

Definir la función

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

tal que (reducida 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 sólo el primer elemento. Por ejemplo,

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

Nota: Basado en el ejercicio Apaxiaaaaaaaaaaaans! de Kattis.

Leer más…

Los subconjuntos de [1, 4, 2] son

[], [1], [4], [1, 4], [2], [1, 2], [4, 2], [1, 4, 2]

Las sumas de sus elementos son

0, 1, 4, 5, 2, 3, 6, 7

Y la suma de las sumas es 28.

Definir la función

sumaSubconjuntos :: [Integer] -> Integer

tal que (sumaSubconjuntos xs) es la suma de las sumas de los subconjuntos de xs. Por ejemplo,

sumaSubconjuntos [1,2]                     == 6
sumaSubconjuntos [1,4,2]                   == 28
length (show (sumaSubconjuntos [1..10^6])) == 301042

Leer más…

El enunciado del problema Por 3 o más 5 de ¡Acepta el reto! es el siguiente

Cuenta la leyenda que un famoso matemático, tras aprender a sumar y multiplicar a la tierna edad de 3 años en apenas 5 días, se dio cuenta de que, empezando por 1, podía generar un montón de números sin más que multiplicar por 3 o sumar 5 a alguno de los que ya hubiera generado antes.

Por ejemplo, el 23 (edad a la que se casaría) lo obtuvo así: ((1 + 5) × 3) + 5 Por su parte el 77 (edad a la que tendría su primer bisnieto) lo consiguió: (((1 × 3 + 5) × 3) × 3) + 5

Por mucho que lo intentó, algunos números, sin embargo, resultaron ser imposibles de obtener, como por ejemplo el 5, el 7 o el 15.

Se dice que un número es generable si se puede escribir como una sucesión (quizá vacía) de multiplicaciones por 3 y sumas de 5 al número 1.

Definir las siguientes funciones

generables     :: [Integer]
generable      :: Integer -> Bool
arbolGenerable :: Integer -> Tree Integer

tales que

• generables es la sucesión de los números generables. Por ejemplo,

λ> take 20 generables
[1,3,6,8,9,11,13,14,16,18,19,21,23,24,26,27,28,29,31,32]
λ> generables !! (10^6)
1250008

• (generable x) se verifica si x es generable. Por ejemplo,

generable 23       ==  True
generable 77       ==  True
generable 15       ==  False
generable 1250008  ==  True
generable 1250010  ==  False

• (arbolGenerable x) es el árbol de los números generables menores o iguales a x. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbolGenerable 11)))
1
|
+- 3
|  |
|  +- 9
|  |
|  `- 8
|
`- 6
   |
   `- 11

Leer más…

El enunciado del problema Números cubifinitos de ¡Acepta el reto! es el siguiente

Se dice que un número es cubifinito cuando al elevar todos sus dígitos al cubo y sumarlos el resultado o bien es 1 o bien es un número cubifinito.

Por ejemplo, el número 1243 es cubifinito, pues al elevar todos sus dígitos al cubo obtenemos 100 que es cubifinito.

Por su parte, el 513 no es cubifinito, pues al elevar al cubo sus dígitos conseguimos el 153 que nunca podrá ser cubifinito, pues la suma de los cubos de sus dígitos vuelve a dar 153.

Definir las funciones

esCubifinito :: Int -> Bool
grafica :: Int -> IO ()

tales que

• (esCubifinito n) se verifica si n es un número cubifinito. Por ejemplo,

esCubifinito 1      ==  True
esCubifinito 10     ==  True
esCubifinito 1243   ==  True
esCubifinito 87418  ==  True
esCubifinito 513    ==  False

• (grafica n) dibuja la gráfica de la sucesión de los primeros n números cubifinitos. Por ejemplo, al evaluar (grafica 50) se dibuja

Leer más…

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

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

Las diferencias de sus elementos consecutivos es

2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

y la distribución de sus frecuencias en el intervalo [-9,9] es

0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

distribucionDDCpi :: Int -> [Int]
graficas :: [Int] -> FilePath -> IO ()

tales que

• (distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,

λ> distribucionDDCpi 18
[0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]
λ> distribucionDDCpi 100
[1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]
λ> distribucionDDCpi 200
[3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]
λ> distribucionDDCpi 1000
[16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]
λ> distribucionDDCpi 5000
[67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

• (graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] "distribucionDDCpi.png" se escribe en el fichero "distribucionDDCpi.png" la siguiente gráfica

Nota: Se puede usar la librería Data.Number.CReal.

Leer más…

Los números de Catalan forman la sucesión cuyo término general es

Los primeros números de Catalan son

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786

Los números de Catalan satisfacen la siguiente relación de recurrencia:

Asintóticamente, los números de Catalan crecen como:

considerando que el cociente entre el n-ésimo número de Catalan y la expresión de la derecha tiende hacia 1 cuando n tiende a infinito.

Definir las funciones

catalan :: [Integer]
grafica :: Int -> Int -> IO ()

tales que

• catalan es la lista de términos de la sucesión de Catalan. Por ejemplo,

λ> take 12 catalan
[1,1,2,5,14,42,132,429,1430,4862,16796,58786]
λ> length (show (catalan !! 50000))
30096

• (grafica a b) dibuja los n-ésimos términos de la sucesión de Catalan, para n entre a y b, junto con los de la expresión de la derecha de

Por ejemplo, (grafica 5 10) dibuja

y (grafica 55 60) dibuja

Leer más…

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

λ> putStrLn (drawTree (fmap show ej))
3
|
+- 5
|  |
|  `- 9
|
`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

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

Definir las siguientes funciones

mayoresDivisores :: Int -> [Int]
arbol            :: Int -> Tree Int
caminos          :: Int -> [[Int]]
caminosMinimales :: Int -> [[Int]]

tales que

• (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

mayoresDivisores 24  ==  [12,8,6]
mayoresDivisores 16  ==  [8,4]
mayoresDivisores 10  ==  [5]
mayoresDivisores 17  ==  []

• (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbol 6)))
6
|
+- 5
|  |
|  `- 4
|     |
|     +- 3
|     |  |
|     |  `- 2
|     |     |
|     |     `- 1
|     |
|     `- 2
|        |
|        `- 1
|
`- 3
   |
   `- 2
      |
      `- 1

• (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

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

• (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

λ> caminosMinimales 6
[[6,3,2,1]]
λ> caminosMinimales 17
[[17,16,4,2,1]]
λ> caminosMinimales 50
[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Leer más…

Los números de Gabonacci generados por (a,b) son los elementos de la sucesión de Gabonacci definida por

G(0) = a
G(1) = b
G(n) = G(n-2) + G(n-1), si n > 1

Por ejemplo, la sucesión de Gabonacci generada por (2,5) es 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, ...

Un número pertenece a distintas sucesiones de Gabonacci. Por ejemplo, el 9 pertenece a las sucesiones de Gabonacci generados por (3,3), (1,4) y (4,5).

El menor generador de Gabonacci de un número x es el par (a,b), con 1 ≤ a ≤ b, tal que (a,b) es un generador de Gabonacci de x y no existe ningún generador de Gabonacci de x (a',b') tal que b' < b ó b' = b y a' < a. Por ejemplo, el menor generador de Gabonacci de 9 es (3,3).

Definir la función

menorGenerador :: Integer -> (Integer,Integer)

tal que (menorGenerador x) es el menor generador de Gabonacci de x. Por ejemplo,

menorGenerador 9          ==  (3,3)
menorGenerador 7          ==  (1,3)
menorGenerador 5          ==  (1,1)
menorGenerador 27         ==  (3,7)
menorGenerador 57         ==  (4,9)
menorGenerador 218        ==  (10,21)
menorGenerador 1121       ==  (20,41)
menorGenerador 89         ==  (1,1)
menorGenerador 123        ==  (1,3)
menorGenerador 1000       ==  (2,10)
menorGenerador 842831057  ==  (2,7)
menorGenerador 1573655    ==  (985,1971)

Leer más…