I1M2011: Ejercicios de definiciones por comprensión y cifrado César en Haskell

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los 5 últimos ejercicios de la 4ª relación, que tratan sobre definiciones por comprensión, y los de la 5ª relación, que amplía la codificación César vista en clase para incluir las mayúsculas.

Los ejercicios, y sus soluciones, se muestran a continuación: Los de la 4ª relación son

-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir, por comprensión, la función
--    sumaConsecutivos :: [Int] -> [Int]
-- tal que (sumaConsecutivos xs) es la suma de los pares de elementos
-- consecutivos de la lista xs. Por ejemplo,
--    sumaConsecutivos [3,1,5,2]  ==  [4,6,7]
--    sumaConsecutivos [3]        ==  []
-- ---------------------------------------------------------------------

sumaConsecutivos :: [Int] -> [Int]
sumaConsecutivos xs = [x+y | (x,y) <- zip xs (tail xs)]

-- ---------------------------------------------------------------------
-- Ejercicio 7.  La distancia de Hamming entre dos listas es el número
-- de posiciones en que los correspondientes elementos son
-- distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba" 
-- es 2 (porque hay 2 posiciones en las que los elementos
-- correspondientes son distintos: la 1ª y la 3ª). 
--    
-- Definir la función
--    distancia :: Eq a => [a] -> [a] -> Int
-- tal que (distancia xs ys) es la distancia de Hamming entre xs e
-- ys. Por ejemplo,
--    distancia "romano" "comino"  ==  2
--    distancia "romano" "camino"  ==  3
--    distancia "roma"   "comino"  ==  2
--    distancia "roma"   "camino"  ==  3
--    distancia "romano" "ron"     ==  1
--    distancia "romano" "cama"    ==  2
--    distancia "romano" "rama"    ==  1
-- ---------------------------------------------------------------------

distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = sum [1 | (x,y) <- zip xs ys, x /= y] 

-- ---------------------------------------------------------------------
-- Ejercicio 8. La suma de la serie
--    1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + ...
-- es pi^2/6. Por tanto, pi se puede aproximar mediante la raíz cuadrada
-- de 6 por la suma de la serie.
-- 
-- Definir la función aproximaPi tal que (aproximaPi n) es la aproximación 
-- de pi obtenida mediante n términos de la serie. Por ejemplo, 
--    aproximaPi 4    == sqrt(6*(1/1^2 + 1/2^2 + 1/3^2 + 1/4^2))
--                    == 2.9226129861250305
--    aproximaPi 1000 == 3.1406380562059946
-- ---------------------------------------------------------------------

aproximaPi n = sqrt(6*sum [1/x^2 | x <- [1..n]])

-- ---------------------------------------------------------------------
-- Ejercicio 9. Un número natural n se denomina abundante si es menor
-- que la suma de sus divisores propios. Por ejemplo, 12 y 30 son
-- abundantes pero 5 y 28 no lo son.
-- ---------------------------------------------------------------------
-- Ejercicio 9.1. Definir la función numeroAbundante tal que
-- (numeroAbundante n) se verifica si n es un número abundante. Por
-- ejemplo, 
--    numeroAbundante 5  == False
--    numeroAbundante 12 == True
--    numeroAbundante 28 == False
--    numeroAbundante 30 == True
-- ---------------------------------------------------------------------

divisores:: Int -> [Int]
divisores n = [m | m <- [1..n-1], n `mod` m == 0]

numeroAbundante:: Int -> Bool 
numeroAbundante n = n < sum (divisores n)

-- ---------------------------------------------------------------------
-- Ejercicio 9.2. Definir la función numerosAbundantesMenores tal que
-- (numerosAbundantesMenores n) es la lista de números abundantes
-- menores o iguales que n. Por ejemplo,
--    numerosAbundantesMenores 50  ==  [12,18,20,24,30,36,40,42,48]
-- ---------------------------------------------------------------------

numerosAbundantesMenores :: Int -> [Int]
numerosAbundantesMenores n = [x | x <- [1..n], numeroAbundante x]

-- ---------------------------------------------------------------------
-- Ejercicio 9.3. Definir la función todosPares tal que (todosPares n)
-- se verifica si todos los números abundantes menores o iguales que n
-- son pares. Por ejemplo,
--    todosPares 10    ==  True
--    todosPares 100   ==  True
--    todosPares 1000  ==  False
-- ---------------------------------------------------------------------

