Efficient algorithm for tower of hanoi variation

Question

So this is a variation of the tower of hanoi problem. The difference here is that you can only move a ring to the pole on the right (3 poles) and if you are on the 3rd pole, moving right means you end up on the first pole. So for example, if you only have one ring in pole 1 and if you want to move it to pole 3, you must first move the ring to pole 2, then to pole 3. Now a very simple recursive algorithm (in pseudocode) to solve this is the following:

// moving from pole A to pole B
SpecialTowerOfHanoi(n, A, B, C):
  if (n == 1):
    move ring from A to B
  else:
    // move the top n-1 to poll B
    SpecialTowerOfHanoi(n-1, A, B, C);

    // move the top n-1 from poll B to poll C
    SpecialTowerOfHanoi(n-1, B, C, A);

    move remaining ring from A to B

    // move n-1 from poll C to poll A
    SpecialTowerOfHanoi(n-1, C, A, B);

    // move n-1 from poll A to poll B
    SpecialTowerOfHanoi(n-1, A, B, C);

However, this is apparently not the most efficient algorithm and the following is supposedly more efficient:

TowerOfHanoiMoveOnceToRight(n, A, B, C):
  if (n == 1):
    move ring from A to B
  else:
    // use a new function to move two times to the right from A to C
    TowerOfHanoiMoveTwiceToRight(n-1, A, C, B);
    move remaining ring from A to B

    // move n-1 from C to B
    TowerOfHanoiMoveTwiceToRight(n-1, C, B, A);

TowerOfHanoiMoveTwiceToRight(n, A, C, B):
  if (n == 1):
    move ring from A to B
    move ring from B to C
  else:
    // move n-1 from A to C
    TowerOfHanoiMoveTwiceToRight(n-1, A, C, B);
    move remaining ring from A to B

    // now only move n-1 from C to A (so once only)
    TowerOfHanoiMoveOnceToRight(n-1, C, A, B);
    move remaining ring from B to C

    // now move n-1 from A to C
    TowerOfHanoiMoveTwiceToRight(n-1, A, C, B);

Obviously, you can show that the second way of doing it is more efficient than the first way through some pretty tedious analysis. However, I am sort of stuck conceptually on why the second one is more efficient. The way I think about this is you want to move the bottom piece as quickly as possible and you can only do this once the top n-1 have been moved twice. Hence, by creating a new function, the first function (TowerOfHanoiMoveOnceToRight) looks a lot simpler than the SpecialTowerOfHanoi function. But the TowerOfHanoiMoveTwiceToRight just looks a lot more complicated. I would like to have some insights on how to think of this problem.

Answer 1

Okay, I think the logical (no proof) way to think about this is that in the second algorithm, you are trying to move the bottom disk as quickly as possible. The only way you can do that is to move the top n-1 disks to poll c. Because every single step in the second algorithm advances the bottom disk to the correct position, it doesn't do anything unnecessary and hence is more efficient. So for example, in the first algorithm, you first move n-1 stack from A to B, this does not really advance the bottom disk. Please let me know if any of you think this is a good way of thinking about this.

Answer 2

This one is faster than the recursive one:

unsigned long i;  
static const int MAXNUMBEROFDISKS = 32;
vector<int> pow2Vec;
uint_fast32_t mPinFrom    = 0;
uint_fast32_t mNumDisk    = 0;
unsigned long numDiskLong = 0;
uint_fast32_t mOffset[MAXNUMBEROFDISKS];
uint_fast32_t mDir[MAXNUMBEROFDISKS]          = { 0 };
uint_fast32_t mPositionDisk[MAXNUMBEROFDISKS] = { 0 };
const uint_fast32_t mRedirectArr[5] = { 2, 0, 1, 2, 0 };

Algos::Algos()
{ 
    for (int i = 0; i < MAXNUMBEROFDISKS; ++i)
    {
        pow2Vec.push_back(pow(2, i));
        mOffset[i] = 1;
    }

    for (int i = 1; i < MAXNUMBEROFDISKS; i += 2)
    {
        mDir[i] = 2;
    }

    mOffset[0] = 0;
}

void Algos::calculListBinExperiment(vector<tuple<int, int, int>>& listeFinale, int nbDisk)
{
    listeFinale.resize(pow2Vec[nbDisk] - 1);
    _BitScanForward(&i, nbDisk);
    for (int noCoup = 1; noCoup < pow2Vec[nbDisk] ; ++noCoup)
    {
        _BitScanForward(&numDiskLong, noCoup);
        mNumDisk = numDiskLong;
        mPinFrom = mPositionDisk[mNumDisk];
        mPositionDisk[mNumDisk] = mRedirectArr[mPositionDisk[mNumDisk] + mDir[mNumDisk + 
        mOffset[i]]];
        listeFinale[noCoup - 1] = make_tuple(mNumDisk, mPinFrom, mPositionDisk[mNumDisk]);
    }
}