Menu Close

Problema de las puertas

José A. Alonso,

Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (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
-- ===========
 
final2 :: Int -> [Estado]
final2 n = foldl pase (inicial n) [1..n] 
 
-- 3ª solució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ª solución
-- ===========
 
-- 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 []     _                =  []
 
-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------
 
--    ghci> last (final 1000)
--    Cerrada
--    (0.23 secs, 218727400 bytes)
--    ghci> last (final 2000)
--    Cerrada
--    (1.78 secs, 868883080 bytes)
--    ghci> last (final2 1000)
--    Cerrada
--    (0.08 secs, 218729392 bytes)
--    ghci> last (final2 2000)
--    Cerrada
--    (1.77 secs, 868948600 bytes)
--    ghci> last (final3 1000)
--    Cerrada
--    (0.01 secs, 1029256 bytes)
--    ghci> last (final3 2000)
--    Cerrada
--    (0.01 secs, 2121984 bytes)
--    ghci> last (final4 1000)
--    Cerrada
--    (0.01 secs, 1029328 bytes)
--    ghci> last (final4 2000)
--    Cerrada
--    (0.01 secs, 1578504 bytes)
--    ghci> last (final3 10000)
--    Abierta
--    (0.01 secs, 4670104 bytes)
--    ghci> last (final3 100000)
--    Cerrada
--    (0.09 secs, 38717032 bytes)
--    ghci> last (final3 1000000)
--    Abierta
--    (1.27 secs, 377100832 bytes)
--    ghci> last (final4 1000000)
--    Abierta
--    (1.41 secs, 273292448 bytes)

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Medio
, , , ,

5 soluciones de “Problema de las puertas”

  1. Responder
    Enrique Zubiría 
    data Estado = Abierta | Cerrada deriving Show
 
final :: Int -> [Estado]
final n = pase 1 [Cerrada | k <- [1..n]]
  where pase m es
          | m < n = pase (m+1)
                         [ if rem k m == 0
                           then cambiaEstado (es!!(k-1))
                           else es!!(k-1) | k <- [1..n]]
          | otherwise = [ if rem k m == 0
                          then cambiaEstado (es!!(k-1))
                          else es!!(k-1) | k <- [1..n]]
        cambiaEstado Abierta = Cerrada
        cambiaEstado Cerrada = Abierta
  2. Responder
    fercarnav 
    data Estado = Abierta | Cerrada deriving Show
 
final :: Int -> [Estado]
final y = cambio 1 1 y (replicate y Cerrada)
 
cambio :: Int -> Int-> Int -> [Estado] -> [Estado]
cambio n a y (x:xs)
  | a == y+1       = x:xs
  | n == y+1       = cambio 1 (a+1) y (x:xs) 
  | a*div n a == n = cambio (n+1) a y (xs++[cambiaEstado x])
  | otherwise      = cambio (n+1) a y (xs++[x])
 
cambiaEstado :: Estado -> Estado
cambiaEstado Cerrada = Abierta
cambiaEstado Abierta = Cerrada
  3. Responder
    anthormol 
    data Estado = Abierta | Cerrada deriving Show
 
final :: Int -> [Estado]
final n = aux (zip (replicate n Cerrada) [1..]) [1..n]
    where aux ys []     = map fst ys
          aux ys (x:xs) = aux (f x ys) xs
          f _ [] = []
          f x (y:ys)
            | mod (snd y) x == 0 = [(cambia (fst y), snd y)] ++ (f x ys)
            | otherwise          = [y] ++ (f x ys)
 
cambia :: Estado -> Estado
cambia Abierta = Cerrada
cambia Cerrada = Abierta
  4. Responder
    juabaerui 
    data Estado = Abierta | Cerrada deriving (Show, Eq)
 
final :: Int -> [Estado]
final n = aux n 1 (replicate n Cerrada)
  where aux n k xs | k <= n    = aux n (k+1) (cambio k xs)
                   | otherwise = xs
 
cambio :: Int ->  [Estado] -> [Estado]
cambio n xs = reverse $ aux n xs 1 []
  where aux n [] k ys = ys
        aux n (x:xs) k ys | mod k n == 0 = aux n xs (k+1) (cambiaEstado x:ys)
                          | otherwise    = aux n xs (k+1) (x:ys)
        cambiaEstado Abierta = Cerrada
        cambiaEstado Cerrada = Abierta
  5. Responder
    rebgongor 
    data Estado = Abierta | Cerrada deriving Show
 
final :: Int -> [Estado]
final 0 = []
final n = Abierta : aux 2 n
  where aux k n | k > n     = []
                | even l    = Abierta : xs
                | otherwise = Cerrada : xs
          where l = length (filter (x -> rem k x == 0) [2..n])
                xs = aux (k+1) n

Escribe tu solución

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