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
| t o d o |
| p a r a |
| n a d a |
| * * * * | |
| 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
| * n p t |
| * a a o |
| * d r d |
| * a a o | |
| * 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
codificado :: String -> String |
codificado :: String -> String
tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,
codificado "todoparanada" == "nptaaodrdaao"
codificado "nptaaodrdaao" == "danaopadtora"
codificado "danaopadtora" == "todoparanada"
codificado "entodolamedida" == "dmdeaeondltiao" |
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
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) |
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)
Se puede imprimir o compartir con
12 soluciones de “Codificación matricial”