El problema de las puertas en Haskell

En Gaussianos han comentado esta semana El problema de las 100 puertas y los divisores de un número natural cuyo enunciado es el siguiente

Supongamos que tenemos n puertas numeradas del 1 al n que están todas cerradas. Realizaremos, para cada puerta, el siguiente proceso: cambiar de estado todas las puertas cuyo número sea múltiplo de la puerta en la que estemos en ese momento. El problema consiste en caracterizar las puertas que quedan abierta al final del proceso.

Por ejemplo, supongamos que n=5 y usamos A para indicar que la puerta está abierta y C para indicar que está cerrada.

Inicialmente, nos encontramos en la posición 1 y el estado de las puertas es CCCCC.
Cambiamos de estado todas las puertas que tienen como número un múltiplo de 1 (es decir, en este caso las abrimos todas, con lo que tenemos AAAAA) y aumentamos la posición a 2.
Cambiamos de estado todas las puertas que tienen como número un múltiplo de 2, (es decir, cerramos la 2 y la 4, con lo que tenemos ACACA) y aumentamos la posición a 3.
Cambiamos de estado todas las puertas que tienen como número un múltiplo de 3, (es decir, cerramos la 3, con lo que tenemos ACCCA) y aumentamos la posición a 4.
Cambiamos de estado todas las puertas que tienen como número un múltiplo de 4, (es decir, abrimos la 4, con lo que tenemos ACCAA) y aumentamos la posición a 5.
Cambiamos de estado todas las puertas que tienen como número un múltiplo de 4, (es decir, cerramos la 5, con lo que tenemos ACCAC).

En este ejemplo han quedado abiertas la puerta 1 y la puerta 4.

Basándome en este problema he escrito la siguiente relación de ejercicios de Haskell para la asignatura de Informática de 1º del Grado en Matemáticas

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir el tipo de dato Estado para representar las
-- posibles Estado de las puertas: A (abierta) o C (cerrada).
-- ---------------------------------------------------------------------

data Estado = A | C deriving (Eq, Show)

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    opuesto :: Estado -> Estado
-- tal que (opuesto x) es el estado opuesto del estado x. 
-- ---------------------------------------------------------------------

opuesto :: Estado -> Estado
opuesto A = C
opuesto C = A

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir el tipo Puerta formado por el número de la
-- puerta y su estado.
-- ---------------------------------------------------------------------

type Puerta = (Int,Estado)

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir el tipo Situacion formado por un número (que la
-- posición actual; es decir, el número de la puerta que estamos
-- visitando) y una lista  de puertas. 
-- ---------------------------------------------------------------------

type Situacion = (Int,[Puerta])

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función 
--    situacionInicial :: Int -> Situacion
-- tal que (situacionInicial n) es el situación inicial del problema de
-- las n puertas; es decir, la posición actual es 1 y las n puertas
-- están cerradas. Por ejemplo,
--    ghci> SituacionInicial 5
--    (1,[(1,C),(2,C),(3,C),(4,C),(5,C)])
-- ---------------------------------------------------------------------

situacionInicial :: Int -> Situacion
situacionInicial n = (1, zip [1..] (replicate n C))

-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir la función
--    esSituacionFinal :: Situacion -> Bool
-- tal que (esSituacionFinal e) se verifica si e es un situación final;
-- es decir, se han visitado todas las puertas. Por ejemplo,
--    ghci> esSituacionFinal (6,[(1,A),(2,C),(3,C),(4,A),(5,C)])
--    True
--    ghci> esSituacionFinal (5,[(1,A),(2,C),(3,C),(4,A),(5,A)])
--    False
-- ---------------------------------------------------------------------

esSituacionFinal :: Situacion -> Bool
esSituacionFinal (n,xs) = n > length xs

-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir la función
--    siguiente :: Situacion -> Situacion
-- tal que (siguiente e) es el situación obtenida cambiando de estado
-- todas las puertas cuyo número sea múltiplo de la posición actual y
-- aumentando en 1 dicha posición. Por ejemplo,
--    ghci> siguiente (2,[(1,A),(2,A),(3,A),(4,A),(5,A)])
--    (3,[(1,A),(2,C),(3,A),(4,C),(5,A)])
-- ---------------------------------------------------------------------

