Menu Close

Codificación matricial

José A. Alonso,

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

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"

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)
Medio
, , , , , , , , , , , , ,

12 soluciones de “Codificación matricial”

  1. Responder
    cescarde 
    import Data.Matrix as M
 
codificado :: String -> String
codificado xs = elimina $ rotaYForma $ b
           where a = rellena xs
                 b = divide a (cu (genericLength a))
 
square :: [Integer]
square = [x^2 | x <- [1..]]
 
eligeNum :: String -> Integer
eligeNum xs = head (dropWhile (<t) square)
         where t = genericLength xs
 
--Añade '*'
rellena :: String -> String
rellena xs = xs ++ replicate (f c) '*'
        where c = eligeNum xs - genericLength xs
              f = fromInteger
--Divide la lista
divide :: String -> Integer -> [String]
divide [] _  = []
divide xs x = take (f x) xs : divide (drop (f x) xs) x
       where f = fromInteger
 
cu :: Integer -> Integer
cu x = round $ sqrt (fromInteger x)
 
rotaYForma :: [[a]] -> [a]
rotaYForma = concat.map reverse.toLists.(M.transpose).fromLists
 
elimina :: String -> String
elimina [] = []
elimina (x:xs) | x == '*' = elimina xs
               | otherwise = x: elimina xs
    • Responder
      cescarde 
      --Una posible mejora (?)
--------------------------------------
import Data.Matrix as M
 
codificado :: String -> String
codificado = del.rota.divide.parElector
           where del = filter (/='*')
                 rota = concatMap reverse.
                        toLists.(M.transpose).fromLists
 
eligeNum :: String -> Integer
eligeNum xs = head (dropWhile (<t) squares)
         where t = genericLength xs
               squares = [x^2 | x <- [1..]]
 
--Forma el par compuesto por la cadena con '*' y el orden de la
--matriz que formaría
 
parElector :: String -> (String,Integer) 
parElector xs = (t, cu $ g t)
           where t = add xs
                 g = genericLength
                 cu = round.sqrt.fromInteger
 
--Añade '*'
 
add :: String -> String
add xs = xs ++ replicate (f c) '*'
        where c = eligeNum xs - genericLength xs
              f = fromInteger
 
divide :: (String,Integer) -> [String]
divide ([],x) = []
divide (xs,x) = take (f x) xs : divide (drop (f x) xs, x)
       where f = fromInteger
  2. Responder
    enrnarbej 
    codificado :: String -> String
codificado xs = (filter (/= '*')
              .  concatMap reverse
              .  M.toLists
              .  M.transpose
              .  M.fromLists
              .  agrupa n) (xs ++ replicate (n^2-length xs) '*')
              where
               n = (ceiling . sqrt . genericLength) xs
 
agrupa :: Int -> String -> [String]
agrupa _ [] = []
agrupa n xs = take n xs : agrupa n (drop n xs)
  3. Responder
    albcercid 
    codificado :: String -> String
codificado xs = descodifica.toList.rota.tb $ (codifica (length xs) 1 xs)
codifica a b xs | a > b^2 = codifica a (b+1) xs
                | otherwise = (b,xs ++ replicate (b^2-a) '*')
tb (a,l) = fromList a a l
descodifica [] = []
descodifica (x:xs) | x == '*' = descodifica xs
                   | otherwise = x:descodifica xs
 
rota p = fromList n n [p !(j,n-i+1) | i <- reverse [1..n],
                                            j <- reverse [1..n]]
     where n = ncols p
  4. Responder
    antdursan 
    codificado :: String -> String
codificado xs = filter (/= '*') (reverse zs)
             where k = head [x | x <- [1..n], x^2 >= n]
                   asteriscos xs = xs ++ (replicate m '*')
                   n = length xs
                   m = k^2 - n
                   zs = toList (rota (fromList k k (asteriscos xs)))
                   rota = fromLists.reverse.toLists.transpose
  5. Responder
    marlobrip 
    import Data.Matrix
 
codificado :: String -> String
codificado xs = filter (/='*') (toList (rota (matriz xs)))
         where rota = fromLists . map reverse . toLists . transpose
 
matriz xs = fromList n n (ins xs)
   where n = rC (menorCuadrado l)
         l = length xs
         rC n = head [x | x <- [1..], x^2 == n]
         ins xs = xs ++ replicate y '*'
         y = menorCuadrado l - l
 
