null

Lista tautológica de literales

PorJosé A. Alonso 14-enero-201621-enero-2016

En lógica matemática, un literal http://bit.ly/1RQ5yJU es una fórmula atómica o su negación. Se puede definir por el tipo de dato

   data Literal = Atom String
                | Neg Literal
                deriving (Eq, Show)

data Literal = Atom String

| Neg Literal

deriving (Eq, Show)

Por ejemplo, el literal los literales p y ¬q se representan por las expresiones (Atom «p») y (Neg (Atom «q»)), respectivamente.

Una lista de literales (que se interpreta como su disyunción) es un tautología si contiene a una fórmula atómica y su negación.

Definir la función

   tautologia :: [Literal] -> Bool

1	tautologia :: [Literal] -> Bool

tal que (tautologia xs) se verifica si la lista de literales xs es una tautología. Por ejemplo,

   λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")]
   True
   λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")]
   False
   λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")]
   False

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")]

True

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")]

False

λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")]

False

Soluciones

[schedule expon=’2016-01-21′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 21 de enero.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2016-01-21′ at=»06:00″]

import Data.List (intersect)

data Literal = Atom String
             | Neg Literal
             deriving (Eq, Show)

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

tautologia1 :: [Literal] -> Bool
tautologia1 xs = or [elem x xs && elem (Neg x) xs | x <- xs]

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

tautologia2 :: [Literal] -> Bool
tautologia2 xs = 
    not (null (intersect ns (map neg ps)))
    where (ps,ns) = span esPositivo xs
          neg x   = Neg x

esPositivo :: Literal -> Bool
esPositivo (Atom _) = True
esPositivo _        = False

-- Comparación de eficiencia
-- =========================

--    λ> tautologia1 (replicate 4000 (Atom "p"))
--    False
--    (6.70 secs, 1031428 bytes)
--    λ> tautologia2 (replicate 4000 (Atom "p"))
--    False
--    (0.01 secs, 1061604 bytes)

import Data.List (intersect)

data Literal = Atom String

| Neg Literal

deriving (Eq, Show)

-- 1ª solución

-- ===========

tautologia1 :: [Literal] -> Bool

tautologia1 xs = or [elem x xs && elem (Neg x) xs | x <- xs]

-- 2ª solución

-- ===========

tautologia2 :: [Literal] -> Bool

tautologia2 xs =

not (null (intersect ns (map neg ps)))

where (ps,ns) = span esPositivo xs

neg x = Neg x

esPositivo :: Literal -> Bool

esPositivo (Atom _) = True

esPositivo _ = False

-- Comparación de eficiencia

-- =========================

-- λ> tautologia1 (replicate 4000 (Atom "p"))

-- False

-- (6.70 secs, 1031428 bytes)

-- λ> tautologia2 (replicate 4000 (Atom "p"))

-- False

-- (0.01 secs, 1061604 bytes)

[/schedule]

Elementos óptimos

PorJosé A. Alonso 31-diciembre-20157-enero-2016

Definir la función

   optimos :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]

1	optimos :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]

tal que (optimos r f xs) es la lista de los elementos de xs donde la función f alcanza sus valores óptimos respecto de la relación r. Por ejemplo,

   optimos (<) length ["ab","c","de","f"]  ==  ["c","f"]
   optimos (>) length ["ab","c","de","f"]  ==  ["ab","de"]

1 2	optimos (<) length ["ab","c","de","f"] == ["c","f"] optimos (>) length ["ab","c","de","f"] == ["ab","de"]

Soluciones

-- 1ª definición
-- =============

optimos1 :: Eq a => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]
optimos1 r f xs = 
    [x | x <- xs, null [y | y <- xs, x /= y, r (f y) (f x)]]

-- 2ª definición
-- =============

optimos2 :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]
optimos2 r f xs = [x | x <- xs, f x `elem` ms]
    where ms = maximales r (map f xs) 