siguiente :: Situacion -> Situacion
siguiente (n,xs) =
    (n+1, [cambia (m,e') | (m,e') <- xs])
    where cambia (m,e') | m `rem` n == 0 = (m,opuesto e')
                        | otherwise      = (m,e') 

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir la función
--    puertas :: Int -> [Puerta]
-- tal que (puertas n) es la lista de las n puertas al final del
-- proceso. Por ejemplo, 
--    ghci> 
--    [(1,A),(2,C),(3,C),(4,A),(5,C),(6,C),(7,C),(8,C),(9,A),(10,C)]
-- ---------------------------------------------------------------------

puertas :: Int -> [Puerta]
puertas n = puertasAux (situacionInicial n)
    where 
      puertasAux e
          | esSituacionFinal e = snd e
          | otherwise          = puertasAux (siguiente e)

-- Otra forma de definirla (sin necesidad de esSituacionFinal es)
puertas' :: Int -> [Puerta]
puertas' n = snd ((iterate siguiente (situacionInicial n)) !! n)

-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir la función
--    puertasAbiertas :: Int -> [Int]
-- tal que (puertasAbiertas n) es la lista de los números de las puertas
-- que quedan abiertas al final del proceso. Por ejemplo,
--    ghci> puertasAbiertas 10
--    [1,4,9]
-- ---------------------------------------------------------------------

puertasAbiertas :: Int -> [Int]
puertasAbiertas n = [m | (m,x) <- puertas n, x == A]

-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir la función
--    prop_puertas :: Int -> Int -> Bool
-- tal que (prop_puertas a b) se verifica si, para todo número natural n
-- entre a y b, el conjunto de los números de las puertas abiertas del
-- problema de las n puertas es igual al conjunto de los cuadrados
-- perfectos menores o iguales que n. Por ejemplo,
--    ghci> prop_puertas 1 100
--    True
-- ---------------------------------------------------------------------

prop_puertas :: Int -> Int -> Bool
prop_puertas a b =
    and [puertasAbiertas n == [x^2 | x <- [1..cota n]] | n <- [a..b]]
    where cota n = floor (sqrt (fromIntegral n))

-- ---------------------------------------------------------------------
-- Ejercicio 10. Demostrar que para todo número natural n, el conjunto
-- de los números de las puertas abiertas del problema de las n puertas
-- es igual al conjunto de los cuadrados perfectos menores o iguales que
-- n. 
-- ---------------------------------------------------------------------

-- Leer una demostración en el artículo de Gaussianos.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir el tipo de dato Estado para representar las

-- posibles Estado de las puertas: A (abierta) o C (cerrada).

-- ---------------------------------------------------------------------

data Estado = A | C deriving (Eq, Show)

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir la función

-- opuesto :: Estado -> Estado

-- tal que (opuesto x) es el estado opuesto del estado x.

-- ---------------------------------------------------------------------

opuesto :: Estado -> Estado

opuesto A = C

opuesto C = A

-- ---------------------------------------------------------------------

-- Ejercicio 3. Definir el tipo Puerta formado por el número de la

-- puerta y su estado.

-- ---------------------------------------------------------------------

type Puerta = (Int,Estado)

-- ---------------------------------------------------------------------

-- Ejercicio 4. Definir el tipo Situacion formado por un número (que la

-- posición actual; es decir, el número de la puerta que estamos

-- visitando) y una lista de puertas.

-- ---------------------------------------------------------------------

type Situacion = (Int,[Puerta])

-- ---------------------------------------------------------------------

-- Ejercicio 5. Definir la función

-- situacionInicial :: Int -> Situacion

-- tal que (situacionInicial n) es el situación inicial del problema de

-- las n puertas; es decir, la posición actual es 1 y las n puertas

-- están cerradas. Por ejemplo,

-- ghci> SituacionInicial 5

-- (1,[(1,C),(2,C),(3,C),(4,C),(5,C)])

-- ---------------------------------------------------------------------

situacionInicial :: Int -> Situacion

situacionInicial n = (1, zip [1..] (replicate n C))

-- ---------------------------------------------------------------------

-- Ejercicio 6. Definir la función

-- esSituacionFinal :: Situacion -> Bool

-- tal que (esSituacionFinal e) se verifica si e es un situación final;

-- es decir, se han visitado todas las puertas. Por ejemplo,

-- ghci> esSituacionFinal (6,[(1,A),(2,C),(3,C),(4,A),(5,C)])

-- True

-- ghci> esSituacionFinal (5,[(1,A),(2,C),(3,C),(4,A),(5,A)])

-- False

-- ---------------------------------------------------------------------

esSituacionFinal :: Situacion -> Bool

esSituacionFinal (n,xs) = n > length xs

-- ---------------------------------------------------------------------

-- Ejercicio 6. Definir la función

-- siguiente :: Situacion -> Situacion

-- tal que (siguiente e) es el situación obtenida cambiando de estado

-- todas las puertas cuyo número sea múltiplo de la posición actual y

-- aumentando en 1 dicha posición. Por ejemplo,

-- ghci> siguiente (2,[(1,A),(2,A),(3,A),(4,A),(5,A)])

-- (3,[(1,A),(2,C),(3,A),(4,C),(5,A)])

-- ---------------------------------------------------------------------

siguiente :: Situacion -> Situacion

siguiente (n,xs) =

(n+1, [cambia (m,e') | (m,e') <- xs])

where cambia (m,e') | m `rem` n == 0 = (m,opuesto e')

| otherwise = (m,e')

-- ---------------------------------------------------------------------

-- Ejercicio 7. Definir la función

-- puertas :: Int -> [Puerta]

-- tal que (puertas n) es la lista de las n puertas al final del

-- proceso. Por ejemplo,

-- ghci>

-- [(1,A),(2,C),(3,C),(4,A),(5,C),(6,C),(7,C),(8,C),(9,A),(10,C)]

-- ---------------------------------------------------------------------

puertas :: Int -> [Puerta]

puertas n = puertasAux (situacionInicial n)

where

puertasAux e

| esSituacionFinal e = snd e

| otherwise = puertasAux (siguiente e)

-- Otra forma de definirla (sin necesidad de esSituacionFinal es)

puertas' :: Int -> [Puerta]

puertas' n = snd ((iterate siguiente (situacionInicial n)) !! n)

-- ---------------------------------------------------------------------

-- Ejercicio 8. Definir la función

-- puertasAbiertas :: Int -> [Int]

-- tal que (puertasAbiertas n) es la lista de los números de las puertas

-- que quedan abiertas al final del proceso. Por ejemplo,

-- ghci> puertasAbiertas 10

-- [1,4,9]

-- ---------------------------------------------------------------------

puertasAbiertas :: Int -> [Int]

puertasAbiertas n = [m | (m,x) <- puertas n, x == A]

-- ---------------------------------------------------------------------

-- Ejercicio 9. Definir la función

-- prop_puertas :: Int -> Int -> Bool

-- tal que (prop_puertas a b) se verifica si, para todo número natural n

-- entre a y b, el conjunto de los números de las puertas abiertas del

-- problema de las n puertas es igual al conjunto de los cuadrados

-- perfectos menores o iguales que n. Por ejemplo,

-- ghci> prop_puertas 1 100

-- True

-- ---------------------------------------------------------------------

prop_puertas :: Int -> Int -> Bool

prop_puertas a b =

and [puertasAbiertas n == [x^2 | x <- [1..cota n]] | n <- [a..b]]

where cota n = floor (sqrt (fromIntegral n))

-- ---------------------------------------------------------------------

-- Ejercicio 10. Demostrar que para todo número natural n, el conjunto

-- de los números de las puertas abiertas del problema de las n puertas

-- es igual al conjunto de los cuadrados perfectos menores o iguales que

-- n.

-- ---------------------------------------------------------------------

-- Leer una demostración en el artículo de Gaussianos.

Se puede imprimir o compartir con