Menu Close

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:

  1. poner un cero al final del número,
  2. poner un cuatro al final del número y
  3. dividir por 2 si el número es par.

Por ejemplo, el 3 y el 5 se pueden obtener como sigue

   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.

-- ---------------------------------------------------------------------
-- § 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

PeH