CC150 3.4

3_4.cpp

/* CC150 3.4
 * Classic problem of the Towers of Hanoi
 * http://en.wikipedia.org/wiki/Tower_of_Hanoi
 */

#include <iostream>
#include <stack>

using namespace std;

// first approach: recursive. return number of moves
int hanoiCount(int n, stack<int> &stackFrom, stack<int> &stackTo, stack<int> &stackVia)
{
	int count = 0;
	if (n < 1) {
		cerr << "Error number of disks..." << endl;
		return -1;
	}
	if (n == 1) {
		stackTo.push(stackFrom.top());
		stackFrom.pop();
		return 1;
	}
	else {
		count += hanoiCount(n - 1, stackFrom, stackVia, stackTo);
		stackTo.push(stackFrom.top());
		stackFrom.pop();
		++count;
		count += hanoiCount(n - 1, stackVia, stackTo, stackFrom);
	}
	return count;
}

void moveBetween(stack<int> &stackA, stack<int> &stackB);
int moveSmallest(bool moveRight, stack<int> &stackLt, stack<int> &stackMid, stack<int> &stackRt, int smallestStack);
void moveLarger(stack<int> &stackLt, stack<int> &stackMid, stack<int> &stackRt, int smallestStack);

// second approach: iterative
void hanoiIter(int n, stack<int> &stackLt, stack<int> &stackMid, stack<int> &stackRt)
{
	bool moveRight = (n % 2) ? false : true; // always move smallest piece to right if n is even, to left if n is odd
	int smallestStack = 0;
	smallestStack = moveSmallest(moveRight, stackLt, stackMid, stackRt, smallestStack);
	while (!stackLt.empty() || !stackMid.empty()) {
		moveLarger(stackLt, stackMid, stackRt, smallestStack);
		smallestStack = moveSmallest(moveRight, stackLt, stackMid, stackRt, smallestStack);
	}
	return;
}

// third approach: iterative
void hanoiIterSimple(int n, stack<int> &stackLt, stack<int> &stackMid, stack<int> &stackRt)
{
	while (1) {
		if (n % 2) { // for an odd number of disks repeat moves between AC, AB, and BC
			moveBetween(stackLt, stackRt);
			if (stackLt.empty() && stackMid.empty())
				break;
			moveBetween(stackLt, stackMid);
		}
		else { // for an odd number of disks repeat moves between AB, AC, BC
			moveBetween(stackLt, stackMid);
			moveBetween(stackLt, stackRt);
			if (stackLt.empty() && stackMid.empty())
				break;
		}
		moveBetween(stackMid, stackRt); // both cases share the third move
		if (stackLt.empty() && stackMid.empty())
			break;
	}
}

// make the legal move between two given stacks
void moveBetween(stack<int> &stackA, stack<int> &stackB)
{
	if (stackA.empty() && stackB.empty()) {
		cerr << "Cannot move between these two stacks!" << endl;
		return;
	}
	if (stackA.empty()) {
		stackA.push(stackB.top());
		stackB.pop();
		return;
	}
	if (stackB.empty()) {
		stackB.push(stackA.top());
		stackA.pop();
		return;
	}
	if (stackA.top() >= stackB.top()) { // strictly ascending??
		stackA.push(stackB.top());
		stackB.pop();
	}
	else {
		stackB.push(stackA.top());
		stackA.pop();
	}
	return;
}

// move the smallest disk in the same direction (to the right for even number of disks, to the left for odd.)
int moveSmallest(bool moveRight, stack<int> &stackLt, stack<int> &stackMid, stack<int> &stackRt, int smallestStack) {
	switch (smallestStack) {
	case 0:
		if (moveRight)
			stackMid.push(stackLt.top());
		else
			stackRt.push(stackLt.top());
		stackLt.pop();
		break;
	case 1:
		if (moveRight)
			stackRt.push(stackMid.top());
		else
			stackLt.push(stackMid.top());
		stackMid.pop();
		break;
	case 2:
		if (moveRight)
			stackLt.push(stackRt.top());
		else
			stackMid.push(stackRt.top());
		stackRt.pop();
		break;
	}
	return moveRight ? (smallestStack + 1) % 3 : (smallestStack + 2) % 3;
}

// move the non-smallest piece (there's only one legal move)
void moveLarger(stack<int> &stackLt, stack<int> &stackMid, stack<int> &stackRt, int smallestStack)
{
	switch (smallestStack) {
	case 0:
		moveBetween(stackMid, stackRt);
		break;
	case 1:
		moveBetween(stackLt, stackRt);
		break;
	case 2:
		moveBetween(stackLt, stackMid);
		break;
	}
	return;
}

// print out the stack from top to bottom
void display(stack<int> s)
{
	while (!s.empty()) {
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;
}

int main()
{
	stack<int> stackFrom, stackVia, stackTo;
	int n;
	cin >> n;
	for (int i = n; i != 0; --i)
		stackFrom.push(i);
	//int count = hanoiCount(n, stackFrom, stackTo, stackVia);
	//hanoiIter(n, stackFrom, stackVia, stackTo);
	hanoiIterSimple(n, stackFrom, stackVia, stackTo);
	cout << "stackFrom: ";
	display(stackFrom);
	cout << "stackVia: ";
	display(stackVia);
	cout << "stackTo: ";
	display(stackTo);
	//cout << "Number of moves is " << count << endl;
	return 0;
}