Menu Close

Búsqueda en lista de listas de pares

José A. Alonso, ,

Enunciado

-- Definir la función
--    busca :: Eq a => a -> [[(a,b)]] -> [b]
-- tal que (busca x pss) es la lista de los segundos componentes de los
-- pares de la lista de listas de pares pss cuya primera componentes es
-- x. Por ejemplo,
--    busca 3 [[(3,4)],[(5,4),(3,2),(3,5)],[(4,1),(7,3)]] == [4,2,5]

Soluciones

-- 1ª solución:
busca :: Eq a => a -> [[(a,b)]] -> [b]
busca x pss = [y | ps <- pss, (z,y) <- ps, z == x]  
 
-- 2ª solución:
busca2 :: Eq a => a -> [[(a,b)]] -> [b]
busca2 x pss = [y | (z,y) <- concat pss, z == x]
Leer más →

Problema de las puertas

José A. Alonso, ,

Enunciado

-- Un hotel dispone de n habitaciones y n camareros. Los camareros
-- tienen la costumbre de cambiar de estado las puestas (es decir,
-- abrir las cerradas y cerrar las abiertas). El proceso es el
-- siguiente: 
--    * Inicialmente todas las puertas están cerradas. 
--    * El primer camarero cambia de estado las puertas de todas las
--      habitaciones. 
--    * El segundo cambia de estado de las puertas de las habitaciones
--      pares. 
--    * El tercero cambia de estado todas las puertas que son
--      múltiplos de 3. 
--    * El cuarto cambia de estado todas las puertas que son múltiplos
--      de 4 
--    * Así hasta que ha pasado el último camarero.
-- Por ejemplo, para n = 5
--    Pase    | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5
--    --------+----------+----------+----------+----------+---------
--    Inicial | Cerrada  | Cerrada  | Cerrada  | Cerrada  | Cerrada
--    Pase 1  | Abierta  | Abierta  | Abierta  | Abierta  | Abierta
--    Pase 2  | Abierta  | Cerrada  | Abierta  | Cerrada  | Abierta
--    Pase 3  | Abierta  | Cerrada  | Cerrada  | Cerrada  | Abierta
--    Pase 4  | Abierta  | Cerrada  | Cerrada  | Abierta  | Abierta
--    Pase 5  | Abierta  | Cerrada  | Cerrada  | Abierta  | Cerrada 
-- 
-- Los estados de las puertas se representan por el siguiente tipo de
-- datos 
--    data Estado = Abierta | Cerrada deriving Show
-- 
-- Definir la función
--    final :: Int -> [Estado]
-- tal que (final n) es la lista de los estados de las n puertas después
-- de que hayan pasado los n camareros. Por
-- ejemplo,
--    ghci> final 5
--    [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
--    ghci> final 7
--    [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]

Soluciones

-- 1ª solución
-- ===========
 
data Estado = Abierta | Cerrada 
              deriving (Eq, Show)
 
cambia Abierta = Cerrada
cambia Cerrada = Abierta
 
-- (inicial n) es el estado inicial para el problema de las n
-- habitaciones. Por ejemplo,
--    inicial 5  ==  [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada]
inicial :: Int -> [Estado]
inicial n = replicate n Cerrada
 
-- (pase k es) es la lista de los estados de las puertas después de pasar el
-- camarero k que las encuentra en los estados es. Por ejemplo,
--    ghci> pase 1 (inicial 5)
--    [Abierta,Abierta,Abierta,Abierta,Abierta]
--    ghci> pase 2 it
--    [Abierta,Cerrada,Abierta,Cerrada,Abierta]
--    ghci> pase 3 it
--    [Abierta,Cerrada,Cerrada,Cerrada,Abierta]
--    ghci> pase 4 it
--    [Abierta,Cerrada,Cerrada,Abierta,Abierta]
--    ghci> pase 5 it
--    [Abierta,Cerrada,Cerrada,Abierta,Cerrada]
pase :: [Estado] -> Int -> [Estado] 
pase es k = zipWith cambiaK  es[1..] 
  where cambiaK e n | n `mod` k == 0 = cambia e
                    | otherwise      = e
 
final :: Int -> [Estado]
final n = aux [1..n] (inicial n) 
    where aux []     es = es  
          aux (k:ks) es = aux ks (pase es k)
 
-- 2ª solución (con foldl')
-- ========================
 
final2 :: Int -> [Estado]
final2 n = foldl pase (inicial n) [1..n] 
 
-- 3ª definición (basada en los cambios de cada posición)
-- ======================================================
 
final3 :: Int -> [Estado]
final3 n = map f [1..n]
    where f x | even (length (divisores x)) = Cerrada
              | otherwise                   = Abierta
 
divisores :: Int -> [Int]
divisores n = [x| x <- [1..n], n `mod` x == 0]
 
-- 4ª definición (basada en posiciones de abiertas)
-- ================================================
 
-- En primer lugar, vamos a determinar la lista de las posiciones
-- (comenzando a contar en 1) de las puertas que quedan abierta en el
-- problema de las n puertas. 
posicionesAbiertas :: Int -> [Int]
posicionesAbiertas n = 
    [x | (x,y) <- zip [1..] (final n), y == Abierta]
 
-- Al calcularlas,
--    ghci> posicionesAbiertas 200
--    [1,4,9,16,25,36,49,64,81,100,121,144,169,196]
-- Se observa las que quedan abiertas son las que sus posiciones son
-- cuadrados perfectos. Usando esta observación se construye la
-- siguiente definición
 
final4 :: Int -> [Estado]
final4 n = aux [1..n] [k*k | k <- [1..]] 
    where aux (x:xs) (y:ys) | x == y  =  Abierta : aux xs ys
          aux (x:xs) ys               =  Cerrada : aux xs ys
          aux []     _                =  []
Leer más →

Llanuras de longitud dada

José A. Alonso, ,

Enunciado

-- Una llanura de longitud n de una lista xs es una sublista de xs
-- formada por n elementos iguales.
--
-- Definir la función
--    llanuras :: Eq a => Int -> [a] -> [[a]]
-- tal que (llanuras n xs) es la lista de las llanuras de xs que tienen
-- n elementos como mínimo. Por ejemplo,
--    llanuras 3 "aabbbcddddffxffxx"  ==  ["bbb","dddd"]

Soluciones

import Data.List (group)
import Test.QuickCheck
 
-- 1ª definición (por comprensión):
llanuras :: Eq a => Int -> [a] -> [[a]]
llanuras n xs = [ys | ys <- group xs, length ys >= n] 
 
-- 2ª definición (por recursión con takeWhile y dropWhile):
llanuras2 :: Eq a => Int -> [a] -> [[a]]
llanuras2 _ [] = []
llanuras2 n xs@(x:_) 
    | length ys >= n = ys : llanuras2 n (dropWhile (x==) xs) 
    | otherwise      = llanuras2 n (dropWhile (x==) xs) 
    where ys = takeWhile (x==) xs
 
-- 3ª definición (por recursión con span):
llanuras3 :: Eq a => Int -> [a] -> [[a]]
llanuras3 _ [] = []
llanuras3 n xs@(x:_) 
    | length ys >= n = ys : llanuras3 n zs
    | otherwise      = llanuras3 n zs
    where (ys,zs) = span (x==) xs
 
-- 4ª definición (por recursión con span):
llanuras4 :: Eq a => Int -> [a] -> [[a]]
llanuras4 n = aux where
    aux [] = []
    aux xs@(x:_) | length ys >= n = ys : llanuras4 n zs
                 | otherwise      = llanuras4 n zs
                 where (ys,zs) = span (x==) xs
 
-- ---------------------------------------------------------------------
-- § Verificación                                                     --
-- ---------------------------------------------------------------------
 
-- Las definiciones son equivalentes
prop_equivalencia :: Int -> [Int] -> Bool
prop_equivalencia n xs =
    llanuras2 n xs == ys &&
    llanuras3 n xs == ys
    where ys = llanuras n xs
 
-- La comprobación es
--    ghci> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

Referencias

Esté ejercicio está basado en el problema Llanura de números iguales con longitud igual a n propuesto Solveet!

Leer más →

Expresiones vectoriales

José A. Alonso, ,

Enunciado

-- El siguiente tipo de dato define representa las expresiones
-- vectoriales formadas por un vector, la suma de dos expresiones
-- vectoriales o el producto de un entero por una expresión vectorial. 
--    data ExpV = Vec Int Int
--              | Sum ExpV ExpV
--              | Mul Int ExpV
--              deriving Show
-- 
-- Definir la función 
--    valor :: ExpV -> (Int,Int)
-- tal que (valor e) es el valor de la expresión vectorial c. Por
-- ejemplo, 
--    valor (Vec 1 2)                                  ==  (1,2)
--    valor (Sum (Vec 1 2 ) (Vec 3 4))                 ==  (4,6)
--    valor (Mul 2 (Vec 3 4))                          ==  (6,8)
--    valor (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4)))         ==  (8,12)
--    valor (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4)))  ==  (8,12)
data ExpV = Vec Int Int
          | Sum ExpV ExpV
          | Mul Int ExpV
          deriving Show
 