menorCuadrado n = head xs
    where xs = dropWhile (<=n) cuadrados
          cuadrados = map (^2) [1..]
  6. Responder
    belbenzam, alvfercen 
    import Data.Matrix 
calcula cs = head [ n | n <- [0..], n ^ 2 >= length cs] 
asteriscos xs  = xs ++ replicate a '*'
  where a = calcula xs  ^ 2 - (length xs) 
matrixxx cs  = fromList (calcula cs) (calcula cs) (asteriscos cs)
rotar cs  = (fromLists (map (reverse) (toLists  (transpose (matrixxx cs) ))))
codificadoyaaa cs = filter (/= '*') (toList (rotar cs) )
  7. Responder
    glovizcas 
    codificado :: String -> String
codificado = elimAsteriscos . concat . toLists . rota . matrizOrdenada
 
menorCuadrado xs = head [ x | x <- [1..] , x^2 >= length xs]
 
asteriscos xs = xs ++ (replicate n '*')
      where n  = ((menorCuadrado xs)^2 - length xs)
 
matrizOrdenada xs = fromList k k (asteriscos xs)
  where k = menorCuadrado xs
 
rota  = fromLists . map reverse . toLists . transpose
 
elimAsteriscos xs = filter (/= '*') xs
  8. Responder
    natruipin 
    buscamincuadrado x  =head(dropWhile ( f x) ( map (^2) [1..]))
 
f x y = x>=y^2 
 
 
añadir xs = xs++ replicate ((buscamincuadrado (length xs))^2- (length xs)) '*'
 
 
pasa xs = fromList p p (añadir xs)
  where p = buscamincuadrado (length xs)
 
rota a =  concatMap (reverse) (toLists(transpose (pasa a)))
 
suprimir [] = []
suprimir (x:xs) | x=='*' = suprimir xs
                | otherwise = x:suprimir (xs)
 
codifica = suprimir.rota
  9. Responder
    Juanjo Ortega (juaorture) 
    import Data.Array
 
entrada :: String -> String
entrada xs = xs ++ replicate ((n xs)^2 - length xs) '*'
 
rota :: Array (Int,Int) Char -> Array (Int,Int) Char
rota p = array ((1,1),(n,m)) [((i,j),p!(m-j+1,i)) | i <- [1..n], j <- [1..m]]
     where (m,n) = snd $ bounds p
 
matriz :: String -> Array (Int,Int) Char
matriz xs = listArray ((1,1),(a,a)) xs
       where a = n (borra '*' xs)
 
n :: String -> Int
n xs = head [ x | x <- [1..], x ^ 2 >= length xs] 
 
borra :: Eq a => a -> [a] -> [a]
borra n [] = []
borra n (x:xs) | x == n    = borra n xs
               | otherwise = x : borra n xs
 
codificado :: String -> String
codificado = borra '*' . elems . rota . matriz . entrada
  10. Responder
    marmerzaf - natmarmar2 
    long xs = length xs
 
mayN n = head [ x | x <- [ 1 ..n] , x^2> n]
resta  xs = (mayN (length xs))^2 - length xs
 
añade  xs = take (resta xs) (repeat "*")
 
lista xs = tail(init[ [x] | x <- show xs])
une xs =  concat (lista xs ++añade xs)
 
matriz xs = rota( fromList k k (une xs))
           where k = resta xs
 
codificado xs = elimAsteriscos( toList (matriz xs))
elimAsteriscos xs = filter (/= '*') xs
rota = fromLists . map reverse . toLists . M.transpose
  11. Responder
    marmerzaf 
    long xs = length xs
 
mayN n = head [ x | x <- [ 1 ..n] , x^2> n]
resta  xs = (mayN (length xs))^2 - length xs
 
añade  xs = take (resta xs) (repeat "*")
 
lista xs = tail(init[ [x] | x <- show xs])
une xs =  concat (lista xs ++añade xs)
 
matriz xs = rota( fromList k k (une xs))
           where k = resta xs
 
codificado xs = elimAsteriscos( toList (matriz xs))
elimAsteriscos xs = filter (/= '*') xs
rota = fromLists . map reverse . toLists . M.transpose

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.