todosPares :: Int -> Bool
todosPares n = and [even x | x <- numerosAbundantesMenores n]

-- ---------------------------------------------------------------------
-- Ejercicio 9.4. Definir la constante primerAbundanteImpar que calcule
-- el primer número natural abundante impar. Determinar el valor de
-- dicho número.
-- ---------------------------------------------------------------------

primerAbundanteImpar:: Int
primerAbundanteImpar = head [x | x <-[1..], numeroAbundante x, odd x]

-- Su cálculo es
--    ghci> primerAbundanteImpar
--    945

-- ---------------------------------------------------------------------
-- Ejercicio 10.1. (Problema 9 del Proyecto Euler). Una terna pitagórica
-- es una terna de números naturales (a,b,c) tal que a<b<c y
-- a^2+b^2=c^2. Por ejemplo (3,4,5) es una terna pitagórica. 
-- 
-- Definir la función 
--    ternasPitagoricas :: Integer -> [[Integer]]
-- tal que (ternasPitagoricas x) es la lista de las ternas pitagóricas
-- cuya suma es x. Por ejemplo,
--    ternasPitagoricas 12  ==  [(3,4,5)]
--    ternasPitagoricas 60  ==  [(10,24,26),(15,20,25)]
-- ---------------------------------------------------------------------

ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas x = [(a,b,c) | a <- [1..x], 
                                 b <- [a+1..x], 
                                 c <- [x-a-b], 
                                 a^2 + b^2 == c^2]

-- ---------------------------------------------------------------------
-- Ejercicio 10.2. Definir la constante euler9 tal que euler9 es producto
-- abc donde (a,b,c) es la única terna pitagórica tal que a+b+c=1000. 
-- Calcular el valor de euler9.
-- ---------------------------------------------------------------------

euler9 = a*b*c
    where (a,b,c) = head (ternasPitagoricas 1000)

-- El cálculo del valor de euler9 es
--    ghci> euler9
--    31875000

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

-- ---------------------------------------------------------------------

-- Ejercicio 6. Definir, por comprensión, la función

-- sumaConsecutivos :: [Int] -> [Int]

-- tal que (sumaConsecutivos xs) es la suma de los pares de elementos

-- consecutivos de la lista xs. Por ejemplo,

-- sumaConsecutivos [3,1,5,2] == [4,6,7]

-- sumaConsecutivos [3] == []

-- ---------------------------------------------------------------------

sumaConsecutivos :: [Int] -> [Int]

sumaConsecutivos xs = [x+y | (x,y) <- zip xs (tail xs)]

-- ---------------------------------------------------------------------

-- Ejercicio 7. La distancia de Hamming entre dos listas es el número

-- de posiciones en que los correspondientes elementos son

-- distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba"

-- es 2 (porque hay 2 posiciones en las que los elementos

-- correspondientes son distintos: la 1ª y la 3ª).

-- Definir la función

-- distancia :: Eq a => [a] -> [a] -> Int

-- tal que (distancia xs ys) es la distancia de Hamming entre xs e

-- ys. Por ejemplo,

-- distancia "romano" "comino" == 2

-- distancia "romano" "camino" == 3

-- distancia "roma" "comino" == 2

-- distancia "roma" "camino" == 3

-- distancia "romano" "ron" == 1

-- distancia "romano" "cama" == 2

-- distancia "romano" "rama" == 1

-- ---------------------------------------------------------------------

distancia :: Eq a => [a] -> [a] -> Int

distancia xs ys = sum [1 | (x,y) <- zip xs ys, x /= y]

-- ---------------------------------------------------------------------

-- Ejercicio 8. La suma de la serie

-- 1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + ...

-- es pi^2/6. Por tanto, pi se puede aproximar mediante la raíz cuadrada

-- de 6 por la suma de la serie.

-- Definir la función aproximaPi tal que (aproximaPi n) es la aproximación

-- de pi obtenida mediante n términos de la serie. Por ejemplo,

-- aproximaPi 4 == sqrt(6*(1/1^2 + 1/2^2 + 1/3^2 + 1/4^2))

-- == 2.9226129861250305

-- aproximaPi 1000 == 3.1406380562059946

-- ---------------------------------------------------------------------

aproximaPi n = sqrt(6*sum [1/x^2 | x <- [1..n]])

-- ---------------------------------------------------------------------

