Menu Close

Laberinto numérico

José A. Alonso,

Enunciado

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

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]
Avanzado
, , , , , , , , ,

3 soluciones de “Laberinto numérico”

  1. Responder
    María Ruiz 
    import Data.List
 
sucesores:: Int -> [Int]
sucesores x | even x    = [x `div` 2, x+2, x*2]
            | otherwise = [x+2, x*2]
 
 
caminoMinimo :: Int -> Int -> [Int]
caminoMinimo x y = reverse (aux [[x]] [x])
    where aux css vs | elem y zs' = head [cs | cs <-css', elem y cs]
                     | otherwise  = aux css' (zs'++vs)
              where amplia vs ys@(x:xs) = [y:ys | y <- (sucesores x)  vs]
                    css' = concat (map (amplia vs) css)
                    zs' = map head css'
 
-- caminoMinimo 3 12 == [3,6,12]
-- caminoMinimo 12 3 == [12,6,3]
-- caminoMinimo 9 2  == [9,11,22,24,12,6,8,4,2]
-- caminoMinimo 2 9  == [2,1,3,5,7,9]
 
longitudCaminoMinimo :: Int -> Int -> Int
longitudCaminoMinimo x y 
    | x == y    = 0 
    | otherwise = length (caminoMinimo x y) - 1
  2. Responder
    María Ruiz 
    -- Sin calculer un camino mínimo:
 
longitudCaminoMinimo2 :: Int -> Int -> Int
longitudCaminoMinimo2 x y = aux [x] [x] 0
    where aux xs vs k | elem y ys = 1+k
                      | otherwise = aux ys (ys++vs) (1+k)
              where ys = (concat (map sucesores xs))  vs
  3. Responder
    María Ruiz 

    
-- En la solución anterior había una error, que ya está corregido

longitudCaminoMinimo2 :: Int -> Int -> Int
longitudCaminoMinimo2 x y = aux [x] [x] 0
    where aux xs vs k | elem y xs = k
                      | otherwise = aux ys (ys++vs) (1+k)
              where ys = (concat (map sucesores xs)) \\ vs

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.