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,
λ> final 5 [Abierta,Cerrada,Cerrada,Abierta,Cerrada] λ> 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, -- λ> pase 1 (inicial 5) -- [Abierta,Abierta,Abierta,Abierta,Abierta] -- λ> pase 2 it -- [Abierta,Cerrada,Abierta,Cerrada,Abierta] -- λ> pase 3 it -- [Abierta,Cerrada,Cerrada,Cerrada,Abierta] -- λ> pase 4 it -- [Abierta,Cerrada,Cerrada,Abierta,Abierta] -- λ> 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, -- λ> 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 -- -- --------------------------------------------------------------------- -- λ> last (final 1000) -- Cerrada -- (0.23 secs, 218727400 bytes) -- λ> last (final 2000) -- Cerrada -- (1.78 secs, 868883080 bytes) -- λ> last (final2 1000) -- Cerrada -- (0.08 secs, 218729392 bytes) -- λ> last (final2 2000) -- Cerrada -- (1.77 secs, 868948600 bytes) -- λ> last (final3 1000) -- Cerrada -- (0.01 secs, 1029256 bytes) -- λ> last (final3 2000) -- Cerrada -- (0.01 secs, 2121984 bytes) -- λ> last (final4 1000) -- Cerrada -- (0.01 secs, 1029328 bytes) -- λ> last (final4 2000) -- Cerrada -- (0.01 secs, 1578504 bytes) -- λ> last (final3 10000) -- Abierta -- (0.01 secs, 4670104 bytes) -- λ> last (final3 100000) -- Cerrada -- (0.09 secs, 38717032 bytes) -- λ> last (final3 1000000) -- Abierta -- (1.27 secs, 377100832 bytes) -- λ> last (final4 1000000) -- Abierta -- (1.41 secs, 273292448 bytes)