#include <iostream>
#include <stack>
#include "conio.h"
using namespace std;

stack<int> peg[4];
int move_counter = 0;
int numDisks;
int aux[2]; //pegs that can't be moved between
int destination;
int DiscsToBeMoved;

//Functions
void load(int num_disks);
void move(int i, int j);
bool stacks_equal(int i, int j);
bool stacks_aux(int i, int j);
bool moved_disc_smaller(int i, int j);
void Hanoi(int DiscsToBeMoved, int source, int dest, int aux);
void simple_long_edge(int DiscsToBeMoved, int source, int dest, int aux, int aux2);
void short_edge(int DiscsToBeMoved, int source, int dest, int aux, int aux2);
void short_edge_backward(int DiscsToBeMoved, int source, int dest, int aux, int aux2);
void long_edge(int DiscsToBeMoved, int source, int dest, int aux, int aux2);

void main()
{
	// Function selection.
	int choice;
	cout << "Please select a function:" << endl << endl;
	cout << "1. Hanoi" << endl;
	cout << "2. simple_long_edge" << endl;
	cout << "3. short_edge" << endl;
	cout << "4. short_edge_backwards" << endl;
	cout << "5. long_edge" << endl;
	cin >> choice;

	switch (choice)
	{
		case 1: 
			system("cls");
			cout << "How many disks? ";
			cin >> numDisks;

			// Load pegs
			for (int i = 0; i < 4;i++)
			{
				peg[i].push(numDisks + 1);
			}
			load(numDisks);
			DiscsToBeMoved = numDisks;

			Hanoi(DiscsToBeMoved, 0, 2, 1);
			cout << "Number of moves: " << move_counter << "." << endl << endl;
			getch();
			break;
		case 2: 
			system("cls");
			cout << "How many disks? ";
			cin >> numDisks;

			// Load pegs
			for (int i = 0; i < 4;i++)
			{
				peg[i].push(numDisks + 1);
			}
			load(numDisks);
			DiscsToBeMoved = numDisks;

			simple_long_edge(DiscsToBeMoved, 0, 3, 1, 2);
			cout << "Number of moves: " << move_counter << "." << endl << endl;
			getch();
			break;
		case 3:
			system("cls");
			cout << "How many disks? ";
			cin >> numDisks;
			
				aux[0] = 2;
				aux[1] = 3;
			

			// Load pegs
			for (int i = 0; i < 4;i++)
			{
				peg[i].push(numDisks + 1);
			}
			load(numDisks);
			DiscsToBeMoved = numDisks;

			short_edge(DiscsToBeMoved, 0, 3, 1, 2);
			cout << "Number of moves: " << move_counter << "." << endl << endl;
			getch();
			break;
		case 4:
			system("cls");
			cout << "How many disks? ";
			cin >> numDisks;
		
				aux[0] = 0;
				aux[1] = 2;

			// Load pegs
			for (int i = 0; i < 4;i++)
			{
				peg[i].push(numDisks + 1);
			}
			load(numDisks);
			DiscsToBeMoved = numDisks;

			short_edge_backward(DiscsToBeMoved, 0, 3, 1, 2);
			cout << "Number of moves: " << move_counter << "." << endl << endl;
			getch();
			break;
		case 5:
			system("cls");
			cout << "How many disks? ";
			cin >> numDisks;
			
				aux[0] = 1;
				aux[1] = 2;

			// Load pegs
			for (int i = 0; i < 4;i++)
			{
				peg[i].push(numDisks + 1);
			}
			load(numDisks);
			DiscsToBeMoved = numDisks;

			long_edge(DiscsToBeMoved, 0, 3, 1, 2);
			cout << "Number of moves: " << move_counter << "." << endl << endl;
			getch();
			break;
		default:
			system("cls");
			cout << "Invalid choice." << endl << endl;
			getch();
			break;
	}
}

void load(int num_disks)
{
	for (int i = 0; i < num_disks; i++)
	{
		peg[0].push(i);
	}
}