-- 1ª solución
-- ===========
valor :: ExpV -> (Int,Int)
valor (Vec x y)   = (x,y)
valor (Sum e1 e2) = (x1+x2,y1+y2) where (x1,y1) = valor e1  
                                        (x2,y2) = valor e2  
valor (Mul n e)   = (n*x,n*y) where (x,y) = valor e  
 
-- 2ª solución
-- ===========
valor2 :: ExpV -> (Int,Int)
valor2 (Vec a b)   = (a, b)
valor2 (Sum e1 e2) = suma (valor2 e1) (valor2 e2)
valor2 (Mul n e1)  = multiplica n (valor2 e1)
 
suma :: (Int,Int) -> (Int,Int) -> (Int,Int)
suma (a,b) (c,d) = (a+c,b+d)
 
multiplica :: Int -> (Int, Int) -> (Int, Int)
multiplica n (a,b) = (n*a,n*b)
Leer más →

Expresiones aritmética normalizadas

José A. Alonso, ,

Enunciado

-- El siguiente tipo de dato representa expresiones construidas con
-- variables, sumas y productos
--    data Expr = V String
--              | S Expr Expr
--              | P Expr Expr
-- Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z"))) 
-- 
-- Una expresión es un término si es un producto de variables. Por
-- ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.
--
-- Una expresión está en forma normal si es una suma de términos. Por
-- ejemplo, x*(y*z) y x+(y*z) está en forma normal; pero x*(y+z) y
-- (x+y)*(x+z) no lo están. 
-- 
-- Definir las funciones 
--    esTermino, esNormal :: Expr -> Bool
-- tales que
-- + (esTermino a) se verifica si a es un término. Por ejemplo,
--      esTermino (V "x")                                    == True
--      esTermino (P (V "x") (P (V "y") (V "z")))            == True
--      esTermino (P (V "x") (S (V "y") (V "z")))            == False
--      esTermino (S (V "x") (P (V "y") (V "z")))            == False
-- + (esNormal a) se verifica si a está en forma normal. Por ejemplo,
--      esNormal (V "x")                                     == True
--      esNormal (P (V "x") (P (V "y") (V "z")))             == True
--      esNormal (S (V "x") (P (V "y") (V "z")))             == True
--      esNormal (P (V "x") (S (V "y") (V "z")))             == False
--      esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

Soluciones

data Expr = V String
          | S Expr Expr
          | P Expr Expr
 
esTermino :: Expr -> Bool
esTermino (V _)   = True
esTermino (S _ _) = False
esTermino (P a b) = esTermino a && esTermino b
 
esNormal :: Expr -> Bool
esNormal (S a b) = esNormal a && esNormal b
esNormal a       = esTermino a
Leer más →