Menu Close

Acrónimos

José A. Alonso,

Introducción

A partir de una palabra de puede formar un acrónimo uniendo un prefijo de la primera con un sufijo de la segunda. Por ejemplo,

  • «ofimática» es un acrónimo de «oficina» e «informática»
  • «informática» es un acrónimo de «información» y «automática»
  • «teleñeco» es un acrónimo de «televisión» y «muñeco»

Enunciado

-- Definir la función
--    esAcronimo :: String -> String -> String -> Bool
-- tal que (esAcronimo xs ys zs) se verifica si xs es un acrónimo de ys
-- y zs. Por ejemplo,
--    esAcronimo "ofimatica" "oficina" "informatica"       ==  True
--    esAcronimo "informatica" "informacion" "automatica"  ==  True
import Data.List
import Test.QuickCheck
 
-- 1ª definición
-- =============
 
esAcronimo1 :: String -> String -> String -> Bool
esAcronimo1 xs ys zs =
    xs `elem` acronimos ys zs
 
-- (acronimos xs ys) es la lista de acrónimos de xs e ys. Por ejemplo,
--    ghci> acronimos "ab" "cde"
--    ["cde","de","e","","acde","ade","ae","a","abcde","abde","abe","ab"]
acronimos :: String -> String -> [String]
acronimos xs ys =
    [us++vs | us <- inits xs, vs <- tails ys]
 
-- 2ª definición
-- =============
 
esAcronimo2 :: String -> String -> String -> Bool
esAcronimo2 xs ys zs = 
    or [isPrefixOf us ys && isSuffixOf vs zs | 
        (us,vs) <- [splitAt n xs | n <- [0..length xs]]]
 
-- Verificación de equivalencia
-- ============================
 
-- La propiedad es
prop_esAcronimo :: String -> String -> String -> Bool
prop_esAcronimo xs ys zs =
    esAcronimo1 xs ys zs == esAcronimo2 xs ys zs
 
-- La comprobación es
--    ghci> quickCheck prop_esAcronimo
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    ghci> let r = replicate
--    
--    ghci> let n = 500 in esAcronimo1 (r n 'a' ++ r n 'b') (r n 'a') (r n 'b')
--    True
--    (3.76 secs, 1779334696 bytes)
--    
--    ghci> let n = 500 in esAcronimo2 (r n 'a' ++ r n 'b') (r n 'a') (r n 'b')
--    True
--    (0.04 secs, 16715376 bytes)
--
-- La 2ª definición es más eficiente
Posted in Medio
Tagged , , , , , , , ,

3 Comments

  1. Jesús Navas Orozco
    Responder 
    esAcronimo :: String -> String -> String -> Bool
esAcronimo xs ys zs = or [isPrefixOf s ys && isSuffixOf t zs | (s,t) <- l]
    where l = [splitAt n xs | n <- [0..length xs]]
  2. Eduardo Román
    Responder 
    esAcronimo :: String -> String -> String -> Bool
esAcronimo xs ys zs = 
    elem xs [take n ys ++ reverse (take (length xs-n) (reverse zs)) |
             n <- [1..length xs-1]]
  3. Pedro Martín Chávez
    Responder 
    esAcronimo :: String -> String -> String -> Bool
esAcronimo xs ys zs = 
    elem xs [bs++cs | (bs,cs) <- combinaciones xs,
                      bs `isPrefixOf` ys, cs `isSuffixOf` zs]
    where combinaciones xs = [splitAt n xs | n <- [0..length xs]]

Escribe tu solución

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