This is a mix between both the Split and Interleaved problems, and the linear problem. We are given two stacks of disks, on three pegs. We are expected to swap the stacks' position while respecting the classical Hanoi movement restrictions (one disk at a time, and no large disk over smaller disks) and the linear movement restriction (no direct exchange between the left-most and right-most pegs).
You will use three recursive functions:
In gather()
, the recursive call comes before two calls to moveDouble()
while in scatter()
, the calls to moveDouble()
come before the recursive call.
The main function that you should write is not recursive, but simply gather almost all disks, moves
directly the remaining disks, and then scatters back the small
disks.
The linearity naturally induces some extra complexity as you have to decompose every move between pegs 0 and 2. I am still confident in your ability to overcome the challenge :)
Note that the requested algorithm was proved optimal for that problem, so you don't need to fiddle the performance this time.