Codificación matricial
El procedimiento de codificación matricial se puede entender siguiendo la codificación del mensaje "todoparanada" como se muestra a continuación:
- Se calcula la longitud L del mensaje. En el ejemplo es L es 12.
- Se calcula el menor entero positivo N cuyo cuadrado es mayor o igual que L. En el ejemplo N es 4.
- Se extiende el mensaje con N²-L asteriscos. En el ejemplo, el mensaje extendido es
"todoparanada****" - Con el mensaje extendido se forma una matriz cuadrada NxN. En el ejemplo la matriz es
|
1 2 3 4 |
| t o d o | | p a r a | | n a d a | | * * * * | |
- Se rota 90º la matriz del mensaje extendido. En el ejemplo, la matriz rotada es
|
1 2 3 4 |
| * n p t | | * a a o | | * d r d | | * a a o | |
- Se calculan los elementos de la matriz rotada. En el ejemplo, los elementos son
"*npt*aap*drd*aao" - El mensaje codificado se obtiene eliminando los asteriscos de los elementos de la matriz rotada. En el ejemplo,
"nptaapdrdaao".
Definir la función
|
1 |
codificado :: String -> String |
tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,
|
1 2 3 4 |
codificado "todoparanada" == "nptaaodrdaao" codificado "nptaaodrdaao" == "danaopadtora" codificado "danaopadtora" == "todoparanada" codificado "entodolamedida" == "dmdeaeondltiao" |
Nota: Este ejercicio está basado en el problema Secret Message de Kattis.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
import Data.List (genericLength) import Data.Array codificado :: String -> String codificado cs = filter (/='*') (elems (rota p)) where n = ceiling (sqrt (genericLength cs)) p = listArray ((1,1),(n,n)) (cs ++ repeat '*') rota :: Array (Int,Int) Char -> Array (Int,Int) Char rota p = array d [((i,j),p!(n+1-j,i)) | (i,j) <- indices p] where d = bounds p n = fst (snd d) |