Torres gêmeas de Hanoi Lineares

Esta é uma mistura entre os problemas "Split", Intercalado e linear. Temos duas pilhas de discos, em três varas. Devemos trocar a posição das pilhas respeitando as restrições clássicas de movimento (um disco por vez, disco grande não pode ficar sobre disco pequeno) e a restrição do movimento linear (proibido mudança diretamente da vara mais à esquerda para a vara mais à direita).

Você vai usar três funções recursivas:

Em gather(), a chamada recursiva vem antes das duas chamadas a moveDouble() enquanto em scatter(), as chamadas para moveDouble() vem depois da chamada recursiva. A função principal que você deve escrever não é recursiva, mas simplesmente obtem quase todos os discos, move os discos restantes diretamente, e então espalha ("scatters") de volta os discos menores.

A linearidade naturalmente induz alguma complexidade extra pois você tem que decompor cada movimento entre as varas 0 e 2. Eu ainda estou confiante na sua capacidade de vencer este desafio :)

Observe que foi provado que o algoritmo requerido é ótimo para este problema, então você não precisa "fiddle" a performance desta vez.