-- Ejercicio 9. Un número natural n se denomina abundante si es menor

-- que la suma de sus divisores propios. Por ejemplo, 12 y 30 son

-- abundantes pero 5 y 28 no lo son.

-- ---------------------------------------------------------------------

-- Ejercicio 9.1. Definir la función numeroAbundante tal que

-- (numeroAbundante n) se verifica si n es un número abundante. Por

-- ejemplo,

-- numeroAbundante 5 == False

-- numeroAbundante 12 == True

-- numeroAbundante 28 == False

-- numeroAbundante 30 == True

-- ---------------------------------------------------------------------

divisores:: Int -> [Int]

divisores n = [m | m <- [1..n-1], n `mod` m == 0]

numeroAbundante:: Int -> Bool

numeroAbundante n = n < sum (divisores n)

-- ---------------------------------------------------------------------

-- Ejercicio 9.2. Definir la función numerosAbundantesMenores tal que

-- (numerosAbundantesMenores n) es la lista de números abundantes

-- menores o iguales que n. Por ejemplo,

-- numerosAbundantesMenores 50 == [12,18,20,24,30,36,40,42,48]

-- ---------------------------------------------------------------------

numerosAbundantesMenores :: Int -> [Int]

numerosAbundantesMenores n = [x | x <- [1..n], numeroAbundante x]

-- ---------------------------------------------------------------------

-- Ejercicio 9.3. Definir la función todosPares tal que (todosPares n)

-- se verifica si todos los números abundantes menores o iguales que n

-- son pares. Por ejemplo,

-- todosPares 10 == True

-- todosPares 100 == True

-- todosPares 1000 == False

-- ---------------------------------------------------------------------

todosPares :: Int -> Bool

todosPares n = and [even x | x <- numerosAbundantesMenores n]

-- ---------------------------------------------------------------------

-- Ejercicio 9.4. Definir la constante primerAbundanteImpar que calcule

-- el primer número natural abundante impar. Determinar el valor de

-- dicho número.

-- ---------------------------------------------------------------------

primerAbundanteImpar:: Int

primerAbundanteImpar = head [x | x <-[1..], numeroAbundante x, odd x]

-- Su cálculo es

-- ghci> primerAbundanteImpar

-- 945

-- ---------------------------------------------------------------------

-- Ejercicio 10.1. (Problema 9 del Proyecto Euler). Una terna pitagórica

-- es una terna de números naturales (a,b,c) tal que a<b<c y

-- a^2+b^2=c^2. Por ejemplo (3,4,5) es una terna pitagórica.

-- Definir la función

-- ternasPitagoricas :: Integer -> [[Integer]]

-- tal que (ternasPitagoricas x) es la lista de las ternas pitagóricas

-- cuya suma es x. Por ejemplo,

-- ternasPitagoricas 12 == [(3,4,5)]

-- ternasPitagoricas 60 == [(10,24,26),(15,20,25)]

-- ---------------------------------------------------------------------

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

ternasPitagoricas x = [(a,b,c) | a <- [1..x],

b <- [a+1..x],

c <- [x-a-b],

a^2 + b^2 == c^2]

-- ---------------------------------------------------------------------

-- Ejercicio 10.2. Definir la constante euler9 tal que euler9 es producto

-- abc donde (a,b,c) es la única terna pitagórica tal que a+b+c=1000.

-- Calcular el valor de euler9.

-- ---------------------------------------------------------------------

euler9 = a*b*c

where (a,b,c) = head (ternasPitagoricas 1000)

-- El cálculo del valor de euler9 es

-- ghci> euler9

-- 31875000

Los de la 5ª relación son

-- I1M 2011-12: Rel_5_sol.hs (5 de Noviembre de 2011)
-- Definiciones por comprensión: El cifrado César.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------

-- En el tema 5, cuyas transparencias se encuentran en 
--    http://www.cs.us.es/~jalonso/cursos/i1m-11/temas/tema-5.pdf
-- se estudió, como aplicación de las definiciones por comprennsión, el
-- cifrado César. El objetivo de esta relación es modificar el programa
-- de cifrado César para que pueda utilizar también letras
-- mayúsculas. Por ejemplo,  
--    *Main> descifra "Ytit Ufwf Sfif"
--    "Todo Para Nada"
-- Para ello, se propone la modificación de las funciones
-- correspondientes del tema 5.

-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import Data.Char

