Una de las razones por la que el matemático húngaro Paul Erdős es conocido es por la multitud de colaboraciones que realizó durante toda su carrera, un total de 511. Tal es así que se establece la distancia a Erdős como la distancia que has estado de coautoría con Erdős. Por ejemplo, si eres Paul Erdős tu distancia a Erdős es 0, si has escrito un artículo con Erdős tu distancia es 1, si has escrito un artículo con alguien que ha escrito un artículo con Erdős tu distancia es 2, etc. El objetivo de este problema es definir una función que a partir de una lista de pares de coautores y un número natural n calcular la lista de los matemáticos a una distancia n de Erdős.

Para el problema se considerará la siguiente lista de coautores

coautores :: [(String,String)]
coautores =
  [("Paul Erdos","Ernst Straus"),("Paul Erdos","Pascual Jordan"),
   ("Paul Erdos","D. Kleitman"),("Albert Einstein","Ernst Straus"),
   ("John von Newmann","David Hilbert"),("S. Glashow","D. Kleitman"),
   ("John von Newmann","Pascual Jordan"), ("David Pines","D. Bohm"),
   ("Albert Einstein","Otto Stern"),("S. Glashow", "M. Gell-Mann"),
   ("Richar Feynman","M. Gell-Mann"),("M. Gell-Mann","David Pines"),
   ("David Pines","A. Bohr"),("Wolfgang Pauli","Albert Einstein"),
   ("D. Bohm","L. De Broglie"), ("Paul Erdos","J. Conway"),
   ("J. Conway", "P. Doyle"),("Paul Erdos","A. J. Granville"),
   ("A. J. Granville","B. Mazur"),("B. Mazur","Andrew Wiles")]

Definir la función

numeroDeErdos :: [(String, String)] -> Int -> [String]

tal que (numeroDeErdos xs n) es la lista de lista de los matemáticos de la lista de coautores xs que se encuentran a una distancia n de Erdős. Por ejemplo,

λ> numeroDeErdos coautores 0
["Paul Erdos"]
λ> numeroDeErdos coautores 1
["Ernst Straus","Pascual Jordan","D. Kleitman","J. Conway","A. J. Granville"]
λ> numeroDeErdos coautores 2
["Albert Einstein","John von Newmann","S. Glashow","P. Doyle","B. Mazur"]

Leer más…

Definir la función

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

tal que (agrupacion xs) es la lista obtenida agrupando los elementos de xs según su primera aparición. Por ejemplo,

agrupacion [3,1,5,1,7,1,5,3]  ==  [3,3,1,1,1,5,5,7]
agrupacion "babcacb"          ==  "bbbaacc"

Leer más…

Definir la función

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

tal que (mayoresMitad xs) es la lista de los elementos de xs que son mayores que la mitad de los elementos de xs, suponiendo que los elementos de xs son distintos. Por ejemplo,

sort (mayoresMitad [1,6,3,4])    ==  [4,6]
sort (mayoresMitad [1,6,3,4,7])  ==  [4,6,7]
sort (mayoresMitad [1,6,3,4,2])  ==  [3,4,6]
length (mayoresMitad3 [1..10^6]) ==  500000

Nota: Se considera que si la lista tiene 2n+1 elementos, su mitad tiene n elementos.

Leer más…

Un carácter c de una cadena cs está bien colocado si la posición de c en cs es la misma que en el abecedario (sin distinguir entre mayúsculas y minúsculas). Por ejemplo, los elementos bien colocados de la cadena "aBaCEria" son 'a', 'B' y 'E'.

Definir la función

nBienColocados :: String -> Int

tal que (nBienColocados cs) es el número de elementos bien colocados de la cadena cs. Por ejemplo,

nBienColocados "aBaCEria"                    ==  3
nBienColocados "xBxxExxxIxxxxNxxxxxTxxxXYZ"  ==  8

Leer más…

Los subconjuntos distinto del vacío del conjunto {3, 2, 5}, junto con sus máximos elementos, son

{3}       su máximo es 3
{2}       su máximo es 2
{5}       su máximo es 5
{3, 2}    su máximo es 3
{3, 5}    su máximo es 5
{2, 5}    su máximo es 5
{3, 2, 5} su máximo es 5

