{"id":1434,"date":"2011-07-03T10:28:38","date_gmt":"2011-07-03T10:28:38","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1434"},"modified":"2011-07-03T10:28:38","modified_gmt":"2011-07-03T10:28:38","slug":"el-problema-de-las-puertas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-problema-de-las-puertas-en-haskell\/","title":{"rendered":"El problema de las puertas en Haskell"},"content":{"rendered":"<p>En <a href=\"http:\/\/gaussianos.com\">Gaussianos<\/a> han comentado esta semana <a href=\"http:\/\/gaussianos.com\/el-problema-de-las-100-puertas-y-los-divisores-de-un-numero-natural\/\">El problema de las 100 puertas y los divisores de un n\u00famero natural<\/a> cuyo enunciado es el siguiente<\/p>\n<blockquote><p>\nSupongamos que tenemos n puertas numeradas del 1 al n que est\u00e1n todas  cerradas. Realizaremos, para cada puerta, el siguiente proceso: cambiar de estado todas las puertas cuyo n\u00famero sea m\u00faltiplo de la puerta en la que estemos en ese momento. El problema consiste en caracterizar las puertas que quedan abierta al final del proceso.<\/p>\n<p>Por ejemplo, supongamos que n=5 y usamos A para indicar que la puerta est\u00e1 abierta y C para indicar que est\u00e1 cerrada.<\/p>\n<ul>\n<li>Inicialmente, nos encontramos en la posici\u00f3n 1 y el estado de las puertas es CCCCC.\n<li>Cambiamos de estado todas las puertas que tienen como n\u00famero un m\u00faltiplo de 1 (es decir, en este caso las abrimos todas, con lo que tenemos AAAAA) y aumentamos la posici\u00f3n a 2.\n<li>Cambiamos de estado todas las puertas que tienen como n\u00famero un m\u00faltiplo de 2, (es decir, cerramos la 2 y la 4, con lo que tenemos ACACA) y aumentamos la posici\u00f3n a 3.\n<li>Cambiamos de estado todas las puertas que tienen como n\u00famero un m\u00faltiplo de 3, (es decir, cerramos la 3, con lo que tenemos ACCCA) y aumentamos la posici\u00f3n a 4.\n<li>Cambiamos de estado todas las puertas que tienen como n\u00famero un m\u00faltiplo de 4, (es decir, abrimos la 4, con lo que tenemos ACCAA) y aumentamos la posici\u00f3n a 5.\n<li>Cambiamos de estado todas las puertas que tienen como n\u00famero un m\u00faltiplo de 4, (es decir, cerramos la 5, con lo que tenemos ACCAC).\n<\/ul>\n<p>En este ejemplo han quedado abiertas la puerta 1 y la puerta 4.\n<\/p><\/blockquote>\n<p>Bas\u00e1ndome en este problema he escrito la siguiente relaci\u00f3n de ejercicios de Haskell para la asignatura de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a><br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir el tipo de dato Estado para representar las\r\n-- posibles Estado de las puertas: A (abierta) o C (cerrada).\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Estado = A | C deriving (Eq, Show)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    opuesto :: Estado -> Estado\r\n-- tal que (opuesto x) es el estado opuesto del estado x. \r\n-- ---------------------------------------------------------------------\r\n\r\nopuesto :: Estado -> Estado\r\nopuesto A = C\r\nopuesto C = A\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir el tipo Puerta formado por el n\u00famero de la\r\n-- puerta y su estado.\r\n-- ---------------------------------------------------------------------\r\n\r\ntype Puerta = (Int,Estado)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir el tipo Situacion formado por un n\u00famero (que la\r\n-- posici\u00f3n actual; es decir, el n\u00famero de la puerta que estamos\r\n-- visitando) y una lista  de puertas. \r\n-- ---------------------------------------------------------------------\r\n\r\ntype Situacion = (Int,[Puerta])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n \r\n--    situacionInicial :: Int -> Situacion\r\n-- tal que (situacionInicial n) es el situaci\u00f3n inicial del problema de\r\n-- las n puertas; es decir, la posici\u00f3n actual es 1 y las n puertas\r\n-- est\u00e1n cerradas. Por ejemplo,\r\n--    ghci> SituacionInicial 5\r\n--    (1,[(1,C),(2,C),(3,C),(4,C),(5,C)])\r\n-- ---------------------------------------------------------------------\r\n\r\nsituacionInicial :: Int -> Situacion\r\nsituacionInicial n = (1, zip [1..] (replicate n C))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    esSituacionFinal :: Situacion -> Bool\r\n-- tal que (esSituacionFinal e) se verifica si e es un situaci\u00f3n final;\r\n-- es decir, se han visitado todas las puertas. Por ejemplo,\r\n--    ghci> esSituacionFinal (6,[(1,A),(2,C),(3,C),(4,A),(5,C)])\r\n--    True\r\n--    ghci> esSituacionFinal (5,[(1,A),(2,C),(3,C),(4,A),(5,A)])\r\n--    False\r\n-- ---------------------------------------------------------------------\r\n\r\nesSituacionFinal :: Situacion -> Bool\r\nesSituacionFinal (n,xs) = n > length xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    siguiente :: Situacion -> Situacion\r\n-- tal que (siguiente e) es el situaci\u00f3n obtenida cambiando de estado\r\n-- todas las puertas cuyo n\u00famero sea m\u00faltiplo de la posici\u00f3n actual y\r\n-- aumentando en 1 dicha posici\u00f3n. Por ejemplo,\r\n--    ghci> siguiente (2,[(1,A),(2,A),(3,A),(4,A),(5,A)])\r\n--    (3,[(1,A),(2,C),(3,A),(4,C),(5,A)])\r\n-- ---------------------------------------------------------------------\r\n\r\nsiguiente :: Situacion -> Situacion\r\nsiguiente (n,xs) =\r\n    (n+1, [cambia (m,e') | (m,e') <- xs])\r\n    where cambia (m,e') | m `rem` n == 0 = (m,opuesto e')\r\n                        | otherwise      = (m,e') \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    puertas :: Int -> [Puerta]\r\n-- tal que (puertas n) es la lista de las n puertas al final del\r\n-- proceso. Por ejemplo, \r\n--    ghci> \r\n--    [(1,A),(2,C),(3,C),(4,A),(5,C),(6,C),(7,C),(8,C),(9,A),(10,C)]\r\n-- ---------------------------------------------------------------------\r\n\r\npuertas :: Int -> [Puerta]\r\npuertas n = puertasAux (situacionInicial n)\r\n    where \r\n      puertasAux e\r\n          | esSituacionFinal e = snd e\r\n          | otherwise          = puertasAux (siguiente e)\r\n\r\n-- Otra forma de definirla (sin necesidad de esSituacionFinal es)\r\npuertas' :: Int -> [Puerta]\r\npuertas' n = snd ((iterate siguiente (situacionInicial n)) !! n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    puertasAbiertas :: Int -> [Int]\r\n-- tal que (puertasAbiertas n) es la lista de los n\u00fameros de las puertas\r\n-- que quedan abiertas al final del proceso. Por ejemplo,\r\n--    ghci> puertasAbiertas 10\r\n--    [1,4,9]\r\n-- ---------------------------------------------------------------------\r\n\r\npuertasAbiertas :: Int -> [Int]\r\npuertasAbiertas n = [m | (m,x) <- puertas n, x == A]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir la funci\u00f3n\r\n--    prop_puertas :: Int -> Int -> Bool\r\n-- tal que (prop_puertas a b) se verifica si, para todo n\u00famero natural n\r\n-- entre a y b, el conjunto de los n\u00fameros de las puertas abiertas del\r\n-- problema de las n puertas es igual al conjunto de los cuadrados\r\n-- perfectos menores o iguales que n. Por ejemplo,\r\n--    ghci> prop_puertas 1 100\r\n--    True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_puertas :: Int -> Int -> Bool\r\nprop_puertas a b =\r\n    and [puertasAbiertas n == [x^2 | x <- [1..cota n]] | n <- [a..b]]\r\n    where cota n = floor (sqrt (fromIntegral n))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Demostrar que para todo n\u00famero natural n, el conjunto\r\n-- de los n\u00fameros de las puertas abiertas del problema de las n puertas\r\n-- es igual al conjunto de los cuadrados perfectos menores o iguales que\r\n-- n. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- Leer una demostraci\u00f3n en el art\u00edculo de Gaussianos.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En Gaussianos han comentado esta semana El problema de las 100 puertas y los divisores de un n\u00famero natural cuyo enunciado es el siguiente Supongamos que tenemos n puertas numeradas del 1 al n que est\u00e1n todas cerradas. Realizaremos, para cada puerta, el siguiente proceso: cambiar de estado todas las puertas cuyo n\u00famero sea m\u00faltiplo&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[270],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1434"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1434"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1434\/revisions"}],"predecessor-version":[{"id":1436,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1434\/revisions\/1436"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1434"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1434"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1434"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}