Ir al contenido principal

Sustitución de pares de elementos consecutivos iguales

Misceláneas

Dada una lista xs se reemplaza el primer par de elementos consecutivos iguales x por x+1 y se repite el proceso con las listas obtenidas hasta que no haya ningún par de elementos consecutivos iguales. Por ejemplo, para [5,2,1,1,2,2] se tiene el siguiente proceso

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

Definir la función

sustitucion :: [Int] -> [Int]

tal que (sustitucion xs) es la lista obtenida aplicándole a xs el proceso anterior. Por ejemplo,

sustitucion [5,2,1,1,2,2]         ==  [5,4]
sustitucion [4,2,1,1,2,2]         ==  [5]
sustitucion [4,5,11,2,5,7,2]      ==  [4,5,11,2,5,7,2]
sustitucion (1:[1..2*10^6])       ==  [2000001]
length (sustitucion [1..2*10^6])  ==  2000000

Leer más…

Problema del dominó

Misceláneas

Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.

Definir la función

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

tal que (domino fs) es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,

λ> domino [(1,2),(2,3),(1,4)]
[[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]
λ> domino [(1,2),(1,1),(1,4)]
[[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]
λ> domino [(1,2),(3,4),(2,3)]
[[(1,2),(2,3),(3,4)]]
λ> domino [(1,2),(2,3),(5,4)]
[]
λ> domino [(x,y) | x <- [1..2], y <- [x..2]]
[[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]]
λ> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
λ> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]])
[(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)]
[(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)]
[(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)]
[(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)]
[(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)]
[(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)]
[(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)]
[(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)]
[(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)]
λ> length (domino [(x,y) | x <- [1..3], y <- [x..3]])
9
λ> length (domino [(x,y) | x <- [1..4], y <- [x..4]])
0
λ> length (domino [(x,y) | x <- [1..5], y <- [x..5]])
84480

Leer más…

El problema de las celebridades

Misceláneas

La celebridad de una reunión es una persona al que todos conocen pero que no conoce a nadie. Por ejemplo, si en la reunión hay tres personas tales que la 1 conoce a la 3 y la 2 conoce a la 1 y a la 3, entonces la celebridad de la reunión es la 3.

La relación de conocimiento se puede representar mediante una lista de pares (x,y) indicando que x conoce a y. Por ejemplo, la reunión anterior se puede representar por [(1,3),(2,1),(2,3)].

Definir la función

celebridad :: Ord a => [(a,a)] -> Maybe a

tal que (celebridad r) es el justo la celebridad de r, si en r hay una celebridad y Nothing, en caso contrario. Por ejemplo,

celebridad [(1,3),(2,1),(2,3)]            ==  Just 3
celebridad [(1,3),(2,1),(3,2)]            ==  Nothing
celebridad [(1,3),(2,1),(2,3),(3,1)]      ==  Nothing
celebridad [(x,1) | x <- [2..10^6]]       ==  Just 1
celebridad [(x,10^6) | x <- [1..10^6-1]]  ==  Just 1000000

Leer más…

Grafo de divisibilidad

Misceláneas

El grafo de divisibilidad de orden n es el grafo cuyos nodos son los números naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x. El coste de cada arista es el cociente entre su mayor y menor elemento.

Definir las siguientes funciones:

grafoDivisibilidad :: Int -> Grafo Int Int
coste              :: Int -> Int

tales que

  • (grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,
λ> grafoDivisibilidad 12
G ND (array (1,12)
            [(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),
                 (8,8),(9,9),(10,10),(11,11),(12,12)]),
             (2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),
             (3,[(1,3),(6,2),(9,3),(12,4)]),
             (4,[(1,4),(2,2),(8,2),(12,3)]),
             (5,[(1,5),(10,2)]),
             (6,[(1,6),(2,3),(3,2),(12,2)]),
             (7,[(1,7)]),
             (8,[(1,8),(2,4),(4,2)]),
             (9,[(1,9),(3,3)]),
             (10,[(1,10),(2,5),(5,2)]),
             (11,[(1,11)]),
             (12,[(1,12),(2,6),(3,4),(4,3),(6,2)])])
  • (coste n) es el coste del árbol de expansión mínimo del grafo de divisibilidad de orden n. Por ejemplo,
coste 12        ==  41
coste 3000      ==  605305
coste (2*10^5)  ==  1711798835

Leer más…

Sucesión de Recamán