-- (minuscula2int c) es el entero correspondiente a la letra minúscula
-- c. Por ejemplo, 
--    minuscula2int 'a'  ==  0
--    minuscula2int 'd'  ==  3
--    minuscula2int 'z'  ==  25
minuscula2int :: Char -> Int
minuscula2int c = ord c - ord 'a'

-- (mayuscula2int c) es el entero correspondiente a la letra mayúscula
-- c. Por ejemplo, 
--    mayuscula2int 'A'  ==  0
--    mayuscula2int 'D'  ==  3
--    mayuscula2int 'Z'  ==  25
mayuscula2int :: Char -> Int
mayuscula2int c = ord c - ord 'A'

-- (int2minuscula n) es la letra minúscula correspondiente al entero
-- n. Por ejemplo, 
--    int2minuscula 0   ==  'a'
--    int2minuscula 3   ==  'd'
--    int2minuscula 25  ==  'z'
int2minuscula :: Int -> Char
int2minuscula n = chr (ord 'a' + n)

-- (int2mayuscula n) es la letra minúscula correspondiente al entero
-- n. Por ejemplo, 
--    int2mayuscula 0   ==  'A'
--    int2mayuscula 3   ==  'D'
--    int2mayuscula 25  ==  'Z'
int2mayuscula :: Int -> Char
int2mayuscula n = chr (ord 'A' + n)

-- (desplaza n c) es el carácter obtenido desplazando n caracteres el
-- carácter c. Por ejemplo, 
--    desplaza   3  'a'  ==  'd'
--    desplaza   3  'y'  ==  'b'
--    desplaza (-3) 'd'  ==  'a'
--    desplaza (-3) 'b'  ==  'y'
--    desplaza   3  'A'  ==  'D'
--    desplaza   3  'Y'  ==  'B'
--    desplaza (-3) 'D'  ==  'A'
--    desplaza (-3) 'B'  ==  'Y'
desplaza :: Int -> Char -> Char
desplaza n c 
    | elem c ['a'..'z'] = int2minuscula ((minuscula2int c+n) `mod` 26)
    | elem c ['A'..'Z'] = int2mayuscula ((mayuscula2int c+n) `mod` 26)
    | otherwise         = c

-- (codifica n xs) es el resultado de codificar el texto xs con un
-- desplazamiento n. Por ejemplo, 
--    *Main> codifica   3  "En Todo La Medida" 
--    "Hq Wrgr Od Phglgd"
--    *Main> codifica (-3) "Hq Wrgr Od Phglgd"
--    "En Todo La Medida"
codifica :: Int -> String -> String
codifica n xs = [desplaza n x | x <- xs]

-- tabla es la lista de la frecuencias de las letras en castellano, Por
-- ejemplo, la frecuencia de la 'a' es del 12.53%, la de la 'b' es
-- 1.42%. 
tabla :: [Float]
tabla = [12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, 
          0.70, 6.25, 0.44, 0.01,  4.97, 3.15, 6.71, 
          8.68, 2.51, 0.88, 6.87,  7.98, 4.63, 3.93, 
          0.90, 0.02, 0.22, 0.90,  0.52]

-- (porcentaje n m) es el porcentaje de n sobre m. Por ejemplo,
--    porcentaje 2 5  ==  40.0  
porcentaje :: Int -> Int -> Float
porcentaje n m = (fromIntegral n / fromIntegral m) * 100

-- (letras xs) es la cadena formada por las letras de la cadena xs. Por
-- ejemplo,  
--    letras "Esto Es Una Prueba"  ==  "EstoEsUnaPrueba"
letras :: String -> String
letras xs = [x | x <- xs, elem x (['a'..'z']++['A'..'Z'])]

