Ir al contenido principal

Eliminación de las ocurrencias aisladas

(actualizado )

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

(actualizado )

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…

Número de inversiones

(actualizado )

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

(actualizado )

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,

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

Leer más…

Índices de valores verdaderos

(actualizado )

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

(actualizado )

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…

Pim, Pam, Pum y divisibilidad

(actualizado )

Misceláneas

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"

Leer más…

Elementos de una matriz con algún vecino menor

(actualizado )

Misceláneas

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.

Leer más…