Por tanto, la suma de los máximos elementos de los subconjuntos de {3, 2, 5} es 3 + 2 + 5 + 3 + 5 + 5 + 5 = 28.

Definir la función

sumaMaximos :: [Integer] -> Integer

tal que (sumaMaximos xs) es la suma de los máximos elementos de los subconjuntos de xs. Por ejemplo,

sumaMaximos [3,2,5]    ==  28
sumaMaximos [4,1,6,3]  ==  71
sumaMaximos [1..100]   ==  125497409422594710748173617332225
length (show (sumaMaximos [1..10^5]))  ==  30108
sumaMaximos [1..10^5] `mod` (10^7)     ==  4490625

Leer más…

Se dice que un elemento x de una lista xs respeta la ordenación si x es mayor o igual que todos lo que tiene delante en xs y es menor o igual que todos lo que tiene detrás en xs. Por ejemplo, en la lista lista [3,2,1,4,6,5,7,9,8] el número 4 respeta la ordenación pero el número 5 no la respeta (porque es mayor que el 6 que está delante).

Definir la función

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

tal que (respetuosos xs) es la lista de los elementos de xs que respetan la ordenación. Por ejemplo,

respetuosos [3,2,1,4,6,4,7,9,8]  ==  [4,7]
respetuosos [2,1,3,4,6,4,7,8,9]  ==  [3,4,7,8,9]
respetuosos "abaco"              ==  "aco"
respetuosos "amor"               ==  "amor"
respetuosos "romanos"            ==  "s"
respetuosos [1..9]               ==  [1,2,3,4,5,6,7,8,9]
respetuosos [9,8..1]             ==  []

Comprobar con QuickCheck que para cualquier lista de enteros xs se verifican las siguientes propiedades:

• todos los elementos de (sort xs) respetan la ordenación y
• en la lista (nub (reverse (sort xs))) hay como máximo un elemento que respeta la ordenación.

Leer más…

Definir la función

sinCerosFinales :: Int -> Int

tal que (sinCerosFinales n) es el número obtenido eliminando los ceros finales de n. Por ejemplo,

sinCerosFinales 104050     == 10405
sinCerosFinales 960000     == 96
sinCerosFinales 100050     == 10005
sinCerosFinales (-10050)   == -1005
sinCerosFinales 12         == 12
sinCerosFinales 0          == 0

Comprobar con QuickCheck que, para cualquier número entero n,

sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

Leer más…

Una lista de listas es engarzada si el último elemento de cada lista coincide con el primero de la siguiente.

Definir la función

engarzada :: Eq a => [[a]] -> Bool

tal que (engarzada xss) se verifica si xss es una lista engarzada. Por ejemplo,

engarzada [[1,2,3], [3,5], [5,9,0]] == True
engarzada [[1,4,5], [5,0], [1,0]]   == False
engarzada [[1,4,5], [], [1,0]]      == False
engarzada [[2]]                     == True

Leer más…

Una lista de números enteros se llama alternada si sus elementos son alternativamente par/impar o impar/par.

Definir la función

alternada :: [Int] -> Bool

tal que (alternada xs) se verifica si xs es una lista alternada. Por ejemplo,

alternada [1,2,3]     == True
alternada [1,4,6,5]   == False
alternada [1,4,3,5]   == False
alternada [8,1,2,3,4] == True
alternada [8,1,2,3]   == True
alternada [8]         == True
alternada [7]         == True

Leer más…

Definir la función

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

tal que (sumasParesImpares) xs es el par formado por la suma de los elementos de xs en posiciones pares y por la suma de los elementos de xs en posiciones impares. Por ejemplo,

sumasParesImpares []         ==  (0,0)
sumasParesImpares [3]        ==  (3,0)
sumasParesImpares [3,2]      ==  (3,2)
sumasParesImpares [3,2,1]    ==  (4,2)
sumasParesImpares [3,2,1,5]  ==  (4,7)
sumasParesImpares [1..10^7]  ==  (25000000000000,25000005000000)

Leer más…