#include <iostream>
#include <cstdlib>
#include <string>
#include <stdio.h>
#include <time.h>
#include <fstream>

using namespace std;

int hanoi2(string, string, string, string, string, string, int, int&, int&);
int hanoi1(string, string, string, string, string, string, int, int&, int&);
void printMove(int, string, string);

int main()
{
    string Start = "Strt";	// Start
    string Dest = "Dest";	// Destination
    string A = "Aux1";		// Auxiliary 1
    string B = "Aux2";		// Auxiliary 2
    string C = "Aux3";		// Auxiliary 3
	string D = "Aux4";		// Auxiliary 4
    int numOfDisks;
	int movesMade = 0;
    int recursive = 0;
	int* m = &movesMade;
    int* r = &recursive;

	clock_t start, finish;
	cout << "Enter the number of Disks: ";
	cin >> numOfDisks;

	while (numOfDisks > 0)
    {
		cout << endl;
		cout << "Start" << endl << endl;

		//timing
		start = clock();
		hanoi1(Start, Dest, A, B, C, D, numOfDisks, *m, *r);
		finish = clock();

		cout << endl << endl;
		cout << "Total time taken to finsih: " << ((double)(finish-start)/CLOCKS_PER_SEC)*1000 <<	" milliseconds." <<	endl;
		cout << "Total moves made: " << movesMade << endl;
		cout << "Total number of recursive calls: " << recursive << endl << endl;

		movesMade = 0;
		recursive = 0;

		cout << "Number of disks: ";
		cin >> numOfDisks;
	}

	cout << endl;
    system("PAUSE");
    return 0;
}
/*
 * hanoi1 moves 1 disk
 */
int hanoi1(string Start, string Dest, string A, string B, string C, string D, int numOfDisks, int &ptr, int &ptr2)
{
    if (numOfDisks == 1)
    {
		printMove(numOfDisks, Start, A);
		ptr++;
		printMove(numOfDisks, A, B);
		ptr++;
		printMove(numOfDisks, B, C);
		ptr++;
		printMove(numOfDisks, C, D);
		ptr++;
		printMove(numOfDisks, D, Dest);
		ptr++;
		printMove(numOfDisks, Dest, Start);
		return ptr;
    }
	else if (numOfDisks > 1)
    {
        hanoi2(Start, A, B, C, D, Dest, numOfDisks-1, ptr, ptr2);
        printMove(numOfDisks, Start, Dest);
		ptr++;
		hanoi1(Dest, Start, A, B, C, D, numOfDisks-1, ptr, ptr2);
        ptr2++;
        hanoi1(Start, A, B, C, D, Dest, numOfDisks-1, ptr, ptr2);
        ptr2++;

    }
    return 0;
};
int hanoi2(string Start, string Dest, string A, string B, string C, string D, int numOfDisks, int &ptr, int &ptr2)
{
    if (numOfDisks == 1)
    {
		printMove(numOfDisks, Start, A);
		ptr++;
		printMove(numOfDisks, A, B);
		ptr++;
		printMove(numOfDisks, B, C);
		ptr++;
		printMove(numOfDisks, C, D);
		ptr++;
		printMove(numOfDisks, D, Dest);
		ptr++;
		printMove(numOfDisks, Dest, Start);
		return ptr;
	}
    else if (numOfDisks > 1)
    {
        hanoi2(Start, A, B, C, D, Dest, numOfDisks-1, ptr, ptr2);    // recursive call with numOfDisks-1 disks
        ptr2++;
        printMove(numOfDisks, Start, A);
		ptr++;
		printMove(numOfDisks, A, B);
		ptr++;
		printMove(numOfDisks, B, C);
        ptr++;
        printMove(numOfDisks, C, D);
		ptr++;
		hanoi1(Dest, Start, A, B, C, D, numOfDisks-1, ptr, ptr2);
		printMove(numOfDisks, D, Dest);
		ptr++;
		hanoi2(Start, A, B, C, D, Dest, numOfDisks-1, ptr, ptr2);
        ptr2++;
    }
	return 0;

};
void printMove(int numOfDisks, string from, string to)
{
    cout << endl << "Move disk (" << numOfDisks << ") from (" << from << ") to (" << to << ")\t";

};