Laberinto numérico

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

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

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]

3 Comentarios

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

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

Responder

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

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

Responder

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

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

Responder

Laberinto numérico

Enunciado

Soluciones

3 Comentarios

Leave a Reply to María RuizCancel reply

Entradas recientes

Buscar

Correo electrónico

Enunciado

Soluciones

Se puede imprimir o compartir con

3 Comentarios

Leave a Reply to María RuizCancel reply

Entradas recientes

Buscar

Correo electrónico