El juego de Oslo en Haskell
En el número especial de la revista Mundo científico sobre El universo de los números se presenta el juego de Oslo. En dicho juego
se trata de obtener cualquier número natural no nulo, por medio de aplicaciones sucesivas de una de las reglas siguientes:
- poner un cero al final del número,
- poner un cuatro al final del número y
- dividir por 2 si el número es par.
Por ejemplo, el 3 y el 5 se pueden obtener como sigue
1 2 |
4 -> 2 -> 24 -> 12 -> 6 -> 3 4 -> 2 -> 1 -> 10 -> 5 |
En la siguiente relación de ejercicios (elaborada para I1M) veremos qué números se pueden alcanzar, cómo y en cuántos pasos. Además, se presentan distintas soluciones comparando 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 227 228 229 230 231 232 233 234 235 |
-- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.List -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- sucesores :: Integer -> [Integer] -- tal que (sucesores x) es la lista de los números que se obtienen -- aplicando a x una de las reglas del juego de Oslo. Por ejemplo, -- sucesores 16 == [160,164,8] -- sucesores 17 == [170,174] -- --------------------------------------------------------------------- sucesores :: Integer -> [Integer] sucesores x | even x = [x*10, x*10+4, x `div` 2] | otherwise = [x*10, x*10+4] -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- nivel :: Integer -> [Integer] -- tal que (nivel n) es la lista de los números obtenidos aplicando u -- veces las reglas del juego de Oslo. Por ejemplo, -- ghci> nivel 0 -- [4] -- ghci> nivel 1 -- [2,40,44] -- ghci> nivel 2 -- [1,20,22,24,400,404,440,444] -- ghci> nivel 3 -- [10,11,12,14,200,202,204,220,222,224,240,244,4000,4004,4040,4044, -- 4400,4404,4440,4444] -- --------------------------------------------------------------------- nivel :: Integer -> [Integer] nivel 0 = [4] nivel n = sort (nub (concat [sucesores x | x <- nivel (n-1)])) -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- alcanzable :: Integer -> Bool -- tal que (alcanzable x) se verifica si el número x se puede obtener -- aplicando las reglas del juego de Oslo. Por ejemplo, -- alcanzable 5 == True -- --------------------------------------------------------------------- alcanzable :: Integer -> Bool alcanzable x = or [x `elem` nivel n | n <- [0..]] -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- profundidad :: Integer -> Integer -- tal que (profundidad de n) es el número de pasos necesarios para -- obtener el número x en el juego de Oslo. Por ejemplo, -- profundidad 3 == 5 -- profundidad 5 == 4 -- --------------------------------------------------------------------- profundidad :: Integer -> Integer profundidad n = head [x | x <- [0..], n `elem` nivel x] -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- niveles :: [[Integer]] -- tal que niveles es la lista de los niveles del juego de Oslo. Por -- ejemplo, -- ghci> take 4 niveles -- [[4], -- [2,40,44], -- [1,20,22,24,400,404,440,444], -- [10,11,12,14,200,202,204,220,222,224,240,244,4000,4004,4040,4044, -- 4400,4404,4440,4444]] -- --------------------------------------------------------------------- niveles :: [[Integer]] niveles = iterate (sort . nub . concatMap sucesores) [4] -- --------------------------------------------------------------------- -- Ejercicio 6. Definir, usando niveles, la función -- alcanzable2 :: Integer -> Bool -- tal que (alcanzable2 x) se verifica si el número x se puede obtener -- aplicando las reglas del juego de Oslo. Por ejemplo, -- alcanzable2 5 == True -- --------------------------------------------------------------------- alcanzable2 :: Integer -> Bool alcanzable2 x = or [x `elem` xs | xs <- niveles] -- --------------------------------------------------------------------- -- Ejercicio 7. Comparar las estadísticas del cálculo de las siguientes -- expresiones -- alcanzable 19 -- alcanzable2 19 -- --------------------------------------------------------------------- -- El cálculo es -- ghci> alcanzable 19 -- True -- (89.86 secs, 43502700 bytes) -- ghci> alcanzable2 19 -- True -- (70.10 secs, 13996816 bytes) -- --------------------------------------------------------------------- -- Ejercicio 8. Definir, usando niveles, la función -- profundidad2 :: Integer -> Integer -- tal que (profundidad2 de n) es el número de pasos necesarios para -- obtener el número x en el juego de Oslo. Por ejemplo, -- profundidad2 3 == 5 -- profundidad2 5 == 4 -- --------------------------------------------------------------------- profundidad2 :: Integer -> Integer profundidad2 n = genericLength (takeWhile (n `notElem`) niveles) -- --------------------------------------------------------------------- -- Ejercicio 9. Comparar las estadísticas del cálculo de las siguientes -- expresiones -- profundidad 19 -- profundidad2 19 -- --------------------------------------------------------------------- -- El cálculo es -- ghci> profundidad 19 -- 11 -- (90.17 secs, 44023720 bytes) -- ghci> profundidad2 19 -- 11 -- (81.96 secs, 22327508 bytes) -- --------------------------------------------------------------------- -- Ejercicio 10. Definir la función -- trayectoria :: Integer -> [Integer] -- tal que (trayectoria n) es la lista de número de 4 a n tal que cada -- elemento de la trayectoria se obtiene aplicándole al anterior alguna -- de las reglas del juego de Oslo. Por ejemplo, -- trayectoria 3 == [4,2,24,12,6,3] -- trayectoria 5 == [4,2,1,10,5] -- --------------------------------------------------------------------- trayectoria :: Integer -> [Integer] trayectoria n = reverse (aux n) where aux 4 = [4] aux n | mod n 10 `elem` [0,4] = n : aux (n `div` 10) | otherwise = n : aux (2*n) -- 2ª definición (con acumulador) trayectoria2 :: Integer -> [Integer] trayectoria2 n = aux n [] where aux 4 xs = 4 : xs aux n xs | mod n 10 `elem` [0,4] = aux (n `div` 10) (n:xs) | otherwise = aux (2*n) (n:xs) -- --------------------------------------------------------------------- -- Ejercicio 11. Definir, usando trayectoria, la función -- alcanzable3 :: Integer -> Bool -- tal que (alcanzable3 x) se verifica si el número x se puede obtener -- aplicando las reglas del juego de Oslo. Por ejemplo, -- alcanzable3 5 == True -- --------------------------------------------------------------------- alcanzable3 :: Integer -> Bool alcanzable3 x = last (trayectoria x) == x -- --------------------------------------------------------------------- -- Ejercicio 12. Comparar las estadísticas del cálculo de las siguientes -- expresiones -- alcanzable 19 -- alcanzable3 19 -- --------------------------------------------------------------------- -- El cálculo es -- ghci> alcanzable 19 -- True -- (89.86 secs, 43502700 bytes) -- ghci> alcanzable3 19 -- True -- (0.02 secs, 516640 bytes) -- --------------------------------------------------------------------- -- Ejercicio 13. Definir, usando trayectoria, la función -- profundidad3 :: Integer -> Integer -- tal que (profundidad3 de n) es el número de pasos necesarios para -- obtener el número x en el juego de Oslo. Por ejemplo, -- profundidad3 3 == 5 -- profundidad3 5 == 4 -- --------------------------------------------------------------------- profundidad3 :: Integer -> Integer profundidad3 n = genericLength (trayectoria n) - 1 -- --------------------------------------------------------------------- -- Ejercicio 14. Comparar las estadísticas del cálculo de las siguientes -- expresiones -- profundidad 19 -- profundidad2 19 -- --------------------------------------------------------------------- -- El cálculo es -- ghci> profundidad 19 -- 11 -- (90.17 secs, 44023720 bytes) -- ghci> profundidad3 19 -- 11 -- (0.01 secs, 516976 bytes) -- --------------------------------------------------------------------- -- Ejercicio 15. Definir, directamente por recursión, la función -- profundidad4 :: Integer -> Integer -- tal que (profundidad4 de n) es el número de pasos necesarios para -- obtener el número x en el juego de Oslo. Por ejemplo, -- profundidad4 3 == 5 -- profundidad4 5 == 4 -- --------------------------------------------------------------------- profundidad4:: Integer -> Integer profundidad4 4 = 0 profundidad4 n | mod n 10 `elem` [0,4] = 1 + profundidad4 (n `div` 10) | otherwise = 1 + profundidad4 (2*n) -- --------------------------------------------------------------------- -- Ejercicio 16. Comparar las estadísticas del cálculo de las siguientes -- expresiones -- maximum [profundidad3 n | n <- [1..10000]] -- maximum [profundidad4 n | n <- [1..10000]] -- --------------------------------------------------------------------- -- El cálculo es -- ghci> maximum [profundidad3 n | n <- [1..10000]] -- 50 -- (1.74 secs, 71085620 bytes) -- ghci> maximum [profundidad4 n | n <- [1..10000]] -- 50 -- (1.04 secs, 35426308 bytes) |
Fuente
- E. Busser, F. Casiro y B. Rittaud. “Buscar, jugar, encontrar”, Mundo Científico, extra “El universo de los números”, [s.a.], p. 108-114.
Destino
La anterior relación de ejercicios la ha elaborado para
- la asignatura de Informática de 1º del Grado en Matemáticas y
- la ampliación del libro Piensa en Haskell.