C# Hanoi Tower Iterative Version

Question

I'm still a beginner in C# and I would like some help. My function works for 3 disks but from 4 it no longer works and I don't understand why. I hope someone could help me.

`public static string HanoiTower(int n)
{
    string res = "Moves for " + n.ToString() + " disks\n";
    string depart = "1";
    string aux = "2";
    string dest = "3";
    string lDisk = "1";
    if (n % 2 == 0)
    {
        dest = aux;
        aux = "3";
    }
    for (int i = 1; i < Lessons.MyPow(2, n); i++)
    {
        if (i % 3 == 1)
        {
            if (lDisk == dest)
            {
                res += dest + " -> " + depart + "\n";
                lDisk = depart;
            }
            else
            {
                if (lDisk == depart)
                    lDisk = dest;
                res += depart + " -> " + dest + "\n";
            }
        }

        else if (i % 3 == 2)
        {
            if (lDisk == aux)
            {
                res += aux + " -> " + depart + "\n";
                lDisk = depart;
            }
            else
            {
                if (lDisk == depart)
                    lDisk = aux;
                res += depart + " -> " + aux + "\n";
            }
        }
        else
        {
            if (lDisk == dest)
            {
                res += dest + " -> " + aux + "\n";
                lDisk = aux;
            }
            else
            {
                if (lDisk == aux)
                    lDisk = dest;
                res += aux + " -> " + dest + "\n";
            }
        }
    }

    return res.Substring(0,res.Length-1);
}`

I've seen people on the internet using stacks but I don't know how to use them and I'd like to avoid it for now so preferably don't offer me solutions with that

Answer 1

The logic to determine the source and target stacks is not very complex, but not as simple as you have in your code.

You rightly started by dealing with the parity of the 𝑛.

Other observations are that the interval at which a disc gets to move is a power of 2. The smallest disc moves every 2 turns (starting at move 1), the one-but-smallest disc moves every 4 turns (starting at move 2), ...etc.

The direction of the move is again ruled by parity.

Here is your code adapted to apply that logic:

    public static string HanoiTower(int n)
    {
        string res = "Moves for " + n.ToString() + " disks\n";
 
        int moveCount = 1 << n; // No need for Lessons import for this
        for (int i = 1; i < moveCount; i++)
        {
            int power = i & -i; // Get least significant set bit value
            // Convert that to a bit nummber to get 0-based disc (numbered by their size): 
            int discToMove = (int) Math.Log(power, 2);
            bool parity = (n + discToMove) % 2 > 0;
            // At which turn this disc will make its first move:
            int discFirstMoveAt = 1 << discToMove;
            // At which interval this disc moves:
            int discPeriod = discFirstMoveAt * 2; 
            // How many moves has this disc already made:
            int discMoveCount = (i - discFirstMoveAt) / discPeriod; 
            int source = (parity ? -discMoveCount % 3 + 3 : discMoveCount) % 3;
            int target = (source + (parity ? 2 : 1)) % 3;
            // Convert source & target to 1-based numbers
            res += (source + 1) + " -> " + (target + 1) + "\n";
        }
        return res.Substring(0, res.Length-1);
    }