Laberinto numérico
Enunciado
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
-- El problema del laberinto numérico consiste en, dados un par de -- números, encontrar la longitud del camino más corto entre ellos -- usando sólo las siguientes operaciones: -- * multiplicar por 2, -- * dividir por 2 (sólo para los pares) y -- * sumar 2. -- Por ejemplo, un camino mínimo -- * de 3 a 12 es [3,6,12], -- * de 12 a 3 es [12,6,3], -- * de 9 a 2 es [9,18,20,10,12,6,8,4,2] y -- * de 2 a 9 es [2,4,8,16,18,9]. -- -- Definir la función -- longitudCaminoMinimo :: Int -> Int -> Int -- tal que (longitudCaminoMinimo x y) es la longitud del camino mínimo -- desde x hasta y en el laberinto numérico. -- longitudCaminoMinimo 3 12 == 2 -- longitudCaminoMinimo 12 3 == 2 -- longitudCaminoMinimo 9 2 == 8 -- longitudCaminoMinimo 2 9 == 5 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
longitudCaminoMinimo :: Int -> Int -> Int longitudCaminoMinimo x y = head [n | n <- [1..], y `elem` orbita n [x]] -- (orbita n xs) es el conjunto de números que se pueden obtener aplicando -- como máximo n veces las operaciones a los elementos de xs. Por ejemplo, -- orbita 0 [12] == [12] -- orbita 1 [12] == [6,12,14,24] -- orbita 2 [12] == [3,6,7,8,12,14,16,24,26,28,48] orbita :: Int -> [Int] -> [Int] orbita 0 xs = sort xs orbita n xs = sort (nub (ys ++ concat [sucesores x | x <- ys])) where ys = orbita (n-1) xs sucesores x | odd x = [2*x, x+2] | otherwise = [2*x, x `div` 2, x+2] |