{"id":3767,"date":"2013-10-22T16:12:34","date_gmt":"2013-10-22T14:12:34","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3767"},"modified":"2013-10-22T16:12:34","modified_gmt":"2013-10-22T14:12:34","slug":"i1m2013-el-cifrado-cesar-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-el-cifrado-cesar-en-haskell\/","title":{"rendered":"I1M2013: El cifrado C\u00e9sar en Haskell"},"content":{"rendered":"

En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado c\u00f3mo definir en Haskell la codificaci\u00f3n de mensajes usando el cifrado C\u00e9sar<\/a>. <\/p>\n

El programa es el siguiente
\n<\/p>\n

\r\nimport Data.Char\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Codificaci\u00f3n y descodificaci\u00f3n                                     --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (let2int c) es el entero correspondiente a la letra min\u00fascula c. Por\r\n-- ejemplo, \r\n--    let2int 'a'  ==>  0\r\n--    let2int 'd'  ==>  3\r\n--    let2int 'z'  ==>  25\r\nlet2int :: Char -> Int\r\nlet2int c = ord c - ord 'a'\r\n\r\n-- (int2let n) es la letra min\u00fascula correspondiente al entero n. Por\r\n-- ejemplo, \r\n--    int2let 0   ==>  'a'\r\n--    int2let 3   ==>  'd'\r\n--    int2let 25  ==>  'z'\r\nint2let :: Int -> Char\r\nint2let n = chr (ord 'a' + n)\r\n\r\n-- (desplaza n c) es el car\u00e1cter obtenido desplazando n caracteres el\r\n-- car\u00e1cter c. Por ejemplo,\r\n--    desplaza   3  'a'  ==>  'd'\r\n--    desplaza   3  'y'  ==>  'b'\r\n--    desplaza (-3) 'd'  ==>  'a'\r\n--    desplaza (-3) 'b'  ==>  'y'\r\ndesplaza :: Int -> Char -> Char\r\ndesplaza n c | isLower c = int2let ((let2int c + n) `mod` 26)\r\n             | otherwise =  c\r\n\r\n-- (codifica n xs) es el resultado de codificar el texto xs con un\r\n-- desplazamiento n. Por ejemplo,\r\n--    codifica   3  \"En todo la medida\"   ==>  \"Eq wrgr od phglgd\"\r\n--    codifica (-3) \"Eq wrgr od phglgd\"   ==>  \"En todo la medida\"\r\ncodifica :: Int -> String -> String\r\ncodifica n xs = [desplaza n x | x <- xs]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- An\u00e1lisis de frecuencia                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- tabla es la lista de la frecuencias de las letras en castellano, Por\r\n-- ejemplo, la frecuencia de la 'a' es del 12.53%, la de la 'b' es 1.42%.\r\ntabla :: [Float]\r\ntabla = [12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, 0.70, 6.25, \r\n          0.44, 0.01, 4.97, 3.15,  6.71, 8.68, 2.51, 0.88, 6.87, \r\n          7.98, 4.63, 3.93, 0.90,  0.02, 0.22, 0.90, 0.52]\r\n\r\n-- (minusculas xs) es la lista de min\u00fasculas en la cadena xs. Por\r\n-- ejemplo,\r\n--    minusculas \"EstoEsUnaPrueba\"  ==>  \"stosnarueba\"  \r\nminusculas :: String -> String\r\nminusculas xs = [x | x <- xs, isLower x]\r\n\r\n-- (ocurrencias x xs) es el n\u00famero de veces que ocurre el car\u00e1cter x en\r\n-- la cadena xs. Por ejemplo, \r\n--    ocurrencias 'a' \"Salamanca\"  ==>  4  \r\nocurrencias :: Char -> String -> Int\r\nocurrencias x xs = length [x' | x' <- xs, x == x']\r\n\r\n-- (porcentaje n m) es el porcentaje de n sobre m. Por ejemplo,\r\n--    porcentaje 2 5  ==>  40.0\r\nporcentaje :: Int -> Int -> Float\r\nporcentaje n m = (fromIntegral n \/ fromIntegral m) * 100\r\n\r\n-- (frecuencias xs) es la frecuencia de cada una de las min\u00fasculas de la\r\n-- cadena xs. Por ejemplo, \r\n--    > frecuencias \"en todo la medida\"\r\n--    [14.3,0,0,21.4,14.3,0,0,0,7.1,0,0,7.1,\r\n--     7.1,7.1,14.3,0,0,0,0,7.1,0,0,0,0,0,0]\r\nfrecuencias :: String -> [Float]\r\nfrecuencias xs = \r\n    [porcentaje (ocurrencias x xs) n | x <- ['a'..'z']]\r\n    where n = length (minusculas xs)\r\n\r\n-- (chiCuadrado os es) es la medida chi cuadrado de la discrepancia\r\n-- entre la distribuci\u00f3n observada os y la esperada es. Por ejemplo,\r\n--    chiCuadrado [3,5,6] [3,5,6]  ==>  0.0\r\n--    chiCuadrado [3,5,6] [5,6,3]  ==>  3.9666667\r\nchiCuadrado :: [Float] -> [Float] -> Float\r\nchiCuadrado os es = sum [((o - e) ^ 2) \/ e | (o,e) <- zip os es]\r\n\r\n-- (rota n xs) es la lista obtenida rotando n posiciones los elementos\r\n-- de la lista xs. Por ejemplo,\r\n--    rota 2 \"ramo\"  ==>  \"mora\"\r\nrota :: Int -> [a] -> [a]\r\nrota n xs = drop n xs ++ take n xs\r\n\r\n-- (posiciones x xs) es la lista de las posiciones de x en la lista\r\n-- xs. Por ejemplo, \r\n--    posiciones 'a' \"Salamanca\"  ==>  [1,3,5,8]\r\nposiciones :: Eq a => a -> [a] -> [Int]\r\nposiciones x xs = [i | (x',i) <- zip xs [0..], x == x']\r\n\r\n-- (descifra xs) es la cadena obtenida descodificando la cadena xs por\r\n-- el desplazamiento que produce una distribuci\u00f3n de min\u00fasculas con\r\n-- la menor deviaci\u00f3n chi cuadrado respecto de la tabla de distribuci\u00f3n\r\n-- de las vocales en castellano. Por ejemplo, \r\n--   > descifra \"Lt htruqnhfit ij qf anif jx ijxhzgwnw qt xnruqj vzj jx\"\r\n--   \"Lo complicado de la vida es descubrir lo simple que es\"\r\ndescifra :: String -> String\r\ndescifra xs =  codifica (-factor) xs\r\n    where\r\n      factor = head (posiciones (minimum tabChi) tabChi)\r\n      tabChi = [chiCuadrado (rota n tabla') tabla | n <- [0..25]]\r\n      tabla' = frecuencias xs\r\n<\/pre>\n
\nLas transparencias usadas en la clase son las comprendidas entre las p\u00e1ginas 14 y 29 del tema 5<\/a>:
\n