Torre de Hanói usando F#

Lendo sobre F# resolvi implementar alguma coisa para distrair. A sintaxe me lembrou muito Haskell, outra linguagem funcional, assim como a estrutura da documentação, os módulos, as tuplas e as listas também me lembraram Haskell. Foi então que me lembrei de um problema que resolvi na época da faculdade, Torre de Hanói (http://pt.wikipedia.org/wiki/Torre_de_Hanói).

Para encontrar o menor número de movimentos, a estratégia que usei foi bem simples, baseado na regra que um disco maior não pode ficar sobre um disco menor, a função segue os seguintes passos:

1. Movimenta todos os N-1 discos para a torre intermediária;
2. Movimenta o último disco para a torre de destino;
3. Movimenta todos os N-1 discos da torre intermediária para a torre de destino.

A forma como a função “sabe” os movimentos para N-1 discos é algo que a recursão resolve (ainda bem!), o importante é a existência de um caso base que para nós é a solução de Hanoi (1), ou seja, o movimento do disco 1 da torre de origem para a torre destino.

O código que calcula os movimentos, se resume basicamente nas 2 linhas de implementação da função hanoi:

#light

// Função recursiva que gera a lista de movimentos dos discos
// n -> Número de discos
// origem -> Torre de origem
// inter -> Torre intermediária
// destino -> Torre de destino
let rec hanoi (n:int) (origem) (inter) (destino) : (int* string* string) list =
  if (n = 1) then [(1,origem,destino)]
  else hanoi (n - 1) origem destino inter @ [(n,origem,destino)] @ hanoi (n - 1) inter origem destino

// Função que imprime o movimento do disco a partir de uma tupla
let imprime (n,origem,destino) =
  "Move disco " + n.ToString() + " da " + origem + " para a " + destino + "\n"

// Função que aplica o Map a cada tupla da lista
// n -> Número de discos
let imprimeJogadas (n:int) =
   List.map imprime (hanoi n "Torre A" "Torre B" "Torre C")

O resultado da execução:

A escolha da demonstração desse problema se deve ao fato que sua resolução apesar de ser bem pequena explora vários recursos do paradigma funcional e de F# como o uso de funções, recursão, tuplas, listas e funcões de alta ordem.

Espero ter ajudado no trabalho de faculdade de alguém!