Thread: 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.