Menu Close

Problema de las puertas

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)

Pensamiento

… cuánto exilio en la presencia cabe.

Antonio Machado

6 soluciones de “Problema de las puertas

  1. frahidzam
    data Estado = Abierta | Cerrada deriving Show
     
    final :: Int -> [Estado]
    final n = auxFinal (n+1) 2 (replicate n Abierta)
     
    auxFinal :: Int -> Int -> [Estado] -> [Estado]
    auxFinal n a xs | a <= n    = auxFinal n (a+1) (cambiaPuerta a xs)
                    | otherwise = xs
     
    cambiaPuerta :: Int -> [Estado] -> [Estado]
    cambiaPuerta n xs =
      cambiaEstados (zip [1..] xs)
                    [(a,niega b) | (a,b) <- zip [1..] xs,
                                   mod a n == 0 ,
                                   a /= 1]
     
    cambiaEstados [] xs = []
    cambiaEstados xs [] = [b | (a,b) <- xs]
    cambiaEstados ((a,b):xs) t@((c,d):ys)
      | a == c    = d : cambiaEstados xs ys
      | otherwise = b : cambiaEstados xs t
     
    niega Abierta = Cerrada
    niega Cerrada = Abierta
  2. adogargon
    data Estado = Abierta | Cerrada
      deriving Show
     
    final :: Int -> [Estado]
    final n = aux 1 (replicate n Cerrada)
      where aux k xs | n + 1 == k = xs
                     | otherwise  = aux (k+1) [ f (x,i) k | (x,i) <- zip xs [1..]]
              where  f (x,i) k | mod i k == 0 = opuesto x
                               | otherwise    = x
     
    opuesto :: Estado -> Estado
    opuesto Cerrada = Abierta
    opuesto Abierta = Cerrada
  3. luipromor
    final :: Int -> [Estado]
    final n = map snd $ aux 1 [(k,Cerrada) | k <- [1..n]]
      where aux a xs
              | n == a    = f a xs
              | otherwise = aux (a+1) $ f a xs
              where f _ [] = []
                    f a ((x,Abierta):xs)
                      | mod x a /= 0 = (x,Abierta) : f a xs
                      | otherwise    = (x,Cerrada) : f a xs
                    f a ((x,Cerrada):xs)
                      | mod x a /= 0 = (x,Cerrada) : f a xs
                      | otherwise    = (x,Abierta) : f a xs
  4. ireprirod
    final :: Int -> [Estado]
    final n = aux 1 n (replicate n Cerrada)
      where aux m n xs | m<n  = aux (m+1) n (selector m xs)
                       | m==n = selector m xs
     
    selector 1 xs = map cambia xs
    selector n xs = map g (zip xs [1..length xs]) 
      where g (a,b) | mod b n == 0 = cambia a
                    | otherwise    = a
     
    cambia :: Estado -> Estado
    cambia Abierta = Cerrada
    cambia Cerrada = Abierta
  5. javmarcha1
    final :: Int -> [Estado]
    final n = finalAux2 n (finalAux n)
      where divisores a = [b| b <- [1..a], rem a b == 0]
            finalAux2 c [] = []
            finalAux2 c (d:ds) | d==True = [Abierta]++finalAux2 c ds
                               | otherwise = [Cerrada]++finalAux2 c ds
            finalAux e =  [odd (length(divisores f)) | f <- [1..e]]
  6. estvegest
    final :: Int -> [Estado]
    final n = [estadoPuerta n x | x <- [1..n]]
    numEstadoPuerta :: Int -> Int -> Int
    numEstadoPuerta 0 _ = 0
    numEstadoPuerta n x | mod x n == 0 = 1 + numEstadoPuerta (n-1) x
                        | otherwise = numEstadoPuerta (n-1) x
    estadoPuerta :: Int -> Int -> Estado
    estadoPuerta n x | even (numEstadoPuerta n x) = Cerrada
                     | otherwise = Abierta

Escribe tu solución

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