-- (ocurrencias x xs) es el número de veces que ocurre el carácter x en
-- la cadena xs. Por ejemplo, 
--    ocurrencias 'a' "Salamanca"  ==  4  
ocurrencias :: Char -> String -> Int
ocurrencias x xs = length [x' | x' <- xs, x == x']  

-- (frecuencias xs) es la frecuencia de cada una de las letras de la
-- cadena xs. Por ejemplo, 
--    *Main> frecuencias "En Todo La Medida"
--    [14.3,0,0,21.4,14.3,0,0,0,7.1,0,0,7.1,
--     7.1,7.1,14.3,0,0,0,0,7.1,0,0,0,0,0,0]
frecuencias :: String -> [Float]
frecuencias xs = 
    [porcentaje (ocurrencias x xs') n | x <- ['a'..'z']]
    where xs' = [toLower x | x <- xs]
          n   = length (letras xs)

-- (chiCuad os es) es la medida chi cuadrado de las distribuciones os y
-- es. Por ejemplo, 
--    chiCuad [3,5,6] [3,5,6]  ==  0.0
--    chiCuad [3,5,6] [5,6,3]  ==  3.9666667
chiCuad :: [Float] -> [Float] -> Float
chiCuad os es = sum [((o-e)^2)/e | (o,e) <- zip os es]

-- (rota n xs) es la lista obtenida rotando n posiciones los elementos
-- de la lista xs. Por ejemplo, 
--    rota 2 "manolo"  ==  "noloma"  
rota :: Int -> [a] -> [a]
rota n xs = drop n xs ++ take n xs

-- (descifra xs) es la cadena obtenida descodificando la cadena xs por
-- el anti-desplazamiento que produce una distribución de letras con la
-- menor deviación chi cuadrado respecto de la tabla de distribución de
-- las letras en castellano. Por ejemplo, 
--    *Main> codifica 5 "Todo Para Nada"
--    "Ytit Ufwf Sfif"
--    *Main> descifra "Ytit Ufwf Sfif"
--    "Todo Para Nada"
descifra :: String -> String
descifra xs =  codifica (-factor) xs
 where
  factor = head (posiciones (minimum tabChi) tabChi)
  tabChi = [chiCuad (rota n tabla') tabla | n <- [0..25]]
  tabla' = frecuencias xs

posiciones :: Eq a => a -> [a] -> [Int]
posiciones x xs = 
    [i | (x',i) <- zip xs [0..], x == x']

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

-- I1M 2011-12: Rel_5_sol.hs (5 de Noviembre de 2011)

-- Definiciones por comprensión: El cifrado César.

-- Departamento de Ciencias de la Computación e I.A.

-- Universidad de Sevilla

-- =====================================================================

-- ---------------------------------------------------------------------

-- Introducción --

-- ---------------------------------------------------------------------

-- En el tema 5, cuyas transparencias se encuentran en

-- http://www.cs.us.es/~jalonso/cursos/i1m-11/temas/tema-5.pdf

-- se estudió, como aplicación de las definiciones por comprennsión, el

-- cifrado César. El objetivo de esta relación es modificar el programa

-- de cifrado César para que pueda utilizar también letras

-- mayúsculas. Por ejemplo,

-- *Main> descifra "Ytit Ufwf Sfif"

-- "Todo Para Nada"

-- Para ello, se propone la modificación de las funciones

-- correspondientes del tema 5.

-- ---------------------------------------------------------------------

-- Importación de librerías auxiliares --

-- ---------------------------------------------------------------------

import Data.Char

-- (minuscula2int c) es el entero correspondiente a la letra minúscula

-- c. Por ejemplo,

-- minuscula2int 'a' == 0

-- minuscula2int 'd' == 3

-- minuscula2int 'z' == 25

minuscula2int :: Char -> Int

minuscula2int c = ord c - ord 'a'

-- (mayuscula2int c) es el entero correspondiente a la letra mayúscula

-- c. Por ejemplo,

-- mayuscula2int 'A' == 0

-- mayuscula2int 'D' == 3

-- mayuscula2int 'Z' == 25

mayuscula2int :: Char -> Int

mayuscula2int c = ord c - ord 'A'

-- (int2minuscula n) es la letra minúscula correspondiente al entero

-- n. Por ejemplo,

-- int2minuscula 0 == 'a'

-- int2minuscula 3 == 'd'

-- int2minuscula 25 == 'z'

int2minuscula :: Int -> Char

int2minuscula n = chr (ord 'a' + n)

-- (int2mayuscula n) es la letra minúscula correspondiente al entero

-- n. Por ejemplo,

-- int2mayuscula 0 == 'A'

-- int2mayuscula 3 == 'D'

-- int2mayuscula 25 == 'Z'

int2mayuscula :: Int -> Char

int2mayuscula n = chr (ord 'A' + n)

-- (desplaza n c) es el carácter obtenido desplazando n caracteres el

-- carácter c. Por ejemplo,

-- desplaza 3 'a' == 'd'

-- desplaza 3 'y' == 'b'

-- desplaza (-3) 'd' == 'a'

-- desplaza (-3) 'b' == 'y'

-- desplaza 3 'A' == 'D'

-- desplaza 3 'Y' == 'B'

-- desplaza (-3) 'D' == 'A'

-- desplaza (-3) 'B' == 'Y'

desplaza :: Int -> Char -> Char

desplaza n c

| elem c ['a'..'z'] = int2minuscula ((minuscula2int c+n) `mod` 26)

| elem c ['A'..'Z'] = int2mayuscula ((mayuscula2int c+n) `mod` 26)

| otherwise = c

-- (codifica n xs) es el resultado de codificar el texto xs con un

-- desplazamiento n. Por ejemplo,

-- *Main> codifica 3 "En Todo La Medida"

-- "Hq Wrgr Od Phglgd"

-- *Main> codifica (-3) "Hq Wrgr Od Phglgd"

-- "En Todo La Medida"

codifica :: Int -> String -> String

codifica n xs = [desplaza n x | x <- xs]

-- tabla es la lista de la frecuencias de las letras en castellano, Por

-- ejemplo, la frecuencia de la 'a' es del 12.53%, la de la 'b' es

-- 1.42%.

tabla :: [Float]

tabla = [12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01,

0.70, 6.25, 0.44, 0.01, 4.97, 3.15, 6.71,

8.68, 2.51, 0.88, 6.87, 7.98, 4.63, 3.93,

0.90, 0.02, 0.22, 0.90, 0.52]

-- (porcentaje n m) es el porcentaje de n sobre m. Por ejemplo,

-- porcentaje 2 5 == 40.0

porcentaje :: Int -> Int -> Float

porcentaje n m = (fromIntegral n / fromIntegral m) * 100

-- (letras xs) es la cadena formada por las letras de la cadena xs. Por

-- ejemplo,

-- letras "Esto Es Una Prueba" == "EstoEsUnaPrueba"

letras :: String -> String

letras xs = [x | x <- xs, elem x (['a'..'z']++['A'..'Z'])]

-- (ocurrencias x xs) es el número de veces que ocurre el carácter x en

-- la cadena xs. Por ejemplo,

-- ocurrencias 'a' "Salamanca" == 4

ocurrencias :: Char -> String -> Int

ocurrencias x xs = length [x' | x' <- xs, x == x']

-- (frecuencias xs) es la frecuencia de cada una de las letras de la

-- cadena xs. Por ejemplo,

-- *Main> frecuencias "En Todo La Medida"

-- [14.3,0,0,21.4,14.3,0,0,0,7.1,0,0,7.1,

-- 7.1,7.1,14.3,0,0,0,0,7.1,0,0,0,0,0,0]

frecuencias :: String -> [Float]

frecuencias xs =

[porcentaje (ocurrencias x xs') n | x <- ['a'..'z']]

where xs' = [toLower x | x <- xs]

n = length (letras xs)

-- (chiCuad os es) es la medida chi cuadrado de las distribuciones os y

-- es. Por ejemplo,

-- chiCuad [3,5,6] [3,5,6] == 0.0

-- chiCuad [3,5,6] [5,6,3] == 3.9666667

chiCuad :: [Float] -> [Float] -> Float

chiCuad os es = sum [((o-e)^2)/e | (o,e) <- zip os es]

-- (rota n xs) es la lista obtenida rotando n posiciones los elementos

-- de la lista xs. Por ejemplo,

-- rota 2 "manolo" == "noloma"

rota :: Int -> [a] -> [a]

rota n xs = drop n xs ++ take n xs

-- (descifra xs) es la cadena obtenida descodificando la cadena xs por

-- el anti-desplazamiento que produce una distribución de letras con la

-- menor deviación chi cuadrado respecto de la tabla de distribución de

-- las letras en castellano. Por ejemplo,

-- *Main> codifica 5 "Todo Para Nada"

-- "Ytit Ufwf Sfif"

-- *Main> descifra "Ytit Ufwf Sfif"

-- "Todo Para Nada"

descifra :: String -> String

descifra xs = codifica (-factor) xs

where

factor = head (posiciones (minimum tabChi) tabChi)

tabChi = [chiCuad (rota n tabla') tabla | n <- [0..25]]

tabla' = frecuencias xs

posiciones :: Eq a => a -> [a] -> [Int]

posiciones x xs =

[i | (x',i) <- zip xs [0..], x == x']

Se puede imprimir o compartir con