Ir al contenido principal

Filtro booleano

(actualizado )

Misceláneas

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]

Leer más…

Mayor sucesión del problema 3n+1

(actualizado )

Misceláneas

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

Leer más…

Buscaminas

(actualizado )

Misceláneas

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 )

Leer más…

Selección hasta el primero que falla inclusive

(actualizado )

Misceláneas

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]

Leer más…

Descomposiciones como sumas de n sumandos

(actualizado )

Misceláneas

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

Leer más…

Órbita prima

(actualizado )

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

Leer más…

Ordenada cíclicamente

(actualizado )

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

(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…

Enumeración de árboles binarios

(actualizado )

Misceláneas

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

Leer más…

Números triangulares con n cifras distintas

(actualizado )

Misceláneas

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]

Leer más…

Mayor producto de las ramas de un árbol

(actualizado )

Misceláneas

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

Leer más…

Número de pares de elementos adyacentes iguales en una matriz

(actualizado )

Misceláneas

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

Leer más…

Elemento más repetido de manera consecutiva

(actualizado )

Misceláneas

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)

Leer más…

Regiones determinadas por n rectas del plano

(actualizado )

Misceláneas

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

Leer más…

Ampliación de matrices por columnas

(actualizado )

Misceláneas

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]

Leer más…

Emparejamiento binario

(actualizado )

Misceláneas

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]

Leer más…

Ordenación de estructuras

(actualizado )

Misceláneas

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]

Leer más…

Numeración de las ternas de números naturales

(actualizado )

Misceláneas

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

Leer más…

Alfabeto comenzando en un carácter

(actualizado )

Misceláneas

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"

Leer más…

Ramas de un árbol

(actualizado )

Misceláneas

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

Leer más…

Valores de polinomios representados con vectores

(actualizado )

Misceláneas

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

Leer más…

Lista cuadrada

(actualizado )

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

Leer más…

Máximos locales

(actualizado )

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"

Leer más…

Matrices de Toepliz

(actualizado )

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

Leer más…

Primos equidistantes

(actualizado )

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

Leer más…

29-Anagramas

(actualizado )

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

Leer más…

Mastermind

(actualizado )

Misceláneas

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)

Leer más…

La bandera tricolor

(actualizado )

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

Leer más…

Ejercicios del curso 2013-14

Misceláneas

Como se comenta en la presentación del blog, su objetivo es complementar el curso de Informática proponiendo un ejercicio diario teniendo en cuenta lo que se ha estudiado hasta ese momento.

Para situar los ejercicios en su contexto se debe de tener presente

  • la página del curso en la que se encuentra los temas, las relaciones de ejercicios y los exámenes;
  • el diario de clases en la que se resume el contenido de cada clase.

El cronograma de las clases es el siguiente, donde los temas se representan con T y las relaciones de problemas con R. Por ejemplo,

  • T2 representa que se ha estudiado el tema 2.
  • R1 representa que se ha estudiado la relación 1.
  • T4[1,14] representa que se ha estudiado el tema 4 desde la transparencia 1 a la 24.
  • R2[9,12] representa que se ha estudiado la relación 2 desde la el ejercicio 9 al 12.
Día Contenido
M-24-Sep-13 T2: Introducción a la programación con Haskell.
V-27-Sep-13 R1: Definiciones por composición con aritmética.
M-01-Oct-13 R2[1,8]: Definiciones por composición con listas.
  T4[1,14]: Definiciones de funciones.
V-04-Oct-13 R2[9,12]: Definiciones por composición con listas.
  R3[1,5]: Definiciones con condicionales.
M-08-Oct-13 T5[1,13]: Definiciones por comprensión.
  R3[6,19]: Definiciones con condicionales.
11-Oct-13 R4[1,7]: Definiciones por comprensión.
15-Oct-13 R4[8,14]: Definiciones por comprensión.
  Introducción a las gráficas con gnuplot.
18-Oct-13 R4[15,19]: Definiciones por comprensión.
22-Oct-13 T5[14,29]: Código César.
25-Oct-13 R4[20,21]: Definiciones por comprensión.
  R5[1,7]: Definiciones por comprensión.
29-Oct-13 T3: Tipos y clases.
05-Nov-13 Examen 1
08-Nov-13 R5[8,14.1]: Definiciones por comprensión.
12-Nov-13 T6[1,10]: Definiciones por recursión.
19-Nov-13 T6[11,24]: Definiciones por comprensión.
22-Nov-13 R7+R8[1,3]: Definiciones por recursión.
26-Nov-13 R9: Ordenación por mezclas y QuickCheck.
29-Nov-13 R8[4,8]: Definiciones por recursión.
  R10[1,5.3]: Definiciones por comprensión y recursión.
03-Dic-13 R10[6,17]: Definiciones por comprensión y recursión.
  R11[1,5]: Definiciones por comprensión y recursión.
