El desafío

Las Torres de Hanói es un rompecabezas inventado en 1883 por el matemático francés Édouard Lucas en lo cual existe tres torres y queremos mudar x discos de uno a otro. Sin embargo:

• No podemos mover más que un disco a la vez.
• Un disco grande nunca puede cubrir uno más pequeño.

El objetivo es producir un array de tuples que representa cada movimiento de cada disco.

Un algoritmo

Mover una pila de un disco o dos es bastante fácil. Con tres, empieza a complicarse la cosa.

Trasladar una pila de 3

[('a','b'),('a','c'),('b','c'),('a','b'),('c','a'),('c','b'),('a','b')]

Trasladar una pila de 4

[('a','c'),('a','b'),('c','b'),('a','c'),('b','a'),('b','c'),('a','c'),('a','b'),('c','b'),('c','a'),('b','a'),('c','b'),('a','c'),('a','b'),('c','b')]

Existe un paradigma recursiva:

1. Mover n - 1 discos desde a a c
2. Mover 1 disco de a a b
3. Mover n - 1 discos descde c a b

El codigo

Podemos hacer la semántica más comprensiva utilizando sinónimos de tipos. Aunque creo que no nos aporta mucho aquí dado la falta de múltiples tipos de Char.

type Tower = Char
type Move = (Tower, Tower)

Y con este signature hacemos una declaración de como funciona y de qué resultado tiene nuestra función hanoi.

hanoi :: Integer -> Tower -> Tower -> Tower -> [Move]

Casos bases

Dos casos bases:

hanoi 0 _ _ _ =  []
hanoi 1 a b _ =  [(a, b)]

El caso recursivo

hanoi n a b c =
  let nMinusOne = (n - 1)
    in
    hanoi nMinusOne a c b ++ -- algoritmo cas0 1
    hanoi 1 a b c ++         -- algoritmo cas0 2
    hanoi nMinusOne c b a    -- algoritmo cas0 3

Vamos a ver con un poco más detaille la correspondencia entre el algoritmo y las llamada del función. Empezamos con:

hanoi 3 'a' 'b' 'c'

hanoi nMinusOne a c b

• No produce valores en la primera instancia - como no hay case base todavía. nMinusOne es 2.

Pero con la primera recursion, hanoi 2 'a' 'c' 'b', se empieza a producir resultados:

• Se nota que ha cambiado el orden de las torres.

• Y nMinusOne siendo ahora 1, salen estos valores:

• hanoi 1 a c b produce [(‘a’, ‘b’)]

• hanoi 1 a b c produce [(‘a’, ‘c’)]

• hanoi 1 c b a produce [(‘b’, ‘c’)]

hanoi 1 a b c

Aquí no hay recursión. Toda pasa dentro de la misma llamada.

1. hanoi 1 a b c ++ produce [(‘a’, ‘b’]

hanoi nMinusOne c b a

Volvemos a recurrir con n = 2. nMinusOne tiene su ámbito léxico establecido en la llamada inicial y siempre va ser 2.

The argumentos ahora son: ‘c’ ‘b’ ‘a’.

1. hanoi 1 a c b produce [(‘c’, ‘a’)]
2. hanoi 1 a b c produce [(‘c’, ‘b’)]
3. hanoi 1 c b a produce [(‘a’, ‘b’)]

El resultado final

Utilizando ++ se ha concatenado los resultados de cada una de las tres llamadas en la función hanoi.

λ> hanoi 3 'a' 'b' 'c'

[('a','b'),('a','c'),('b','c'),('a','b'),('c','a'),('c','b'),('a','b')]

Podriamos aplicar hanoi 4 'a' 'b' 'c', or hanoi 5 'a' 'b' 'c' etc.