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
|
1 2 3 4 5 6 7 |
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 |
data Estado = Abierta | Cerrada deriving 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
[schedule on=’2020-06-05′ at=»06:00″]
|
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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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) |
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>
5 Comentarios