Misceláneas

La sucesión de Recamán está definida como sigue:

a(0) = 0
a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión
a(n) = a(n-1) + n, en caso contrario.

Definir las funciones

sucRecaman :: [Int]
invRecaman :: Int -> Int
graficaSucRecaman :: Int -> IO ()
graficaInvRecaman :: Int -> IO ()

tales que

  • sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,
λ> take 25 sucRecaman3
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]
λ> sucRecaman !! 1000
3686
λ> sucRecaman !! 1000001
1057163
  • (invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,
invRecaman 10       ==  12
invRecaman 3686     ==  1000
invRecaman 1057163  ==  1000001
  • (graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja

Sucesión de Recamán

  • (graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja

Sucesión de Recamán

y (graficaInvRecaman 100) dibuja

Sucesión de Recamán

Leer más…

Problema de las jarras

Misceláneas

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en alguna de las dos jarras.

Definir la función

jarras :: (Int,Int,Int) -> Maybe [(Int,Int)]

tal (jarras (a,b,c)) es una solución del problema de las jarras (a,b,c) con el mínimo número de movimientos, si el problema tiene solución y Nothing, en caso contrario. Por ejemplo,

λ> jarras (5,3,4)
Just [(0,0),(5,0),(2,3),(2,0),(0,2),(5,2),(4,3)]

La interpretación de la solución anterior es

(0,0) se inicia con las dos jarras vacías,
(5,0) se llena la jarra de 5 con el grifo,
(2,3) se llena la de 3 con la de 5,
(2,0) se vacía la de 3,
(0,2) se pasa el contenido de la primera a la segunda,
(5,2) se llena la primera con el grifo,
(4,3) se llena la segunda con la primera.

Otros ejemplos:

λ> jarras (3,5,4)
Just [(0,0),(0,5),(3,2),(0,2),(2,0),(2,5),(3,4)]
λ> jarras (15,10,5)
Just [(0,0),(15,0),(5,10)]
λ> jarras (15,10,4)
Nothing
λ> length <$> jarras (181,179,100)
Just 199

Leer más…

Mayor número de atracciones

Misceláneas

En el siguiente gráfico se representa en una cuadrícula el plano de Manhattan. Cada línea es una opción a seguir; el número representa las atracciones que se pueden visitar si se elige esa opción.

     3         2         4         0
* ------- * ------- * ------- * ------- *
|         |         |         |         |
|1        |0        |2        |4        |3
|    3    |    2    |    4    |    2    |
* ------- * ------- * ------- * ------- *
|         |         |         |         |
|4        |6        |5        |2        |1
|    0    |    7    |    3    |    4    |
* ------- * ------- * ------- * ------- *
|         |         |         |         |
|4        |4        |5        |2        |1
|    3    |    3    |    0    |    2    |
* ------- * ------- * ------- * ------- *
|         |         |         |         |
|5        |6        |8        |5        |3
|    1    |    3    |    2    |    2    |
* ------- * ------- * ------- * ------- *

El turista entra por el extremo superior izquierda y sale por el extremo inferior derecha. Sólo puede moverse en las direcciones Sur y Este (es decir, hacia abajo o hacia la derecha).

Representamos el mapa mediante una matriz p tal que p(i,j) = (a,b), donde a = nº de atracciones si se va hacia el sur y b = nº de atracciones si se va al este. Además, ponemos un 0 en el valor del número de atracciones por un camino que no se puede elegir. De esta forma, el mapa anterior se representa por la matriz siguiente:

( (1,3)   (0,2)   (2,4)   (4,0)  (3,0) )
( (4,3)   (6,2)   (5,4)   (2,2)  (1,0) )
( (4,0)   (4,7)   (5,3)   (2,4)  (1,0) )
( (5,3)   (6,3)   (8,0)   (5,2)  (3,0) )
( (0,1)   (0,3)   (0,2)   (0,2)  (0,0) )

En este caso, si se hace el recorrido

[S, E, S, E, S, S, E, E],

el número de atracciones es

1  3  6  7  5  8  2  2

cuya suma es 34.

Definir la función

mayorNumeroV:: M.Matrix (Int,Int) -> Int

tal que (mayorNumeroV p) es el máximo número de atracciones que se pueden visitar en el plano representado por la matriz p. Por ejemplo, si se define la matriz anterior por

ejMapa :: M.Matrix (Int,Int)
ejMapa = M.fromLists [[(1,3),(0,2),(2,4),(4,0),(3,0)],
                      [(4,3),(6,2),(5,4),(2,2),(1,0)],
                      [(4,0),(4,7),(5,3),(2,4),(1,0)],
                      [(5,3),(6,3),(8,0),(5,2),(3,0)],
                      [(0,1),(0,3),(0,2),(0,2),(0,0)]]

entonces

mayorNumeroV ejMapa                                     ==  34
mayorNumeroV (fromLists [[(1,3),(0,0)],[(0,3),(0,0)]])  ==  4
mayorNumeroV (fromLists [[(1,3),(6,0)],[(0,3),(0,0)]])  ==  9

Para los siguientes ejemplos se define un generador de mapas

genMapa :: Int -> Matrix (Int,Int)
genMapa n =
extendTo (0,0) n n (fromList (n-1) (n-1) [(k,k+1) | k <- [1..]])

Entonces,

mayorNumeroV (genMapa 10)  ==  962
mayorNumeroV (genMapa 500)  ==  185880992

Leer más…

Números construidos con los dígitos de un conjunto dado

Misceláneas

Definir las siguientes funciones

numerosCon      :: [Integer] -> [Integer]
numeroDeDigitos :: [Integer] -> Int -> Int

tales que

  • (numerosCon ds) es la lista de los números que se pueden construir con los dígitos de ds (cuyos elementos son distintos elementos del 1 al 9) . Por ejemplo,
λ> take 22 (numerosCon [1,4,6,9])
[1,4,6,9,11,14,16,19,41,44,46,49,61,64,66,69,91,94,96,99,111,114]
λ> take 15 (numerosCon [4,6,9])
[4,6,9,44,46,49,64,66,69,94,96,99,444,446,449]
λ> take 15 (numerosCon [6,9])
[6,9,66,69,96,99,666,669,696,699,966,969,996,999,6666]
  • (numeroDeDigitos ds k) es el número de dígitos que tiene el k-ésimo elemento (empezando a contar en 0) de la sucesión (numerosCon ds). Por ejemplo,
numeroDeDigitos [1,4,6,9]   3  ==  1
numeroDeDigitos [1,4,6,9]   6  ==  2
numeroDeDigitos [1,4,6,9]  22  ==  3
numeroDeDigitos [4,6,9]    15  ==  3
numeroDeDigitos [6,9]      15  ==  4
numeroDeDigitos [1,4,6,9] (10^(10^5))  ==  166097
numeroDeDigitos   [4,6,9] (10^(10^5))  ==  209590
numeroDeDigitos     [6,9] (10^(10^5))  ==  332192

Leer más…

Número de triangulaciones de un polígono

Misceláneas

Una triangulación de un polígono es una división del área en un conjunto de triángulos, de forma que la unión de todos ellos es igual al polígono original, y cualquier par de triángulos es disjunto o comparte únicamente un vértice o un lado. En el caso de polígonos convexos, la cantidad de triangulaciones posibles depende únicamente del número de vértices del polígono.

Si llamamos T(n) al número de triangulaciones de un polígono de n vértices, se verifica la siguiente relación de recurrencia:

T(2) = 1
T(n) = T(2)*T(n-1) + T(3)*T(n-2) + ... + T(n-1)*T(2)

Definir la función

numeroTriangulaciones :: Integer -> Integer

tal que (numeroTriangulaciones n) es el número de triangulaciones de un polígono convexo de n vértices. Por ejemplo,

numeroTriangulaciones 3  == 1
numeroTriangulaciones 5  == 5
numeroTriangulaciones 6  == 14
numeroTriangulaciones 7  == 42
numeroTriangulaciones 50 == 131327898242169365477991900
length (show (numeroTriangulaciones   800)) ==  476
length (show (numeroTriangulaciones  1000)) ==  597
length (show (numeroTriangulaciones 10000)) == 6014

Leer más…

Sucesiones suaves

Misceláneas

Una sucesión es suave si valor absoluto de la diferencia de sus términos consecutivos es 1.

Definir la función

suaves :: Int -> [[Int]]

tal que (suaves n) es la lista de las sucesiones suaves de longitud n cuyo último término es 0. Por ejemplo,

suaves 2  ==  [[1,0],[-1,0]]
suaves 3  ==  [[2,1,0],[0,1,0],[0,-1,0],[-2,-1,0]]

Leer más…