Las torres de Hanói

PorJosé A. Alonso 13-abril-201525-abril-2021

En la clase de la semana pasada comenté la posibilidad de que los alumnos me enviaran propuestas de ejercicios para publicarlos en Exercitium. La primera que he recibido es la de Javier Linares sobre el problema de las torres de Hanoi que constituye el ejercicio de hoy.

Las torres de Hanoi es un rompecabeza que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los N discos en el poste C.

Definir la función

   hanoi :: Int -> [String]

1	hanoi :: Int -> [String]

tal que (hanoi n) es la lista de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,

   ghci> hanoi 1
   ["Mueve el disco 1 de A a C"]
   ghci> hanoi 2
   ["Mueve el disco 1 de A a B","Mueve el disco 2 de A a C","Mueve el disco 1 de B a C"]
   ghci> mapM_ putStrLn (hanoi 2)
   Mueve el disco 1 de A a B
   Mueve el disco 2 de A a C
   Mueve el disco 1 de B a C
   ghci> mapM_ putStrLn (hanoi 3)
   Mueve el disco 1 de A a C
   Mueve el disco 2 de A a B
   Mueve el disco 1 de C a B
   Mueve el disco 3 de A a C
   Mueve el disco 1 de B a A
   Mueve el disco 2 de B a C
   Mueve el disco 1 de A a C

ghci> hanoi 1

["Mueve el disco 1 de A a C"]

ghci> hanoi 2

["Mueve el disco 1 de A a B","Mueve el disco 2 de A a C","Mueve el disco 1 de B a C"]

ghci> mapM_ putStrLn (hanoi 2)

Mueve el disco 1 de A a B

Mueve el disco 2 de A a C

Mueve el disco 1 de B a C

ghci> mapM_ putStrLn (hanoi 3)

Mueve el disco 1 de A a C

Mueve el disco 2 de A a B

Mueve el disco 1 de C a B

Mueve el disco 3 de A a C

Mueve el disco 1 de B a A

Mueve el disco 2 de B a C

Mueve el disco 1 de A a C

Soluciones

hanoi :: Int -> [String]
hanoi n = aux n "A" "B" "C" where  
    aux n a b c
        | n == 1 = ["Mueve el disco 1 de " ++ a ++ " a " ++ c]
        | otherwise = 
            aux (n-1) a c b ++ 
            ["Mueve el disco "++ show n ++ " de " ++ a ++ " a " ++ c] ++
            aux (n-1) b a c

hanoi :: Int -> [String]

hanoi n = aux n "A" "B" "C" where

aux n a b c

| n == 1 = ["Mueve el disco 1 de " ++ a ++ " a " ++ c]

| otherwise =

aux (n-1) a c b ++

["Mueve el disco "++ show n ++ " de " ++ a ++ " a " ++ c] ++

aux (n-1) b a c

5 Comentarios

import Data.Char (intToDigit)

hanoi :: Int -> [String]
hanoi n = hanoi' n 'A' 'B' 'C'

hanoi' :: Int -> Char -> Char -> Char -> [String]
hanoi' 0 _ _ _ = []
hanoi' n a b c = 
    hanoi' (n-1) a c b ++ 
    ["Mueve el disco " ++ [intToDigit n] ++ " de " ++ [a] ++ " a " ++ [c]] ++ 
    hanoi' (n-1) b a c

import Data.Char (intToDigit)

hanoi :: Int -> [String]

hanoi n = hanoi' n 'A' 'B' 'C'

hanoi' :: Int -> Char -> Char -> Char -> [String]

hanoi' 0 _ _ _ = []

hanoi' n a b c =

hanoi' (n-1) a c b ++

["Mueve el disco " ++ [intToDigit n] ++ " de " ++ [a] ++ " a " ++ [c]] ++

hanoi' (n-1) b a c

Responder

import Data.Monoid

data Peg a = Peg a

type Move a b = Int -> Peg a -> Peg a -> b

hanoiP :: Monoid b => Peg a -> Peg a -> Peg a -> Move a b -> Int -> b
hanoiP _ _ _ _ 0 = mempty
hanoiP from to aux f n =
  hanoiP from aux to f (n - 1) <> f n from to <> hanoiP aux to from f (n - 1)

hanoi :: Int -> [String]
hanoi = hanoiP (Peg "A") (Peg "C") (Peg "B") move
  where
    move n (Peg s) (Peg d) = ["Mueve el disco " ++ show n ++ " de " ++ s ++ " a " ++ d]

import Data.Monoid

data Peg a = Peg a

type Move a b = Int -> Peg a -> Peg a -> b

hanoiP :: Monoid b => Peg a -> Peg a -> Peg a -> Move a b -> Int -> b

