I1M2012: Ejercicios sobre el cifrado César

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los ejercicios de la 6ª 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

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

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

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