{"id":2431,"date":"2012-12-18T16:40:35","date_gmt":"2012-12-18T16:40:35","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2431"},"modified":"2013-03-16T08:02:33","modified_gmt":"2013-03-16T08:02:33","slug":"i1m2012-el-problema-de-las-numeros-bonitos-y-numeros-feos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-el-problema-de-las-numeros-bonitos-y-numeros-feos-en-haskell\/","title":{"rendered":"I1M2012: El problema de las n\u00fameros bonitos y n\u00fameros feos en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado la soluci\u00f3n con Haskell el desaf\u00edo matem\u00e1ticos <a href=\"http:\/\/goo.gl\/IOdGq\">N\u00fameros bonitos, n\u00fameros feos<\/a> publicado en EL PA\u00cdS con motivo del sorteo de la Loter\u00eda de Navidad. Su enunciado es<\/p>\n<blockquote><p>\nDesde el a\u00f1o 2011 en la Loter\u00eda Navidad se sortean los premios entre los cien mil n\u00fameros que van del 00000 al 99999 (en los d\u00e9cimos los n\u00fameros siempre se escriben con cinco cifras). Aunque todos los n\u00fameros tienen exactamente las mismas posibilidades de resultar premiados, con frecuencia se habla de n\u00fameros bonitos y n\u00fameros feos. Como es una valoraci\u00f3n est\u00e9tica, que un n\u00famero sea bonito o feo depende de los gustos de cada uno.<\/p>\n<p>En este caso un n\u00famero de loter\u00eda nos parecer\u00e1 bonito si cumple<br \/>\nexactamente una, y solamente una, de estas tres condiciones: <\/p>\n<ul>\n<li> a) es divisible entre 5,\n<li> b) da resto 2 al dividirlo entre 7,\n<li> c) la suma de sus cifras es divisible entre 9.\n<\/ul>\n<p>Por ejemplo, el 00037 es bonito porque cumple la condici\u00f3n b pero no las otras dos; sin embargo, el 00324 es feo, ya que cumple las condiciones b y c. De igual forma, podr\u00edamos decir que el 00041 y el 00450 son horribles. El primero, porque no cumple ninguna de las tres condiciones; y el segundo, porque es un exagerado y cumple las tres. <\/p>\n<p>El desaf\u00edo que se propone es decidir cu\u00e1ntos de los n\u00fameros que participan en el sorteo de Loter\u00eda de Navidad (recordad, del 00000 al 99999) son bonitos seg\u00fan el criterio expresado anteriormente.\n<\/p><\/blockquote>\n<p>A continuaci\u00f3n, se presentan 5 soluciones en Haskell y se comparan sus eficiencias.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Soluci\u00f3n 1                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La primera soluci\u00f3n es una traducci\u00f3n directa del enunciado.\r\n\r\n-- solucion1 es la soluci\u00f3n del problema.\r\nsolucion1 :: Int\r\nsolucion1 = \r\n    length [n | n <- [0..99999], \r\n                verificaUna n [condicionA, condicionB, condicionC]]\r\n\r\n-- (condicionA n) se verifica si n cumple la condici\u00f3n a; es decir, n es\r\n-- divisible entre 5. \r\ncondicionA :: Integer -> Bool\r\ncondicionA n = rem n 5 == 0\r\n\r\n-- (condicionB n) se verifica si n cumple la condici\u00f3n b; es decir, el\r\n-- resto de dividir n entre 7 es 2.\r\ncondicionB :: Integer -> Bool\r\ncondicionB n = rem n 7 == 2\r\n\r\n-- (condicionC n) se verifica si n cumple la condici\u00f3n c; es decir, la\r\n-- suma de sus cifras es divisible entre 9. \r\ncondicionC :: Integer -> Bool\r\ncondicionC n = rem (sumaCifras n) 9 == 0\r\n\r\n-- (sumaCifras n) es la suma de las cifras de n.\r\nsumaCifras :: Integer -> Integer\r\nsumaCifras n = sum [read [x] | x <- show n]\r\n\r\n-- (verificaUna n ps) se verifica si n cumple una, y s\u00f3lo una, de las\r\n-- propiedades ps.\r\nverificaUna :: Integer -> [Integer -> Bool] -> Bool\r\nverificaUna n ps = [p n | p <- ps, p n] == [True]\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> solucion1\r\n--    33016\r\n--    (11.90 secs, 1618646276 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Soluci\u00f3n 2                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- En esta soluci\u00f3n se modifica la condici\u00f3n c por su equivalente: n es\r\n-- m\u00faltiplo de 9.\r\n\r\nsolucion2 :: Int\r\nsolucion2 = \r\n    length [n | n <- [0..99999], \r\n                verificaUna n [condicionA, condicionB, condicionC2]]\r\n\r\n-- (condicionC2 n) se verifica si n cumple la condici\u00f3n c; es decir, es\r\n-- m\u00faltiplo de 9.\r\ncondicionC2 :: Integer -> Bool\r\ncondicionC2 n = rem n 9 == 0\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> solucion2\r\n--    33016\r\n--    (1.72 secs, 66504036 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Soluci\u00f3n 3                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Considerando los conjuntos que cumplen una, dos o tres de las\r\n-- condiciones. \r\n\r\nsolucion3 :: Int\r\nsolucion3 = \r\n    numero condicionA + numero condicionB + numero condicionC2 \r\n    - 2* (numero condicionAB + numero condicionAC + numero condicionBC) \r\n    + 3* numero condicionABC\r\n\r\n-- (condicion p) es el conjunto de elementos que cumplen la condicion\r\n-- p. Por ejemplo,\r\n--    ghci> take 10 (conjunto condicionA)\r\n--    [0,5,10,15,20,25,30,35,40,45]\r\n--    ghci> take 10 (conjunto condicionB)\r\n--    [2,9,16,23,30,37,44,51,58,65]\r\n--    ghci> take 10 (conjunto condicionC)\r\n--    [0,9,18,27,36,45,54,63,72,81]\r\n--    ghci> take 10 (conjunto condicionAB)\r\n--    [30,65,100,135,170,205,240,275,310,345]\r\n--    ghci> take 10 (conjunto condicionAC)\r\n--    [0,45,90,135,180,225,270,315,360,405]\r\n--    ghci> take 10 (conjunto condicionBC)\r\n--    [9,72,135,198,261,324,387,450,513,576]\r\n--    ghci> take 10 (conjunto condicionABC)\r\n--    [135,450,765,1080,1395,1710,2025,2340,2655,2970]\r\nconjunto p = [n | n <- [0..99999], p n]\r\n\r\n-- (condicionAB n) se verifica si n cumple las condiciones a y b.\r\ncondicionAB :: Integer -> Bool\r\ncondicionAB n = condicionA n && condicionB n\r\n\r\n-- (condicionAC n) se verifica si n cumple las condiciones a y c.\r\ncondicionAC :: Integer -> Bool\r\ncondicionAC n = condicionA n && condicionC2 n\r\n\r\n-- (condicionBC n) se verifica si n cumple las condiciones b y c.\r\ncondicionBC :: Integer -> Bool\r\ncondicionBC n = condicionB n && condicionC2 n\r\n\r\n-- (condicionABC n) se verifica si n cumple las condiciones a, b y c.\r\ncondicionABC :: Integer -> Bool\r\ncondicionABC n = condicionA n && condicionB n && condicionC2 n\r\n\r\n-- (numero p) es el n\u00famero de elementos que cumplen la condicion\r\n-- p. Por ejemplo,\r\n--    numero condicionA    ==  20000\r\n--    numero condicionB    ==  14286\r\n--    numero condicionC    ==  11112\r\n--    numero condicionAB   ==  2857\r\n--    numero condicionAC   ==  2223\r\n--    numero condicionBC   ==  1588\r\n--    numero condicionABC  ==  318\r\nnumero p = length (conjunto p)\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> solucion3\r\n--    33016\r\n--    (3.85 secs, 153248904 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Soluci\u00f3n 4                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Generando los conjuntos que cumplen una, dos o tres de las\r\n-- condiciones.  \r\n\r\nsolucion4 :: Int\r\nsolucion4 = \r\n    length conjuntoA + length conjuntoB + length conjuntoC \r\n    - 2* (length conjuntoAB + length conjuntoAC + length conjuntoBC) \r\n    + 3* length conjuntoABC\r\n\r\n-- conjuntoA es la lista de elementos que cumple la condici\u00f3n A:\r\nconjuntoA = [0,5..99999]\r\n\r\n-- conjuntoB es la lista de elementos que cumple la condici\u00f3n B:\r\nconjuntoB = [2,9..99999]\r\n\r\n-- conjuntoC es la lista de elementos que cumple la condici\u00f3n C:\r\nconjuntoC = [0,9..99999]\r\n\r\n-- conjuntoAB es la lista de elementos que cumplen las condiciones A y B: \r\nconjuntoAB = [30,65..99999]\r\n\r\n-- conjuntoAC es la lista de elementos que cumplen las condiciones A y C: \r\nconjuntoAC = [0,45..99999]\r\n\r\n-- conjuntoBC es la lista de elementos que cumplen las condiciones B y C: \r\nconjuntoBC = [9,72..99999]\r\n\r\n-- conjuntoABC es la lista de elementos que cumplen las condiciones A, B\r\n-- y C: \r\nconjuntoABC = [135,450..99999]\r\n\r\n-- El c\u00e1lculo de la soluci\u00f3n es\r\n--    ghci> :set +s\r\n--    ghci> solucion4\r\n--    33016\r\n--    (0.03 secs, 3154124 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Soluci\u00f3n 5                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Calculando el que n\u00famero de elementos que cumplen una, dos o tres de\r\n-- las condiciones.  \r\n\r\nsolucion5 :: Int\r\nsolucion5 = \r\n    numeroA + numeroB + numeroC \r\n    - 2 * (numeroAB + numeroAC + numeroBC) \r\n    + 3 * numeroABC\r\n\r\n-- (numeroProgrsion x d y) es el n\u00famero de t\u00e9rminos de la prograsi\u00f3n\r\n-- aritm\u00e9tica de diferencia d que empieza en x y termina en y. \r\nnumeroProgresion x d y = 1 + (y-x) `div` d\r\n \r\n-- numeroA es la cantidad de n\u00fameros que cumple la condici\u00f3n A.\r\nnumeroA = numeroProgresion 0 5 99999\r\n \r\n-- numeroB es la cantidad de n\u00fameros que cumple la condici\u00f3n B.\r\nnumeroB = numeroProgresion 2 7 99999\r\n \r\n-- numeroC es la cantidad de n\u00fameros que cumple la condici\u00f3n C.\r\nnumeroC = numeroProgresion 0 9 99999\r\n \r\n-- numeroAB es la cantidad de n\u00fameros que cumplen las condiciones A y B.\r\nnumeroAB = numeroProgresion 30 35 99999\r\n \r\n-- numeroAC es la cantidad de n\u00fameros que cumplen las condiciones A y C.\r\nnumeroAC = numeroProgresion 0 45 99999\r\n \r\n-- numeroBC es la cantidad de n\u00fameros que cumplen las condiciones B y C.\r\nnumeroBC = numeroProgresion 9 63 99999\r\n \r\n-- numeroABC es la cantidad de n\u00fameros que cumplen las condiciones A, B\r\n-- y C.\r\nnumeroABC = numeroProgresion 135 315 99999\r\n\r\n-- El c\u00e1lculo de la soluci\u00f3n es\r\n--    ghci> solucion5\r\n--    33016\r\n--    (0.01 secs, 1129032 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Comparaci\u00f3n                                                      --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comparaci\u00f3n del tiempo y espacio usado en las 5 soluciones es la\r\n-- siguiente: \r\n--    +-----+-------+---------------+\r\n--    | Sol | Segs. | Bytes         |\r\n--    +-----+-------+---------------+\r\n--    |   1 | 11.90 | 1.618.646.276 |\r\n--    |   2 |  1.72 |    66.504.036 |\r\n--    |   3 |  3.85 |   153.248.904 |\r\n--    |   4 |  0.03 |     3.154.124 |\r\n--    |   5 |  0.01 |     1.129.032 |\r\n--    +-----+-------+---------------+\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado la soluci\u00f3n con Haskell el desaf\u00edo matem\u00e1ticos N\u00fameros bonitos, n\u00fameros feos publicado en EL PA\u00cdS con motivo del sorteo de la Loter\u00eda de Navidad. Su enunciado es Desde el a\u00f1o 2011 en la Loter\u00eda Navidad se sortean los premios entre&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[1],"tags":[270,298,194],"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\/2431"}],"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=2431"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2431\/revisions"}],"predecessor-version":[{"id":3131,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2431\/revisions\/3131"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2431"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2431"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2431"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}