//Basic move function - calls to 3 boolean functions to make sure move is allowed.
void move(int i, int j)
{
	if (stacks_equal(i,j) && stacks_aux(i,j) && moved_disc_smaller(i,j))
	{
		peg[j].push(peg[i].top());
		peg[i].pop();
		if (numDisks <= 5)
		{
			cout << "move disc " << peg[j].top() << " from " << i << " to " << j << "." << endl;
		}
		move_counter++;
	}
	else
	{
		cout << "Illegal move!" << endl;
	}
}

// Checks if the 2 stacks that user is trying to move disc between are equal.
bool stacks_equal(int i, int j)
{
	if (i != j)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// Checks if an illegal move is being made between two pegs that can't be moved between.
bool stacks_aux(int i, int j)
{
	if ((i == aux[0] && j == aux[1]) || (j == aux[0] && i == aux[1]))
	{
		return false;
	}
	else
	{
		return true;
	}
}

// Checks to make sure a larger disc is not being put on top of a smaller disc.
bool moved_disc_smaller(int i, int j)
{
	if (peg[i].top() == (numDisks + 1))
	{
		return false;
	}
	else
	{
		if (peg[i].top() < peg[j].top())
		{
			if((peg[j].top()) == (numDisks + 1))
			{
				return true;
			}
			else
			{
				return false;
			}
		}
		else
		{
			return true;
		}
	}
}

// Basic 3-peg Hanoi algorithm.
void Hanoi(int DiscsToBeMoved, int source, int dest, int aux)
{
	if (DiscsToBeMoved > 0)
	{
	  Hanoi(DiscsToBeMoved - 1, source, aux, dest);
      move(source, dest);
      Hanoi(DiscsToBeMoved - 1, aux, dest, source);
	}
}

// 4 pegs - only makes calls to basic 3-peg Hanoi algorithm
void simple_long_edge(int DiscsToBeMoved, int source, int dest, int aux, int aux2)
{
	  if (DiscsToBeMoved % 2 == 0)
	  {
		  Hanoi(numDisks/2, source, aux, dest);
		  Hanoi(numDisks/2,source,dest,aux2);
		  Hanoi(numDisks/2, aux, dest, source);
	  }
	  else
	  {
		  Hanoi(((numDisks-1)/2),source,aux,dest);
		  Hanoi(((numDisks+1)/2),source,dest,aux2);
		  Hanoi(((numDisks-1)/2),aux,dest,source);
	  }
}

// Moves are not allowed between aux2 and dest
void short_edge(int DiscsToBeMoved, int source, int dest, int aux, int aux2)
{
	if (DiscsToBeMoved == 1)
	{
		move(source,dest); 
	}
	else if (DiscsToBeMoved == 2)
	{
		Hanoi(DiscsToBeMoved, source, dest, aux);
	}
	else if (DiscsToBeMoved == 3)
	{
		move(source, aux);
		move(source, aux2);
		move(source, dest);
		move(aux2, source);
		move(source,dest);
		move(aux, dest);
	}
	else
	{
		int CalculatedDiscs=2;
		while ((CalculatedDiscs * (CalculatedDiscs+1)) <= (2 * DiscsToBeMoved))
		{
			CalculatedDiscs++;
		}
		CalculatedDiscs = DiscsToBeMoved - CalculatedDiscs;

		short_edge(CalculatedDiscs, source, aux2, aux, dest);
		Hanoi(DiscsToBeMoved - CalculatedDiscs, source, dest, aux);
		Hanoi(CalculatedDiscs, aux2, source, aux);
		short_edge(CalculatedDiscs, source, dest, aux, aux2);
		
	}
}

//moves are not allowed between source and aux2
void short_edge_backward(int DiscsToBeMoved, int source, int dest, int aux, int aux2)
{
	if (DiscsToBeMoved == 1)
	{
		move(source,dest); 
	}
	else if (DiscsToBeMoved == 2)
	{
		Hanoi(DiscsToBeMoved, source, dest, aux);
	}
	else if (DiscsToBeMoved == 3)
	{
		move(source, aux);
		move(source, dest);
		move(dest, aux2);
		move(source, dest);
		move(aux2, dest);
		move(aux, dest);
	}
	else
	{
		int CalculatedDiscs=2;
		while ((CalculatedDiscs * (CalculatedDiscs+1)) <= (2 * DiscsToBeMoved))
		{
			CalculatedDiscs++;
		}
		CalculatedDiscs = DiscsToBeMoved - CalculatedDiscs;

		short_edge_backward(CalculatedDiscs, source, dest, aux, aux2);
		Hanoi(CalculatedDiscs, dest, aux2, aux);
		Hanoi(DiscsToBeMoved - CalculatedDiscs, source, dest, aux);
		short_edge_backward(CalculatedDiscs, aux2, dest, aux, source);
	}
}

//moves are not allowed between aux and aux2
void long_edge(int DiscsToBeMoved, int source, int dest, int aux, int aux2)
{
	if (DiscsToBeMoved == 1)
	{
		move(source,dest); 
	}
	else if (DiscsToBeMoved == 2)
	{
		move(source,aux);
		move(source,dest);
		move(aux,dest);
	}
	else if (DiscsToBeMoved == 3)
	{
		move(source, aux);
		move(source, aux2);
		move(source, dest);
		move(aux2,dest);
		move(aux, dest);
	
		/*if (stacks_equal(aux2,dest) && stacks_aux(aux2,dest) && moved_disc_smaller(aux2,dest))
		{
			move(aux2,dest);
		}
		else if (stacks_equal(aux2,source) && stacks_aux(aux2,source) && moved_disc_smaller(aux2,source))
		{
			move(aux2,source);
			move(source,dest);
		}
		else
		{
			move(aux2,aux);
			move(aux,dest);
		}
		if (stacks_equal(aux,dest) && stacks_aux(aux,dest) && moved_disc_smaller(aux,dest))
		{
			move(aux,dest);
		}
		else if (stacks_equal(aux,source) && stacks_aux(aux,source) && moved_disc_smaller(aux,source))
		{
			move(aux,source);
			move(source,dest);
		}
		else
		{
			move(aux,aux2);
			move(aux2,dest);
		}*/
	}
	/*else if (DiscsToBeMoved == 4)
	{
		move(source, dest);
		move(source, aux2);
		move(source, aux);
		move(dest,aux2);
		move(source,dest);
		move(aux,dest);
		move(aux2,source);
		move(aux2,dest);
		move(source,dest);
		//Hanoi(2,aux,dest,source);
	}/*
	else if (DiscsToBeMoved == 5)
	{
		move(source, aux2);
		move(source, dest);
		move(source, aux);
		move(dest,aux);
		move(aux2,dest);
		move(dest,aux);
		move(source,aux2);
		move(source,dest);
		Hanoi(3,aux,dest,source);
	}
	*/
	else
	{
		int CalculatedDiscs=2;
		while ((CalculatedDiscs * (CalculatedDiscs+1)) < (2 * DiscsToBeMoved))
		{
			CalculatedDiscs++;
		}
		CalculatedDiscs = DiscsToBeMoved - CalculatedDiscs;



		//Hanoi(CalculatedDiscs,source,aux,dest);
		//Hanoi(DiscsToBeMoved - CalculatedDiscs,source,dest,aux2);
		//long_edge(CalculatedDiscs,aux,dest,source,aux2);

		long_edge(CalculatedDiscs,source,aux2,dest,aux);
		Hanoi(DiscsToBeMoved - CalculatedDiscs, source, dest, aux);
		long_edge(CalculatedDiscs,aux2,dest,source,aux);

	//	long_edge(CalculatedDiscs-1, source, aux, dest, aux2);
		//Hanoi(DiscsToBeMoved - CalculatedDiscs+1, source, dest, aux2);
		//Hanoi(CalculatedDiscs, aux2, source, aux);
		//short_edge(CalculatedDiscs, source, dest, aux, aux2);

		 //if (DiscsToBeMoved % 2 == 0)
		// {
		//	 long_edge(DiscsToBeMoved/2,source,aux2,aux,dest);
		//	Hanoi(DiscsToBeMoved/2,source,dest,aux);
		// }
	//	 else
		// {
		//	 long_edge(((DiscsToBeMoved-1)/2),source,aux2,dest,aux);
			// Hanoi(((DiscsToBeMoved+1)/2),source,dest,aux);
	//	 }
	}
}