Modded Tower of Hanoi

Okay, so here's a modded tower of hanoi problem:


Instead of 3, we have 4 pegs, a source peg, a target peg, and 2 auxiliary pegs. Disks can
be moved from any stack to any other stack, with one exception. Direct moves between
the auxiliary pegs are not allowed. (Naturally, we maintain the rule that we cannot put
a larger disk on top of a smaller disk.)
As a data structure, you use an array of four stacks (with source being stack number 0 and
target being stack number 3). A simple array implementation of the stacks themselves is
sufficient. If you use a global array of stacks then the various procedures (called functions in
C++) can just pass the array indices instead of actual stacks.
You may assume n < 100. You may encode the bottom of each stack by a disk of size
n + 1 that is never moved.


Here's my Main function: I get an error trying to pass the stack array through the function...it's been a few years since I've coded at all and I am stumped.

Code:

---

#include <iostream>
#include <stack>
using namespace std;
int counter = 0;
int m;
stack<int> Peg[4];

int main () 
{
    int n = 0;
    counter = 0; 

    cout << "Please enter a number between 1 and 100: ";
    cin >> n;
    cout << endl;
    cout << "OK. Run Towers of Hanoi puzzle with " << n << " disks:" << endl;
    cout << endl;
    Peg[0].push(n+1);
        Peg[1].push(n+1);
        Peg[2].push(n+1);
        Peg[3].push(n+1);
       
        for(int x=n; x > 0; x--)
        {
                Peg[0].push(x);
        }

        Hanoi(n, Peg[0],Peg[1],Peg[2]);

    cout << endl;
    cout << "That took " << counter << " moves." << endl;
    cout << endl;

    system ("PAUSE");
    return 0;
}

---

Error stems from bolded portion.

Anyway, so now I can not test and do the rest of the assignment, but want to make sure I'm on the right track

2.
Write a procedure move(i, j) to move the top disk of stack i to the top of stack j. The
procedure tests whether i 6= j and whether a direct move from stack i to stack j is
allowed, i.e., {i, j} is not the set of auxiliary stacks. The procedure also has to test
whether the newly moved disk is indeed smaller than the disk on which it is placed.
This procedure operates on a globally defined array of stacks. Naturally, it is a bit of
a waste to do these tests at run time, but it should improve the confidence that your
solutions are correct.
Let m be a global variable, being the initial value of n, i.e., the total number of disks.
If m 5, then move(i, j) should also produce the line of output, “move from i to j”.
In any case, move(i, j) should also increment a global counter s counting the number of
steps. The counter is output once at the end.

Code:

---

void Move(int i,int j)
{
        if(Peg[a].top() < Peg[j].top() && (a*j != 2))
        {
                Peg[j].push(Peg[a].top());
                Peg[a].pop();
                counter++;
                cout<<"move disk " << a << " to " << j << " Moves: " << counter << endl;
        }
        else cout << "invalid";
}

---

This should be correct, I just haven't implemented only showing moves if m < 5.

3.
Write a procedure hanoi(n, s, t, u) for the regular Tower of Hanoi problem to move n
disks from peg s to peg t with the help of the auxiliary peg u.

Code:

---

void Hanoi(int n, int from, int to, int aux)
{
        if(n>0)
        {
                Hanoi(n-1,from,aux,to);
                Move(from,to);
                Hanoi(n-1,aux,to,from);
        }
}

---

This, too, should be the correct algorithm for the original tower of hanoi problem


4.
Now we deal with the Tower of Hanoi problem with 2 auxiliary pegs. The task is to
move n disks from source peg s to a target peg t with the help of 2 auxiliary pegs u and
v.

(a) Write a simple procedure simple long edge(n, s, t, u, v) based on calls to hanoi only.
For a good choice of k, move k disks from s to u, then the remaining n − k disks
from s to t, and finally the k disks from u to t.

Code:

---

Simple_long(int i,int from,int to,int aux1,int aux2)
{
        int k=i/2;
        Hanoi(k, from,aux2,to);
        Hanoi(1-k,from,to,aux1);
        Hanoi(k, aux2,to,from);
}