hanoiP _ _ _ _ 0 = mempty

hanoiP from to aux f n =

hanoiP from aux to f (n - 1) <> f n from to <> hanoiP aux to from f (n - 1)

hanoi :: Int -> [String]

hanoi = hanoiP (Peg "A") (Peg "C") (Peg "B") move

where

move n (Peg s) (Peg d) = ["Mueve el disco " ++ show n ++ " de " ++ s ++ " a " ++ d]

Responder

Esta solución se basa en el patrón que siguen las soluciones. El disco n se mueve 1 vez, el disco (n-1) 2 veces… el disco m se mueve (2^(n-m)) veces.

import Data.List (unfoldr, uncons)

data Mover = M Int Int

hanoi :: Int -> [String]
hanoi n = unfoldr f (zip [1..n] (repeat 0), hanoiRel n)

hanoiRel :: Int -> [Mover]
hanoiRel n = foldl (\r (x,p) -> esparcir (M x p) r) [] (zip [n,n-1..1] (esparcir 2 (repeat 1)))

f (xs,ms) = 
    do ((M n p),rs) <- uncons ms
       y <- lookup n xs
       let ny = (y+p) `mod` 3
       return (muestra n y ny,(take (n-1) xs ++ [(n,ny)] ++ drop n xs,rs))

esparcir n (x:xs) = n : x : esparcir n xs -- (n:) . (++[n]) . intersperse n
esparcir n [] = [n]

muestra n y ny = "Mueve el disco "++show n++" de "++muestraD y++" a "++muestraD ny
    where muestraD 0 = "A"
          muestraD 1 = "B"
          muestraD 2 = "C"

import Data.List (unfoldr, uncons)

data Mover = M Int Int

hanoi :: Int -> [String]

hanoi n = unfoldr f (zip [1..n] (repeat 0), hanoiRel n)

hanoiRel :: Int -> [Mover]

hanoiRel n = foldl (\r (x,p) -> esparcir (M x p) r) [] (zip [n,n-1..1] (esparcir 2 (repeat 1)))

f (xs,ms) =

do ((M n p),rs) <- uncons ms

y <- lookup n xs

let ny = (y+p) `mod` 3

return (muestra n y ny,(take (n-1) xs ++ [(n,ny)] ++ drop n xs,rs))

esparcir n (x:xs) = n : x : esparcir n xs -- (n:) . (++[n]) . intersperse n

esparcir n [] = [n]

muestra n y ny = "Mueve el disco "++show n++" de "++muestraD y++" a "++muestraD ny

where muestraD 0 = "A"

muestraD 1 = "B"

muestraD 2 = "C"

Responder

Una mejor solución:

data Mover = M Int Int

hanoi :: Int -> [String]
hanoi n = map hanoiAux $
    foldl (\r (x,p) -> esparcirIx (M x p) r 0) [] (zip [n,n-1..1] (concat (repeat [1,0])))
hanoiAux (M n i, p) = "Mueve el disco "++show n++" de "
    ++(["A a B","B a C","C a A","A a C","C a B","B a A"]!!(p+3*i))

esparcirIx n (x:xs) i = (n,i) : x : esparcirIx n xs ((i+1) `mod` 3)
esparcirIx n [] i = [(n,i)]

data Mover = M Int Int

hanoi :: Int -> [String]

hanoi n = map hanoiAux $

foldl (\r (x,p) -> esparcirIx (M x p) r 0) [] (zip [n,n-1..1] (concat (repeat [1,0])))

hanoiAux (M n i, p) = "Mueve el disco "++show n++" de "

++(["A a B","B a C","C a A","A a C","C a B","B a A"]!!(p+3*i))

esparcirIx n (x:xs) i = (n,i) : x : esparcirIx n xs ((i+1) `mod` 3)

esparcirIx n [] i = [(n,i)]

Responder

hanoi :: Int -> [String]
hanoi n = hanoi' n 'A' 'B' 'C'

hanoi' :: Int -> Char -> Char -> Char -> [String]
hanoi' 0 a b c = []
hanoi' n a b c = 
    hanoi' (n-1) a c b  ++ 
    ["Mueve el disco " ++ show n ++ " de " ++ [a] ++ " a " ++ [c]] ++  
    hanoi' (n-1) b a c

hanoi :: Int -> [String]

hanoi n = hanoi' n 'A' 'B' 'C'

hanoi' :: Int -> Char -> Char -> Char -> [String]

hanoi' 0 a b c = []

hanoi' n a b c =

hanoi' (n-1) a c b ++

["Mueve el disco " ++ show n ++ " de " ++ [a] ++ " a " ++ [c]] ++

hanoi' (n-1) b a c

Responder

Las torres de Hanói

Soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico