{"id":4060,"date":"2014-01-27T04:05:44","date_gmt":"2014-01-27T03:05:44","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4060"},"modified":"2014-01-26T19:08:58","modified_gmt":"2014-01-26T18:08:58","slug":"el-juego-de-oslo-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-juego-de-oslo-en-haskell\/","title":{"rendered":"El juego de Oslo en Haskell"},"content":{"rendered":"

En el n\u00famero especial de la revista Mundo cient\u00edfico<\/i> sobre El universo de los n\u00fameros<\/i> se presenta el juego de Oslo. En dicho juego
\nse trata de obtener cualquier n\u00famero natural no nulo, por medio de aplicaciones sucesivas de una de las reglas siguientes:<\/p>\n

    \n
  1. poner un cero al final del n\u00famero,\n
  2. poner un cuatro al final del n\u00famero y\n
  3. dividir por 2 si el n\u00famero es par.\n<\/ol>\n

    Por ejemplo, el 3 y el 5 se pueden obtener como sigue<\/p>\n

    \r\n   4 -> 2 -> 24 -> 12 -> 6 -> 3\r\n   4 -> 2 ->  1 -> 10 -> 5\r\n<\/pre>\n
    En la siguiente relaci\u00f3n de ejercicios (elaborada para I1M<\/a>) veremos qu\u00e9 n\u00fameros  se pueden alcanzar, c\u00f3mo y en cu\u00e1ntos pasos. Adem\u00e1s, se presentan distintas soluciones comparando sus eficiencias.
    \n <\/p>\n
    \r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librer\u00edas auxiliares                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    sucesores :: Integer -> [Integer]\r\n-- tal que (sucesores x) es la lista de los n\u00fameros que se obtienen\r\n-- aplicando a x una de las reglas del juego de Oslo. Por ejemplo,\r\n--    sucesores 16  ==  [160,164,8]\r\n--    sucesores 17  ==  [170,174]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucesores :: Integer -> [Integer]\r\nsucesores x | even x    = [x*10, x*10+4, x `div` 2]\r\n            | otherwise = [x*10, x*10+4]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    nivel :: Integer -> [Integer]\r\n-- tal que (nivel n) es la lista de los n\u00fameros obtenidos aplicando u\r\n-- veces las reglas del juego de Oslo. Por ejemplo,\r\n--    ghci> nivel 0\r\n--    [4]\r\n--    ghci> nivel 1\r\n--    [2,40,44]\r\n--    ghci> nivel 2\r\n--    [1,20,22,24,400,404,440,444]\r\n--    ghci> nivel 3\r\n--    [10,11,12,14,200,202,204,220,222,224,240,244,4000,4004,4040,4044,\r\n--     4400,4404,4440,4444]\r\n-- ---------------------------------------------------------------------\r\n\r\nnivel :: Integer -> [Integer]\r\nnivel 0 = [4]\r\nnivel n = sort (nub (concat [sucesores x | x <- nivel (n-1)]))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n \r\n--    alcanzable :: Integer -> Bool\r\n-- tal que (alcanzable x) se verifica si el n\u00famero x se puede obtener\r\n-- aplicando las reglas del juego de Oslo. Por ejemplo,\r\n--    alcanzable 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nalcanzable :: Integer -> Bool\r\nalcanzable x = or [x `elem` nivel n | n <- [0..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    profundidad :: Integer -> Integer\r\n-- tal que (profundidad de n) es el n\u00famero de pasos necesarios para\r\n-- obtener el n\u00famero x en el juego de Oslo. Por ejemplo,\r\n--    profundidad 3  ==  5\r\n--    profundidad 5  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nprofundidad :: Integer -> Integer\r\nprofundidad n = head [x | x <- [0..], n `elem` nivel x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    niveles :: [[Integer]]\r\n-- tal que niveles es la lista de los niveles del juego de Oslo. Por\r\n-- ejemplo, \r\n--    ghci> take 4 niveles\r\n--    [[4],\r\n--     [2,40,44],\r\n--     [1,20,22,24,400,404,440,444],\r\n--     [10,11,12,14,200,202,204,220,222,224,240,244,4000,4004,4040,4044,\r\n--      4400,4404,4440,4444]]\r\n-- ---------------------------------------------------------------------\r\n\r\nniveles :: [[Integer]]\r\nniveles = iterate (sort . nub . concatMap sucesores) [4]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir, usando niveles, la funci\u00f3n \r\n--    alcanzable2 :: Integer -> Bool\r\n-- tal que (alcanzable2 x) se verifica si el n\u00famero x se puede obtener\r\n-- aplicando las reglas del juego de Oslo. Por ejemplo,\r\n--    alcanzable2 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nalcanzable2 :: Integer -> Bool\r\nalcanzable2 x = or [x `elem` xs | xs <- niveles]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Comparar las estad\u00edsticas del c\u00e1lculo de las siguientes\r\n-- expresiones \r\n--    alcanzable  19\r\n--    alcanzable2 19\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> alcanzable 19\r\n--    True\r\n--    (89.86 secs, 43502700 bytes)\r\n--    ghci> alcanzable2 19\r\n--    True\r\n--    (70.10 secs, 13996816 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir, usando niveles, la funci\u00f3n\r\n--    profundidad2 :: Integer -> Integer\r\n-- tal que (profundidad2 de n) es el n\u00famero de pasos necesarios para\r\n-- obtener el n\u00famero x en el juego de Oslo. Por ejemplo,\r\n--    profundidad2 3  ==  5\r\n--    profundidad2 5  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nprofundidad2 :: Integer -> Integer\r\nprofundidad2 n = genericLength (takeWhile (n `notElem`) niveles)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Comparar las estad\u00edsticas del c\u00e1lculo de las siguientes\r\n-- expresiones \r\n--    profundidad  19\r\n--    profundidad2 19\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> profundidad 19\r\n--    11\r\n--    (90.17 secs, 44023720 bytes)\r\n--    ghci> profundidad2 19\r\n--    11\r\n--    (81.96 secs, 22327508 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    trayectoria :: Integer -> [Integer]\r\n-- tal que (trayectoria n) es la lista de n\u00famero de 4 a n tal que cada\r\n-- elemento de la trayectoria se obtiene aplic\u00e1ndole al anterior alguna\r\n-- de las reglas del juego de Oslo. Por ejemplo,\r\n--    trayectoria 3  ==  [4,2,24,12,6,3]\r\n--    trayectoria 5  ==  [4,2,1,10,5]\r\n-- ---------------------------------------------------------------------\r\n\r\ntrayectoria :: Integer -> [Integer]\r\ntrayectoria n = reverse (aux n)\r\n    where aux 4 = [4]\r\n          aux n | mod n 10 `elem` [0,4] = n : aux (n `div` 10)\r\n                | otherwise             = n : aux (2*n)\r\n\r\n-- 2\u00aa definici\u00f3n (con acumulador)\r\ntrayectoria2 :: Integer -> [Integer]\r\ntrayectoria2 n = aux n []\r\n    where aux 4 xs = 4 : xs \r\n          aux n xs | mod n 10 `elem` [0,4] = aux (n `div` 10) (n:xs)\r\n                   | otherwise             = aux (2*n) (n:xs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir, usando trayectoria, la funci\u00f3n \r\n--    alcanzable3 :: Integer -> Bool\r\n-- tal que (alcanzable3 x) se verifica si el n\u00famero x se puede obtener\r\n-- aplicando las reglas del juego de Oslo. Por ejemplo,\r\n--    alcanzable3 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nalcanzable3 :: Integer -> Bool\r\nalcanzable3 x = last (trayectoria x) == x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Comparar las estad\u00edsticas del c\u00e1lculo de las siguientes\r\n-- expresiones \r\n--    alcanzable  19\r\n--    alcanzable3 19\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> alcanzable 19\r\n--    True\r\n--    (89.86 secs, 43502700 bytes)\r\n--    ghci> alcanzable3 19\r\n--    True\r\n--    (0.02 secs, 516640 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir, usando trayectoria, la funci\u00f3n\r\n--    profundidad3 :: Integer -> Integer\r\n-- tal que (profundidad3 de n) es el n\u00famero de pasos necesarios para\r\n-- obtener el n\u00famero x en el juego de Oslo. Por ejemplo,\r\n--    profundidad3 3  ==  5\r\n--    profundidad3 5  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nprofundidad3 :: Integer -> Integer\r\nprofundidad3 n = genericLength (trayectoria n) - 1 \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Comparar las estad\u00edsticas del c\u00e1lculo de las siguientes\r\n-- expresiones \r\n--    profundidad  19\r\n--    profundidad2 19\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> profundidad 19\r\n--    11\r\n--    (90.17 secs, 44023720 bytes)\r\n--    ghci> profundidad3 19\r\n--    11\r\n--    (0.01 secs, 516976 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Definir, directamente por recursi\u00f3n, la funci\u00f3n\r\n--    profundidad4 :: Integer -> Integer\r\n-- tal que (profundidad4 de n) es el n\u00famero de pasos necesarios para\r\n-- obtener el n\u00famero x en el juego de Oslo. Por ejemplo,\r\n--    profundidad4 3  ==  5\r\n--    profundidad4 5  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nprofundidad4:: Integer -> Integer\r\nprofundidad4 4 = 0\r\nprofundidad4 n | mod n 10 `elem` [0,4] = 1 + profundidad4 (n `div` 10)\r\n               | otherwise             = 1 + profundidad4 (2*n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Comparar las estad\u00edsticas del c\u00e1lculo de las siguientes\r\n-- expresiones \r\n--    maximum [profundidad3 n | n <- [1..10000]]\r\n--    maximum [profundidad4 n | n <- [1..10000]]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> maximum [profundidad3 n | n <- [1..10000]]\r\n--    50\r\n--    (1.74 secs, 71085620 bytes)\r\n--    ghci> maximum [profundidad4 n | n <- [1..10000]]\r\n--    50\r\n--    (1.04 secs, 35426308 bytes)\r\n<\/pre>\n
    Fuente<\/b><\/p>\n