-- (maximales r xs) es la lista de los elementos de xs para los que no
-- hay ningún otro elemento de xs mayor según la relación r. Por
-- ejemplo, 
--    maximales (>) [2,3,4,6]                     ==  [6]
--    maximales (<) [2,3,4,6]                     ==  [2]
--    maximales (\x y -> mod x y == 0) [2,3,4,6]  ==  [4,6]
--    maximales (\x y -> mod y x == 0) [2,3,4,6]  ==  [2,3]
maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a]
maximales r xs = [x | x <- xs, null [y | y <- xs, y /= x, r y x]]

-- Comparación de eficiencia
-- =========================

--    λ> length $ optimos1 (>) length [replicate n 'a' | n <- [1..1000]]
--    1
--    (16.74 secs, 153,957,400 bytes)
--    λ> length $ optimos2 (>) length [replicate n 'a' | n <- [1..1000]]
--    1
--    (0.64 secs, 85,520,896 bytes)

-- 1ª definición

-- =============

optimos1 :: Eq a => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]

optimos1 r f xs =

[x | x <- xs, null [y | y <- xs, x /= y, r (f y) (f x)]]

-- 2ª definición

-- =============

optimos2 :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]

optimos2 r f xs = [x | x <- xs, f x `elem` ms]

where ms = maximales r (map f xs)

-- (maximales r xs) es la lista de los elementos de xs para los que no

-- hay ningún otro elemento de xs mayor según la relación r. Por

-- ejemplo,

-- maximales (>) [2,3,4,6] == [6]

-- maximales (<) [2,3,4,6] == [2]

-- maximales (\x y -> mod x y == 0) [2,3,4,6] == [4,6]

-- maximales (\x y -> mod y x == 0) [2,3,4,6] == [2,3]

maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a]

maximales r xs = [x | x <- xs, null [y | y <- xs, y /= x, r y x]]

-- Comparación de eficiencia

-- =========================

-- λ> length $ optimos1 (>) length [replicate n 'a' | n <- [1..1000]]

-- 1

-- (16.74 secs, 153,957,400 bytes)

-- λ> length $ optimos2 (>) length [replicate n 'a' | n <- [1..1000]]

-- 1

-- (0.64 secs, 85,520,896 bytes)

Elementos maximales

PorJosé A. Alonso 30-diciembre-20157-enero-2016

Definir la función

   maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a]

1	maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a]

tal que (maximales r xs) es la lista de los elementos de xs para los que no hay ningún otro elemento de xs mayor según la relación r. Por ejemplo,

   maximales (>) [2,3,4,6]                     ==  [6]
   maximales (<) [2,3,4,6]                     ==  [2]
   maximales (\x y -> mod x y == 0) [2,3,4,6]  ==  [4,6]
   maximales (\x y -> mod y x == 0) [2,3,4,6]  ==  [2,3]

maximales (>) [2,3,4,6] == [6]

maximales (<) [2,3,4,6] == [2]

maximales (\x y -> mod x y == 0) [2,3,4,6] == [4,6]

maximales (\x y -> mod y x == 0) [2,3,4,6] == [2,3]

Soluciones

maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a]
maximales r xs = [x | x <- xs, null [y | y <- xs, y /= x, r y x]]

1 2	maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a] maximales r xs = [x \| x <- xs, null [y \| y <- xs, y /= x, r y x]]

Factorizable respecto de una lista

PorJosé A. Alonso 16-diciembre-201523-diciembre-2015

Definir la función

   factorizable :: Integer -> [Integer] -> Bool

1	factorizable :: Integer -> [Integer] -> Bool

tal que (factorizable x ys) se verifica si x se puede escribir como producto de potencias de elementos de ys. Por ejemplo,

   factorizable 1  [2,5,6]                           ==  True
   factorizable 12 [2,5,3]                           ==  True
   factorizable 12 [2,5,6]                           ==  True
   factorizable 12 [7,5,12]                          ==  True
   factorizable 12 [2,3,1]                           ==  True
   factorizable 12 [2,3,0]                           ==  True
   factorizable 24 [12,4,6]                          ==  True
   factorizable 0  [2,3,0]                           ==  True
   factorizable 12 [5,6]                             ==  False
   factorizable 12 [2,5,1]                           ==  False
   factorizable 0  [2,3,5]                           ==  False
   factorizable (product [1..3000])     [1..100000]  ==  True
   factorizable (1 + product [1..3000]) [1..100000]  ==  False

