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.