I1M2012: El problema de las números bonitos y números feos en Haskell
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell el desafío matemáticos Números bonitos, números feos publicado en EL PAÍS con motivo del sorteo de la Lotería de Navidad. Su enunciado es
Desde el año 2011 en la Lotería Navidad se sortean los premios entre los cien mil números que van del 00000 al 99999 (en los décimos los números siempre se escriben con cinco cifras). Aunque todos los números tienen exactamente las mismas posibilidades de resultar premiados, con frecuencia se habla de números bonitos y números feos. Como es una valoración estética, que un número sea bonito o feo depende de los gustos de cada uno.
En este caso un número de lotería nos parecerá bonito si cumple
exactamente una, y solamente una, de estas tres condiciones:
- a) es divisible entre 5,
- b) da resto 2 al dividirlo entre 7,
- c) la suma de sus cifras es divisible entre 9.
Por ejemplo, el 00037 es bonito porque cumple la condición b pero no las otras dos; sin embargo, el 00324 es feo, ya que cumple las condiciones b y c. De igual forma, podríamos 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.
El desafío que se propone es decidir cuántos de los números que participan en el sorteo de Lotería de Navidad (recordad, del 00000 al 99999) son bonitos según el criterio expresado anteriormente.
A continuación, se presentan 5 soluciones en Haskell y se comparan sus eficiencias.
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 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 |
-- --------------------------------------------------------------------- -- § Solución 1 -- -- --------------------------------------------------------------------- -- La primera solución es una traducción directa del enunciado. -- solucion1 es la solución del problema. solucion1 :: Int solucion1 = length [n | n <- [0..99999], verificaUna n [condicionA, condicionB, condicionC]] -- (condicionA n) se verifica si n cumple la condición a; es decir, n es -- divisible entre 5. condicionA :: Integer -> Bool condicionA n = rem n 5 == 0 -- (condicionB n) se verifica si n cumple la condición b; es decir, el -- resto de dividir n entre 7 es 2. condicionB :: Integer -> Bool condicionB n = rem n 7 == 2 -- (condicionC n) se verifica si n cumple la condición c; es decir, la -- suma de sus cifras es divisible entre 9. condicionC :: Integer -> Bool condicionC n = rem (sumaCifras n) 9 == 0 -- (sumaCifras n) es la suma de las cifras de n. sumaCifras :: Integer -> Integer sumaCifras n = sum [read [x] | x <- show n] -- (verificaUna n ps) se verifica si n cumple una, y sólo una, de las -- propiedades ps. verificaUna :: Integer -> [Integer -> Bool] -> Bool verificaUna n ps = [p n | p <- ps, p n] == [True] -- El cálculo es -- ghci> solucion1 -- 33016 -- (11.90 secs, 1618646276 bytes) -- --------------------------------------------------------------------- -- § Solución 2 -- -- --------------------------------------------------------------------- -- En esta solución se modifica la condición c por su equivalente: n es -- múltiplo de 9. solucion2 :: Int solucion2 = length [n | n <- [0..99999], verificaUna n [condicionA, condicionB, condicionC2]] -- (condicionC2 n) se verifica si n cumple la condición c; es decir, es -- múltiplo de 9. condicionC2 :: Integer -> Bool condicionC2 n = rem n 9 == 0 -- El cálculo es -- ghci> solucion2 -- 33016 -- (1.72 secs, 66504036 bytes) -- --------------------------------------------------------------------- -- § Solución 3 -- -- --------------------------------------------------------------------- -- Considerando los conjuntos que cumplen una, dos o tres de las -- condiciones. solucion3 :: Int solucion3 = numero condicionA + numero condicionB + numero condicionC2 - 2* (numero condicionAB + numero condicionAC + numero condicionBC) + 3* numero condicionABC -- (condicion p) es el conjunto de elementos que cumplen la condicion -- p. Por ejemplo, -- ghci> take 10 (conjunto condicionA) -- [0,5,10,15,20,25,30,35,40,45] -- ghci> take 10 (conjunto condicionB) -- [2,9,16,23,30,37,44,51,58,65] -- ghci> take 10 (conjunto condicionC) -- [0,9,18,27,36,45,54,63,72,81] -- ghci> take 10 (conjunto condicionAB) -- [30,65,100,135,170,205,240,275,310,345] -- ghci> take 10 (conjunto condicionAC) -- [0,45,90,135,180,225,270,315,360,405] -- ghci> take 10 (conjunto condicionBC) -- [9,72,135,198,261,324,387,450,513,576] -- ghci> take 10 (conjunto condicionABC) -- [135,450,765,1080,1395,1710,2025,2340,2655,2970] conjunto p = [n | n <- [0..99999], p n] -- (condicionAB n) se verifica si n cumple las condiciones a y b. condicionAB :: Integer -> Bool condicionAB n = condicionA n && condicionB n -- (condicionAC n) se verifica si n cumple las condiciones a y c. condicionAC :: Integer -> Bool condicionAC n = condicionA n && condicionC2 n -- (condicionBC n) se verifica si n cumple las condiciones b y c. condicionBC :: Integer -> Bool condicionBC n = condicionB n && condicionC2 n -- (condicionABC n) se verifica si n cumple las condiciones a, b y c. condicionABC :: Integer -> Bool condicionABC n = condicionA n && condicionB n && condicionC2 n -- (numero p) es el número de elementos que cumplen la condicion -- p. Por ejemplo, -- numero condicionA == 20000 -- numero condicionB == 14286 -- numero condicionC == 11112 -- numero condicionAB == 2857 -- numero condicionAC == 2223 -- numero condicionBC == 1588 -- numero condicionABC == 318 numero p = length (conjunto p) -- El cálculo es -- ghci> solucion3 -- 33016 -- (3.85 secs, 153248904 bytes) -- --------------------------------------------------------------------- -- § Solución 4 -- -- --------------------------------------------------------------------- -- Generando los conjuntos que cumplen una, dos o tres de las -- condiciones. solucion4 :: Int solucion4 = length conjuntoA + length conjuntoB + length conjuntoC - 2* (length conjuntoAB + length conjuntoAC + length conjuntoBC) + 3* length conjuntoABC -- conjuntoA es la lista de elementos que cumple la condición A: conjuntoA = [0,5..99999] -- conjuntoB es la lista de elementos que cumple la condición B: conjuntoB = [2,9..99999] -- conjuntoC es la lista de elementos que cumple la condición C: conjuntoC = [0,9..99999] -- conjuntoAB es la lista de elementos que cumplen las condiciones A y B: conjuntoAB = [30,65..99999] -- conjuntoAC es la lista de elementos que cumplen las condiciones A y C: conjuntoAC = [0,45..99999] -- conjuntoBC es la lista de elementos que cumplen las condiciones B y C: conjuntoBC = [9,72..99999] -- conjuntoABC es la lista de elementos que cumplen las condiciones A, B -- y C: conjuntoABC = [135,450..99999] -- El cálculo de la solución es -- ghci> :set +s -- ghci> solucion4 -- 33016 -- (0.03 secs, 3154124 bytes) -- --------------------------------------------------------------------- -- § Solución 5 -- -- --------------------------------------------------------------------- -- Calculando el que número de elementos que cumplen una, dos o tres de -- las condiciones. solucion5 :: Int solucion5 = numeroA + numeroB + numeroC - 2 * (numeroAB + numeroAC + numeroBC) + 3 * numeroABC -- (numeroProgrsion x d y) es el número de términos de la prograsión -- aritmética de diferencia d que empieza en x y termina en y. numeroProgresion x d y = 1 + (y-x) `div` d -- numeroA es la cantidad de números que cumple la condición A. numeroA = numeroProgresion 0 5 99999 -- numeroB es la cantidad de números que cumple la condición B. numeroB = numeroProgresion 2 7 99999 -- numeroC es la cantidad de números que cumple la condición C. numeroC = numeroProgresion 0 9 99999 -- numeroAB es la cantidad de números que cumplen las condiciones A y B. numeroAB = numeroProgresion 30 35 99999 -- numeroAC es la cantidad de números que cumplen las condiciones A y C. numeroAC = numeroProgresion 0 45 99999 -- numeroBC es la cantidad de números que cumplen las condiciones B y C. numeroBC = numeroProgresion 9 63 99999 -- numeroABC es la cantidad de números que cumplen las condiciones A, B -- y C. numeroABC = numeroProgresion 135 315 99999 -- El cálculo de la solución es -- ghci> solucion5 -- 33016 -- (0.01 secs, 1129032 bytes) -- --------------------------------------------------------------------- -- § Comparación -- -- --------------------------------------------------------------------- -- La comparación del tiempo y espacio usado en las 5 soluciones es la -- siguiente: -- +-----+-------+---------------+ -- | Sol | Segs. | Bytes | -- +-----+-------+---------------+ -- | 1 | 11.90 | 1.618.646.276 | -- | 2 | 1.72 | 66.504.036 | -- | 3 | 3.85 | 153.248.904 | -- | 4 | 0.03 | 3.154.124 | -- | 5 | 0.01 | 1.129.032 | -- +-----+-------+---------------+ |