factorizable 1 [2,5,6] == True

factorizable 12 [2,5,3] == True

factorizable 12 [2,5,6] == True

factorizable 12 [7,5,12] == True

factorizable 12 [2,3,1] == True

factorizable 12 [2,3,0] == True

factorizable 24 [12,4,6] == True

factorizable 0 [2,3,0] == True

factorizable 12 [5,6] == False

factorizable 12 [2,5,1] == False

factorizable 0 [2,3,5] == False

factorizable (product [1..3000]) [1..100000] == True

factorizable (1 + product [1..3000]) [1..100000] == False

Soluciones

-- 1ª definición
factorizable1 :: Integer -> [Integer] -> Bool
factorizable1 1 _  = True
factorizable1 0 ys = 0 `elem` ys
factorizable1 x ys = 
    or [ factorizable1 (x `div` y) ys | y <- ys
                                       , y /= 0 && y /= 1
                                       , x `mod` y == 0 ]

-- 2ª definición
factorizable2 :: Integer -> [Integer] -> Bool
factorizable2 1 _  = True
factorizable2 0 ys = 0 `elem` ys
factorizable2 x ys = 
    aux x [y | y <- ys, y > 1, x `mod` y == 0]
    where aux _ [] = False
          aux 1 _  = True
          aux x ys | null zs   = False
                   | otherwise = or [aux (x `div` z) ys | z <- zs] 
                   where zs = [y | y <- ys, x `mod` y == 0]

-- 3ª definición
factorizable3 :: Integer -> [Integer] -> Bool
factorizable3 1 _  = True
factorizable3 0 ys = 0 `elem` ys
factorizable3 x ys = 
    aux x [y | y <- ys, y > 1, x `mod` y == 0]
    where aux _ [] = False
          aux 1 _  = True
          aux x (y:ys) 
              | rem x y == 0 = aux (div x y) (y:ys) || aux x ys
              | otherwise    = aux x ys

-- Comparación de eficiencia
-- =========================

--    λ> factorizable1 (product [1..3000]) [1..100000]
--    True
--    (3.55 secs, 322,471,488 bytes)
--    λ> factorizable2 (product [1..3000]) [1..100000]
--    True
--    (2.46 secs, 274,024,832 bytes)
--    λ> factorizable3 (product [1..3000]) [1..100000]
--    True
--    (0.30 secs, 47,606,400 bytes)
--    
--    λ> factorizable1 (1 + product [1..3000]) [1..100000]
--    False
--    (2.41 secs, 147,221,760 bytes)
--    λ> factorizable2 (1 + product [1..3000]) [1..100000]
--    False
--    (0.45 secs, 40,472,168 bytes)
--    λ> factorizable3 (1 + product [1..3000]) [1..100000]
--    False
--    (0.43 secs, 29,949,680 bytes)

-- 1ª definición

factorizable1 :: Integer -> [Integer] -> Bool

factorizable1 1 _ = True

factorizable1 0 ys = 0 `elem` ys

factorizable1 x ys =

or [ factorizable1 (x `div` y) ys | y <- ys

, y /= 0 && y /= 1

, x `mod` y == 0 ]

-- 2ª definición

factorizable2 :: Integer -> [Integer] -> Bool

factorizable2 1 _ = True

factorizable2 0 ys = 0 `elem` ys

factorizable2 x ys =

aux x [y | y <- ys, y > 1, x `mod` y == 0]

where aux _ [] = False

aux 1 _ = True

aux x ys | null zs = False

| otherwise = or [aux (x `div` z) ys | z <- zs]

where zs = [y | y <- ys, x `mod` y == 0]

-- 3ª definición

