Again, our previous solution is working, but it is far from being optimal. When moving the towers, we use the algorithm for 3 pegs even if we have 4 pegs. Of course, movements to the last peg are restricted since it contains the other stack, but we can always store the smallest disk on top of the other stack before moving our stack.
For that, we need to devise a new function hanoi_fast(height, src, free, full, dst)
that
moves the stack from src
to dst
using free
, but storing the smallest
disk onto full
beforehand.
hanoi_fast(height, src, free, full, dst)
function is not recursive.
It moves the first disk and then call the regular hanoi()
function.
This change greatly improve the performance, as you can see below. Of course, this trick could also be used for the interleaved algorithm, leading as expected to the exact same performance.
Disks amount | Interleaved | Slow Split | Fast Split |
5 pairs | 62 moves | 88 moves | 46 moves |
6 pairs | 126 moves | 183 moves | 82 moves |
7 pairs | 254 moves | 374 moves | 150 moves |
As a conclusion, most of us are satisfied with a working solution and we easily overlook possibilities to improve the problem decomposition. You should not do that ;)