---

I haven't optimized this yet, just initially choosing k at half of the stack. Other than that, that should be right as well.


5.
Write 3 procedures which might call each other. Run each of the procedures for n = 4
and n = 20.
You can get 20 points for each. 5 for describing the idea, 5 for the solution being nicely
structured, 5 for a correct solution, and 5 for the output. You receive the first 10 points
only if your solution is non-trivial, i.e., not just a call to hanoi.
(a) Write a procedure short edge(n, s, t, u, v) moving n disks from s to t in the case
where no direct moves between t and v are allowed.

Code:

---

Short_edge(int i, int from, int to, int aux1, int aux2)
{
        if (i==1)
                move(from,to);
        if (i==2)
                Hanoi(1-k,from,to,aux1);
        if(i>2)
        {
                Short_edge(i/2,from,aux1,to,aux2);
                Hanoi(i-1/2,from,to,aux2);
                short_edge_back(i/2-1,aux1,from,aux2,to); 
                move(aux1,aux2);
                move(aux2,to);
                short_edge(i/2-1,from,to,aux1,aux2);
        }
}

---

This one I'm not completely sure on the algorithm....

(b) Write a procedure short edge backward(n, s, t, u, v) moving n disks from s to t in
the case where no direct moves between s and v are allowed.

Code:

---

Short_edge_back(int i, int from, int to, int aux1, int aux2)
{
        if(i>3)
        {
                Short_edge_back(i/2-1,from,to,aux1,aux2);
                move(from,aux1);
                move(aux1,aux2);
                Short_edge(i/2,to,aux2,from,aux1);
                Hanoi(aux1,to,from);
                Short_edge_back(aux2,to,aux1,from);
        }
}

---

I haven't hard coded if there are only 1 or 2 disks, but the logic seems right to me.

(c) Write a procedure long edge(n, s, t, u, v) moving n disks from s to t in the case
where no direct moves between u and v are allowed.

This one kind of has me stumped :\



If you need anything else, just let me know. Thanks in advance for any help :)


EDIT: NEvermind on the error, I don't know what I was thinking, I can just use Hanoi(n, 1, 2, 3); lol, whoops.

Unless they're constructors for classes, many of your functions are missing a return type -- probably void.

You never use counter in main(), so it will always be zero. Perhaps you should use the return value of Hanoi to count the number of moves . . .

That's because I wrote pseudo-code in word, I didn't include the return types.


Anyway, now that I got past that, I still can't get it to run properly. It goes through one move then crashes at the bold point.

I tried to debug it, and it seems that the second time it goes to the Move() function, Peg[i] is empty for some reason....

Code:

---

void Move(int i,int j)
{
        if(Peg[i].top() <= Peg[j].top() /*&& (i*j != 2)*/)
        {
                Peg[j].push(Peg[i].top());
                Peg[i].pop();
                counter++;
                cout<<"move disk " << i << " to " << j << " Moves: " << counter << endl;
        }
        else cout << "invalid";
}


void Hanoi(int n, int from, int to, int aux)
{
        if(n>0)
        {
                Hanoi(n-1,from,aux,to);
                Move(to,from);
                Hanoi(n-1,aux,to, from);
        }
}

---

Here's my main functino again if you need it:

Code:

---

int main () 
{
    int n = 0;
    counter = 0; 

    cout << "Please enter a number between 1 and 100: ";
    cin >> n;
    cout << endl;
    cout << "OK. Run Towers of Hanoi puzzle with " << n << " disks:" << endl;
    cout << endl;
    Peg[0].push(n+1);
        Peg[1].push(n+1);
        Peg[2].push(n+1);
        Peg[3].push(n+1);
       
        for(int x=n; x > 0; x--)
        {
                Peg[0].push(x);
        }

        Hanoi(n,1,2,3);

    cout << endl;
    cout << "That took " << counter << " moves." << endl;
    cout << endl;
    return 0;
}

