Codificación matricial

PorJosé A. Alonso 21-marzo-201729-marzo-2017

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

1	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)

12 Comentarios

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

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

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

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

Responder

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)

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)

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

Codificación matricial

Soluciones

12 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

12 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico