Problema de las puertas
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
|
1 2 3 4 5 6 7 8 |
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
|
1 2 |
data Estado = Abierta | Cerrada deriving (Eq, Show) |
Definir la función
|
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,
|
1 2 3 4 |
ghci> final 5 [Abierta,Cerrada,Cerrada,Abierta,Cerrada] ghci> final 7 [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
-- 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 [] _ = [] |