---

NOTE: I'm still just trying to get the regular 3 peg tower of hanoi problem to work correctly.

Okay, I figured out some stuff:

Here's my new code if anyone is interested:

Code:

---

void Move(int i,int j)
{
        if(Peg[i].top() <= Peg[j].top() /*&& (i*j != 2)*/)
        {
                Peg[j].push(Peg[i].top());
                Peg[i].pop();
                counter++;
                if(m <= 5)
                        cout<<"move disk " << i << " to " << j << " Moves: " << counter << endl;
        }
        else cout << "invalid";
}

void Hanoi(int n, int from, int to, int aux)
{
        if(n>0)
        {
                Hanoi(n-1,from,aux,to);
                Move(from,to);
                Hanoi(n-1,aux,to,from);
        }
}


int main () 
{
    int n = 0;
    counter = 0; 

    cout << "Please enter a number between 1 and 100: ";
    cin >> n;

        m = n;
    cout << endl;
    cout << "OK. Run Towers of Hanoi puzzle with " << n << " disks:" << endl;
    cout << endl;
    Peg[0].push(n+1);
        Peg[1].push(n+1);
        Peg[2].push(n+1);
        Peg[3].push(n+1);
        Peg[4].push(n+1);
       
        for(int x=n; x > 0; x--)
        {
                Peg[1].push(x);
        }

        Hanoi(n,1,2,3);

        //Simple_long(n,1,2,3,4);

    cout << endl;
    cout << "That took " << counter << " moves." << endl;
    cout << endl;
    return 0;
}

---

Basically, I mixed up some stuff implementing the algorithm I had to look over, and It messed up when I tried to send 0 since it tried to store it as a peg # too, so I had to send pegs 1,2,3 (and 1,2,3,4 when I needed 4). probably not the neatest way to fix it, but it fixes it, heh...

I also figured out the one with 4 towers:

Code:

---

void Simple_long(int i,int from,int to,int aux1,int aux2)
{
        int k=i/2;
        Hanoi(k, from,aux2,to);
        Hanoi(1-k,from,to,aux1);
        Hanoi(k, aux2,to,from);
}

---

it finds the minimum amount of moves with 2 auxiliary pegs. k is the amount of pegs it does first. I just naturally went with 1/2...probably a better number based on the amount of pegs.

Anyway, now I'm trying to figure out this one:

Write a procedure short edge(n, s, t, u, v) moving n disks from s to t in the case
where no direct moves between t and v are allowed.

t and v being the destination peg and the second aux peg, respectively.

Code:

---

void Short_edge(int i, int from, int to, int aux1, int aux2)
{
        if (i==1)
                Move(from,to);
        if (i==2)
                Hanoi(i,from,to,aux1);
        if(i>2)
        {
                Short_edge(i/2,from,aux1,to,aux2);
                Hanoi(i-i/2,from,to,aux2);
                Short_edge_back(i/2-1,aux1,from,aux2,to); 
                Move(aux1,aux2);
                Move(aux2,to);
                Short_edge(i/2-1,from,to,aux1,aux2);
        }
}

---

and it does work, kind of...it compiles and runs, but anything over 5 disks and it starts having invalid moves. the higher the number, the higher the number of invalid moves...

Can anyone see any flaws in the algorithm?

EDIT: Crap, I forgot that there's a call to another one of my functions, which is the next part of the question:

Write a procedure short edge backward(n, s, t, u, v) moving n disks from s to t in
the case where no direct moves between s and v are allowed.

and here's what I have, this actually might be where it's messed up:

Code:

---

void Short_edge_back(int i, int from, int to, int aux1, int aux2)
{
        if(i>3)
        {
                Short_edge_back(i/2-1,from,to,aux1,aux2);
                Move(from,aux1);
                Move(aux1,aux2);
                Short_edge(i/2,to,aux2,from,aux1);
                Hanoi(i/2-1,aux1,to,from);
                Short_edge_back(i/2-1,aux2,to,aux1,from);
        }
}

---