Menu Close

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