Ir al contenido principal

Anagramas


Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, mora y roma son anagramas de amor.

Definir la función

anagramas :: String -> [String] -> [String]

tal que (anagramas x ys) es la lista de los elementos de ys que son anagramas de x. Por ejemplo,

λ> anagramas "amor" ["Roma","mola","loma","moRa", "rama"]
["Roma","moRa"]
λ> anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"]
["aMar","aRma"]

Soluciones

import Data.List (sort)
import Data.Char (toLower)
import Data.Function (on)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

-- 1ª solución
-- ===========

anagramas1 :: String -> [String] -> [String]
anagramas1 _ [] = []
anagramas1 x (y:ys) | sonAnagramas1 x y = y : anagramas1 x ys
                    | otherwise         = anagramas1 x ys

-- (sonAnagramas1 xs ys) se verifica si xs e ys son anagramas. Por
-- ejemplo,
--    sonAnagramas1 "amor" "Roma"  ==  True
--    sonAnagramas1 "amor" "mola"  ==  False
sonAnagramas1 :: String -> String -> Bool
sonAnagramas1 xs ys =
  sort (map toLower xs) == sort (map toLower ys)

-- 2ª solución
-- ===========

anagramas2 :: String -> [String] -> [String]
anagramas2 _ [] = []
anagramas2 x (y:ys) | sonAnagramas2 x y = y : anagramas2 x ys
                    | otherwise         = anagramas2 x ys

sonAnagramas2 :: String -> String -> Bool
sonAnagramas2 xs ys =
  (sort . map toLower) xs == (sort . map toLower) ys

-- 3ª solución
-- ===========

anagramas3 :: String -> [String] -> [String]
anagramas3 _ [] = []
anagramas3 x (y:ys) | sonAnagramas3 x y = y : anagramas3 x ys
                    | otherwise         = anagramas3 x ys

sonAnagramas3 :: String -> String -> Bool
sonAnagramas3 = (==) `on` (sort . map toLower)

-- Nota. En la solución anterior se usa la función on ya que
--    (f `on` g) x y
-- es equivalente a
--    f (g x) (g y)
-- Por ejemplo,
--    λ> ((*) `on` (+2)) 3 4
--    30

-- 4ª solución
-- ===========

anagramas4 :: String -> [String] -> [String]
anagramas4 x ys = [y | y <- ys, sonAnagramas1 x y]

-- 5ª solución
-- ===========

anagramas5 :: String -> [String] -> [String]
anagramas5 x = filter (`sonAnagramas1` x)

-- 6ª solución
-- ===========

anagramas6 :: String -> [String] -> [String]
anagramas6 x = filter (((==) `on` (sort . map toLower)) x)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: (String -> [String] -> [String]) -> Spec
specG anagramas = do
  it "e1" $
    anagramas "amor" ["Roma","mola","loma","moRa", "rama"] `shouldBe`
      ["Roma","moRa"]
  it "e2" $
    anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"] `shouldBe`
      ["aMar","aRma"]

spec :: Spec
spec = do
  describe "def. 1" $ specG anagramas1
  describe "def. 2" $ specG anagramas2
  describe "def. 3" $ specG anagramas3
  describe "def. 4" $ specG anagramas4
  describe "def. 5" $ specG anagramas5
  describe "def. 6" $ specG anagramas6

-- La verificación es
--    λ> verifica
--    12 examples, 0 failures

-- Comprobación de equivalencia
-- ============================

-- Genera un carácter. Por ejemplo.
--    λ> sample genCaracter
--    'b'
--    'O'
--    'Y'
--    't'
--    'B'
--    'm'
--    'S'
--    'z'
--    'e'
--    'c'
--    'c'
genCaracter :: Gen Char
genCaracter = elements (['a'..'z'] ++ ['A'..'Z'])

-- Genera una palabra. Por ejemplo.
--    λ> sample genPalabra
--    ""
--    "U"
--    ""
--    ""
--    "SBNrDsv"
--    "L"
--    ""
--    "WEbZepkEMiOT"
--    "TPC"
--    "MQKbhuiOSoiLhGKc"
--    "TTUujizoQZxLtyKTH"
genPalabra :: Gen String
genPalabra = listOf genCaracter

-- Genera una lista de palabras.
genPalabras :: Gen [String]
genPalabras = listOf genPalabra

-- Propiedad con generador personalizado
prop_equivalencia :: Property
prop_equivalencia =
  forAll genPalabra $ \x ->
  forAll genPalabras $ \ys ->
  all (== anagramas1 x ys)
      [anagramas2 x ys,
       anagramas3 x ys,
       anagramas4 x ys,
       anagramas5 x ys,
       anagramas6 x ys]

-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.
--    (0.16 secs, 240,359,144 bytes)