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 a respeitar 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).
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 deve escrever não é recursiva, mas simplesmente obtém 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 adicional, pois tem que decompor cada movimento entre as varas 0 e 2. Ainda estou confiante na sua capacidade de vencer este desafio :)
Observe que foi provado que o algoritmo requerido é ótimo para este problema, então não precisa mexer no desempenho desta vez.