10-Dic-13 T7[1,23]: Funciones de orden superior.
13-Dic-13 R12[1,5]: Funciones de orden superior.
17-Dic-13 Examen 2
20-Dic-13 R12[6,11]: Funciones de orden superior.
07-Ene-14 T10: Evaluación perezosa.
  T7[23,27]: Cambio de base.
10-Ene-14 R13: Funciones de orden superior (2).
  R14: Funciones sobre cadenas.
14-Ene-14 T7[28,36]: Codificación binaria y transmisión de cadenas.
  R15[1,3.2]: Evaluación perezosa y listas infinitas (1).
17-Ene-14 R15[4,7.5]: Evaluación perezosa y listas infinitas (2).
  R16[1,4.2]: Evaluación perezosa y listas infinitas (3).
-Ene-14 Examen 3
11-Feb-14 T9[1,26]: Declaraciones de tipos y clases.
15-Feb-14 R17[1,2.5]: Evaluación perezosa y listas infinitas.
18-Feb-14 T11: Aplicaciones de la programación funcional.
22-Feb-14 R18+R19[1,6]: Tipos de datos algebraicos.
25-Feb-14 R20: Cálculo numérico.
  R19[7,10]: Árboles binarios.
  R17[3,3]: Triángulo de Pascal.
04-Mar-14 T21[1,41]: El TAD de los polinomios.
07-Mar-14 R22: Combinatoria.
11-Mar-14 T21[41,55]: Operaciones con polinomios.
  R17[6.1,6.13]: El triángulo de Floyd.
14-Mar-14 R22+R23: Operaciones con polinomios.
18-Mar-14 R17[4,5]: Codificación por longitud y autocontadora.
21-Mar-14 Examen 4
25-Mar-14 T18[1,18]: La librería de las tablas.
28-Mar-14 R26[1,10]: Vectores y matrices.
01-Abr-14 T18[19,19]: El TAD de las tablas.
04-Abr-14 R26[11,24]: Vectores y matrices (2).
08-Abr-14 T22[1,39]: Grafos.
11-Abr-14 R26: Implementación de grafos con listas.
22-Abr-14 T17[1,29]: El TAD de los conjuntos.
  R27[1,4]: Ejercicios sobre grafos.
25-Abr-14 R27[5,22]: Ejercicios sobre grafos.
29-Abr-14 Exercitium: Ejercicios del 21 al 25 de abril.
13-May-14 R28: Operaciones con conjuntos.
  R29: Relaciones binarias.
16-May-14 Examen 5
20-May-14 Programación de dibujos con Gloss
27-May-14 Programación de fractales.
03-Jun-14 Programación de fractales.
06-Jun-14 Relación con dibujos y fractales.

Exercitium (Un reto diario de programación)

Misceláneas

La programación informática, como cualquier disciplina creativa, requiere estudio y práctica constantes. Este blog publica ejercicios de programación diariamente para que los programadores, independientemente de su nivel de experiencia, puedan mantener y perfeccionar sus habilidades, explorando soluciones más allá de sus zonas de confort habituales.

Objetivo y enfoque

Estos ejercicios no constituyen un concurso. Fueron originalmente diseñados para los estudiantes de la asignatura de Informática de 1º del Grado en Matemáticas. No se otorgan puntuaciones ni se mantiene un registro de quienes los completan. La verdadera recompensa es el conocimiento adquirido y la mejora de tus habilidades como programador.

Cada ejercicio está concebido para resolverse en aproximadamente quince minutos, aunque el tiempo real puede variar desde unos pocos minutos hasta varias horas, dependiendo de la experiencia individual, la creatividad y los recursos disponibles.

Antes de consultar las soluciones propuestas, te recomendamos intentar resolver el ejercicio por tu cuenta. Una vez completado, podrás comparar tu enfoque con las soluciones sugeridas.

Múltiples soluciones y enfoques

No existe una única solución "correcta" o perfecta para ejercicios. De hecho, te animamos a explorar diferentes enfoques una vez completado un ejercicio: puedes intentarlo con un algoritmo distinto o utilizando otro lenguaje de programación. También puedes compartir y discutir tus soluciones en Mastodon o en Bluesky.

La mayoría de las soluciones propuestas están implementadas en Haskell. Sin embargo, estos ejercicios son una excelente oportunidad para:

  • Perfeccionar tus habilidades en tu lenguaje de programación habitual
  • Aprender un nuevo lenguaje de programación
  • Comparar implementaciones en diferentes lenguajes

Recursos adicionales

Si eres estudiante principiante, especialmente si estás aprendiendo Haskell como primer lenguaje, te recomendamos consultar Programación funcional con Haskell. Este material ha sido la base del primer curso de informática en el Grado en Matemáticas de la Universidad de Sevilla durante muchos años.

Todas las soluciones están disponibles en GitHub como un proyecto con Stack, lo que evita problemas de compatibilidad entre diferentes versiones de las bibliotecas utilizadas.

Puedes suscribirte al canal RSS de este blog en https://jaalonso.github.io/exercitium/rss.xml.