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

1	data Estado = Abierta \| Cerrada deriving Show

Definir la función

   final :: Int -> [Estado]

1	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]

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)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

-- 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 Comentarios

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

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

Responder

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

deriving Show

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

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

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

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

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

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]]

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]]

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

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

Problema de las puertas

Soluciones

Pensamiento

6 Comentarios

Leave a Reply to luipromorCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

6 Comentarios

Leave a Reply to luipromorCancel reply

Entradas recientes

Buscar

Correo electrónico