factorizable3 :: Integer -> [Integer] -> Bool

factorizable3 1 _ = True

factorizable3 0 ys = 0 `elem` ys

factorizable3 x ys =

aux x [y | y <- ys, y > 1, x `mod` y == 0]

where aux _ [] = False

aux 1 _ = True

aux x (y:ys)

| rem x y == 0 = aux (div x y) (y:ys) || aux x ys

| otherwise = aux x ys

-- Comparación de eficiencia

-- =========================

-- λ> factorizable1 (product [1..3000]) [1..100000]

-- True

-- (3.55 secs, 322,471,488 bytes)

-- λ> factorizable2 (product [1..3000]) [1..100000]

-- True

-- (2.46 secs, 274,024,832 bytes)

-- λ> factorizable3 (product [1..3000]) [1..100000]

-- True

-- (0.30 secs, 47,606,400 bytes)

-- λ> factorizable1 (1 + product [1..3000]) [1..100000]

-- False

-- (2.41 secs, 147,221,760 bytes)

-- λ> factorizable2 (1 + product [1..3000]) [1..100000]

-- False

-- (0.45 secs, 40,472,168 bytes)

-- λ> factorizable3 (1 + product [1..3000]) [1..100000]

-- False

-- (0.43 secs, 29,949,680 bytes)

Dígitos visibles y ocultos

PorJosé A. Alonso 16-noviembre-201526-marzo-2022

Una cadena clave es una cadena que contiene dígitos visibles y ocultos. Los dígitos se ocultan mediante las primeras letras minúsculas: la ‘a’ oculta el ‘0’, la ‘b’ el ‘1’ y así sucesivamente hasta la ‘j’ que oculta el ‘9’. Los restantes símbolos de la cadena no tienen significado y se pueden ignorar.

Definir la función

   numeroOculto :: String -> Maybe Integer

1	numeroOculto :: String -> Maybe Integer

tal que (numeroOculto cs) es justo el número formado por los dígitos visibles u ocultos de la cadena clave cs, si cs tiene dígitos y Nothing en caso contrario. Por ejemplo,

   numeroOculto "jihgfedcba"            ==  Just 9876543210
   numeroOculto "JIHGFEDCBA"            ==  Nothing
   numeroOculto "el 23 de Enero"        ==  Just 423344
   numeroOculto "El 23 de Enero"        ==  Just 23344
   numeroOculto "El 23 de enero"        ==  Just 233444
   numeroOculto "Todo para nada"        ==  Just 300030
   numeroOculto (replicate (10^6) 'A')  ==  Nothing

numeroOculto "jihgfedcba" == Just 9876543210

numeroOculto "JIHGFEDCBA" == Nothing

numeroOculto "el 23 de Enero" == Just 423344

numeroOculto "El 23 de Enero" == Just 23344

numeroOculto "El 23 de enero" == Just 233444

numeroOculto "Todo para nada" == Just 300030

numeroOculto (replicate (10^6) 'A') == Nothing

Soluciones

import Data.Char (isDigit, ord, chr)

numeroOculto :: String -> Maybe Integer
numeroOculto cs | null aux  = Nothing
                | otherwise = Just (read aux)
    where aux = filter isDigit (map visible cs)

visible :: Char -> Char
visible c | c `elem` ['a'..'j'] = chr (ord c - n)
          | otherwise           = c
          where n = ord 'a' - ord '0'

import Data.Char (isDigit, ord, chr)

numeroOculto :: String -> Maybe Integer

numeroOculto cs | null aux = Nothing

| otherwise = Just (read aux)

where aux = filter isDigit (map visible cs)

visible :: Char -> Char

visible c | c `elem` ['a'..'j'] = chr (ord c - n)

| otherwise = c

where n = ord 'a' - ord '0'

Lista tautológica de literales

Soluciones

Elementos óptimos

Soluciones

Elementos maximales

Soluciones

Factorizable respecto de una lista

Soluciones

Dígitos visibles y ocultos

Soluciones

Entradas recientes

Buscar

Correo electrónico