//=========================================================================
#define PROGRAMMER "SOLUTIONS, NoFrills"
#define PROG_CODE  "soln"
#define COURSE     "ECE-1021"
#define YEAR       (2003)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "Example"
#define REVISION   (0)
#define TITLE      "The Tower of Hanoi"
#define SUBTITLE   "Example Program"
#define EMAIL      "wbahn@eas.uccs.edu"
#define FILENAME   "hanoi.c"
//=========================================================================

//====================================================================
// PROBLEM:
//====================================================================
//
// Write a program that solves the Tower of Hanois puzzle.
//
//====================================================================
// SOLUTION:
//====================================================================
//
// First, build the basic building blocks needed for a solution.
//
// 1) Represent the three Posts
// 2) Represent the Disks on the Posts.
// 3) Draw the Posts
// 4) Draw the Disks
// 5) Move a Disk
//
// Graphical Representation of Posts
//
//         |               |               |
//         |               |               |
//         |               |               |
//         |               |               |
//         |               |               |
//         |               |               |
// 1<--N-->|<--N-->1<--N-->|<--N-->1<--N-->|<--N-->1
//	====================================================
//
// If the screen width is 80, then 80 = 6N+7 or N=12
//
//                         |<--N-->|<--N-->|
// Disk N will be drawn as  ******* *******
//
// An integer array will be used to store the size of the disks
// one each post.
//
// disk[post][level]
//
// where post is the post number (0,1,2) and level is the position
// in the stack with level=0 being the bottom.
//
// 1) TASK: Get data from User
// 2) TASK: Initialize the disk array.
// 3) TASK: Draw the structure (base and posts)
// 4) TASK: Draw the disks
// 5) TASK: Solve the Puzzle

//====================================================================
// DECOMPOSITION LEVEL 2
//====================================================================
//
// Taking each of the above tasks in turn:
//
// TASK: Get data from User
// 1) TASK: Get initial post
// 2) TASK: Get final post
//
// TASK: Initialize the disk array.
// 1) TASK: Empty all posts
// 1.1) SET: all array values to zero
// 2) TASK: Place Disks on posts starting with largest
// 2.1) SET: thisdisk = DISKS
// 2.2) WHILE (thisdisk > 0)
// 2.2.1) SET: thispost = InitialPost(config)
// 2.2.2) SET: level = StackHeight(disk, thispost)
// 2.2.3) SET: disk[thispost][level] = thisdisk
// 2.2.4) SET: thispost--

// TASK: Draw the structure (base and posts)
// 1) TASK: Draw the Base
// 1.1) SET: row = 24
// 1.2) SET: col = 1
// 1.3) WHILE: (col < 80)
// 1.3.1) CALL: gotoxy(col, row)
// 1.3.2) OUT: '='
// 1.3.3) SET: col++
// 2) TASK: Draw the Posts
// 2.1) SET: thispost = 0
// 2.2) WHILE: (thispost < POSTS)
// 2.2.1) TASK: Draw a post at that location that can hold all the disks.
// 2.2.1.1) CALL: DrawPost(thispost, DISKS)
// 2.2.2) SET: thispost++

// TASK: Draw the disks on all the posts
// 1) SET: post = 0
// 2) WHILE: (post < POSTS)
// 2.1) CALL: DrawDisksOnPost(disk, post)
// 2.2) CALL: post++

// TASK: Solve the Puzzle
// 1) WHILE: Puzzle is not solved.
// 1.1) TASK: Get a move from the user
// 1.2) IF: move is legal
// 1.2.1) TASK: Make move
// 1.3) ELSE:
// 1.2.1) TASK: Print Error Message
//
// Since only one disk can be moved at a time, a move can be fully
// described by knowing what post a disk is being moved from and what
// post it is being moved to. To facilitate passing this information
// between functions, we'll use an array such that:
//
// move[0] = from post
// move[1] = to post

//== MACRO DEFINITIONS ====================================================
#define DISKS (12)
#define POSTS (3)
#define FROM  (0)
#define TO    (1)
#define DRAWDISK ('*')
#define ERASEDISK (' ')
#define MANUAL    (0)
#define AUTOPLAY  (1)
#define AUTOPAUSE (2)
//== INCLUDE FILES ========================================================
#include <stdio.h> // printf(), scanf()
#include <stdlib.h> // RAND_MAX, srand(), rand()
#include <conio.h> // gotoxy(), putchar()

//== FUNCTION PROTOTYPES (functions called in main() ) ====================
void PrintHeader(void);
int  GetInitialPost(void);
int  GetTargetPost(void);
int  GetSolutionMode(void);
void InitializeDisks(int disk[POSTS][DISKS], int config);
void DrawPlatform(void);
void DrawDisks(int disk[POSTS][DISKS]);
long SolvePuzzle(int disk[POSTS][DISKS], int target, int mode);

//== MAIN FUNCTION ========================================================
int main(void)
{
	int disk[POSTS][DISKS];
	int start, target, mode;
	long moves;

	PrintHeader();
	printf("\n"); // Print a blank line

	// 1) TASK: Get data from User.
	start = GetInitialPost();
	target = GetTargetPost();
	mode = GetSolutionMode();

	// 2) TASK: Initialize the disk array.
	InitializeDisks(disk, start);

	// 3) TASK: Draw the structure (base and posts)
	DrawPlatform();

	// 4) TASK: Draw the disks
	DrawDisks(disk);

	// 5) TASK: Solve the Puzzle
	moves=SolvePuzzle(disk, target, mode);

	gotoxy(30,25);
	printf("  Total Moves: %i  ", moves);

	return(0);
}

//== SUPPORT FUNCTION PROTOTYPES (functions not called in main() ) ========

int InitialPost(int config);
int StackHeight(int disk[POSTS][DISKS], int post);
void DrawPost(int p, int disks);
void DrawDisksOnPost(int disk[POSTS][DISKS], int post);
void DrawDisk(int disk[POSTS][DISKS], int post, int height, int mode);
int IsPuzzleSolved(int disk[POSTS][DISKS], int target);
int IsMoveLegal(int disk[POSTS][DISKS], int move[]);
int MoveDisk(int disk[POSTS][DISKS], int move[]);
int SizeOfTopDisk(int disk[POSTS][DISKS], int pole);
long SolvePuzzleManually(int disk[POSTS][DISKS], int target);
long SolvePuzzleAutomatically(int disk[POSTS][DISKS], int target, int mode);
int PoleWithDisk(int disk[POSTS][DISKS], int disksize);
int DiskHeightOnPole(int disk[POSTS][DISKS], int pole, int disksize);
int OtherPole(int pole1, int pole2);
long MoveDisks(int disk[POSTS][DISKS], int disksize, int ToPole, int mode);
int WaitForKey(void);

//== SUPPORT FUNCTIONS ====================================================
void PrintHeader(void)
{
	printf("========================================"
			 "=======================================\n");
	printf("Course....... %s-%i (%s %i)\n", COURSE, SECTION, TERM, YEAR);
	printf("Programmer... %s (%s)\n", PROGRAMMER, PROG_CODE);
	printf("Assignment... %s (Rev %i) (Source Code in %s)\n",
		ASSIGNMENT, REVISION, FILENAME);
	printf("Description.. %s\n", TITLE);
	printf("              %s\n", SUBTITLE);
	printf("========================================"
			 "=======================================\n");

	return;
}

//====================================================================
// PSEUDOCODE FOR SUPPORT FUNCTIONS (called by main())
//====================================================================

int GetInitialPost(void)
{
	int i;

	gotoxy(1,8);
	printf("What post to start from (0,1,2) or -1 for random: ");
	scanf("%i", &i);
	return(i);
}

int GetTargetPost(void)
{
	int i;

	gotoxy(1,9);
	printf("What post to move all disks to: ");
	scanf("%i", &i);
	return(i);
}

int GetSolutionMode(void)
{
	int i;

	gotoxy(35,9);
	printf("Mode (0=manual, 1=auto, 2=auto w/pause): ");
	scanf("%i", &i);
	return(i);
}

// TASK: Initialize the disk array.
// 1) TASK: Empty all posts
// 1.1) SET: all array values to zero
// 2) TASK: Place Disks on posts starting with largest
// 2.1) SET: thisdisk = DISKS
// 2.2) WHILE (thisdisk > 0)
// 2.2.1) SET: thispost = InitialPost(config)
// 2.2.2) SET: level = StackHeight(disk, thispost)
// 2.2.3) SET: disk[thispost][level] = thisdisk
// 2.2.4) SET: thispost++

void InitializeDisks(int disk[POSTS][DISKS], int config)
{
	int p, d;
	int level;

	// 1) TASK: Empty all posts
	for(p=0; p<POSTS; p++)
	{
		for(d=0; d<DISKS; d++)
		{
			disk[p][d] = 0;
		}
	}

	// 2) TASK: Place Disks on posts starting with largest
	d = DISKS;
	while(d > 0)
	{
		p = InitialPost(config);
		level = StackHeight(disk, p);
		disk[p][level] = d;
		d--;
	}

	return;
}

// TASK: Draw the structure (base and posts)
// 1) TASK: Draw the Base
// 1.1) SET: row = 24
// 1.2) SET: col = 1
// 1.3) WHILE: (col < 80)
// 1.3.1) CALL: gotoxy(col, row)
// 1.3.2) OUT: '='
// 1.3.3) SET: col++
// 2) TASK: Draw the Posts
// 2.1) SET: thispost = 0
// 2.2) WHILE: (thispost < POSTS)
// 2.2.1) TASK: Draw a post at that location that can hold all the disks.
// 2.2.1.1) CALL: DrawPost(p, DISKS)
// 2.2.2) SET: thispost++

void DrawPlatform(void)
{
	int row, col, p;

	// TASK: Draw the structure (base and posts)
	row = 25;
	col = 1;

	while(col < 80)
	{
		gotoxy(col, row);
		putchar('=');
		col++;
	}

	// 2) TASK: Draw the Posts
	p = 0;
	while(p < POSTS)
	{
		DrawPost(p, DISKS);
		p++;
	}

	return;
}

// TASK: Draw the disks on all the posts
// 1) SET: post = 0
// 2) WHILE: (post < POSTS)
// 2.1) CALL: DrawDisksOnPost(disk, post)

void DrawDisks(int disk[POSTS][DISKS])
{
	int post;

	// TASK: Draw the disks on all the posts
	post = 0;
	while(post < POSTS)
	{
		DrawDisksOnPost(disk, post);
		post++;
	}

	return;
}

// TASK: Solve the Puzzle
// 1) WHILE: Puzzle is not solved.
// 1.1) TASK: Get a move from the user
// 1.2) IF: move is legal
// 1.2.1) TASK: Make move
// 1.3) ELSE:
// 1.2.1) TASK: Print Error Message

long SolvePuzzle(int disk[POSTS][DISKS], int target, int mode)
{

	switch(mode)
	{
		case AUTOPLAY:
		case AUTOPAUSE:
			return(SolvePuzzleAutomatically(disk, target, mode));
		case MANUAL:
			return(SolvePuzzleManually(disk, target));
		default:
			printf("Invalid Play Mode - program terminiated!\n");
	}

	return(-1);
}


//====================================================================
// PSEUDOCODE FOR SUPPORT FUNCTIONS (not called by main())
//====================================================================

int InitialPost(int config)
{
	switch(config)
	{
		case 0:
		case 1:
		case 2:
			return(config);
	}

	return(rand()%3);
}

int StackHeight(int disk[POSTS][DISKS], int post)
{
	int height;

	for(height = 0; disk[post][height] > 0; height++);

	return(height);
}

void DrawPost(int p, int disks)
{
	int col;
	int row;
	int i;

	col = (disks+2) + p*(2*disks+2);

	for(i = 0; i<disks; i++)
	{
		row = 24-i;
		gotoxy(col, row);
		putchar('|');
	}

	row = 24-i;
	gotoxy(col, row);
	putchar('0' + p);

	return;
}

// TASK: Draw the disks on a given post
// 1) SET: height = 0
// 2) WHILE: (height < StackHeight(disk, post)
// 2.1) CALL: DrawDisk(disk, post, height)
// 2.2) height++

void DrawDisksOnPost(int disk[POSTS][DISKS], int post)
{
	int height;

	height = 0;
	while(height < StackHeight(disk, post))
	{
		DrawDisk(disk, post, height, '*');
		height++;
	}

	return;
}

// TASK: Draw the disk on a given post at a given height
// 1) TASK: Find the row, col of the center of the disk
// 1.1) SET: col = (DISKS+2) + post*(2*DISKS+2)
// 1.2) SET: row = 24-height
// 2) TASK: Draw the actual disk as N *'s left and right of center
// 2.1) SET: i = 0
// 2.2) WHILE: (i < disk[post][height])
// 2.2.1) gotoxy(col-(i+1), row)
// 2.2.2) putchar('*')
// 2.2.1) gotoxy(col+(i+1), row)
// 2.2.2) putchar('*')
// 2.2.3) i++

void DrawDisk(int disk[POSTS][DISKS], int post, int height, int mode)
{
	int row, col;
	int i;

	// 1) TASK: Find the row, col of the center of the disk
	col = (DISKS+2) + post*(2*DISKS+2);
	row = 24-height;

	// 2) TASK: Draw the actual disk as N *'s left and right of center
	i = 0;
	while(i < disk[post][height])
	{
		gotoxy(col-(i+1), row);
		putchar(mode);
		gotoxy(col+(i+1), row);
		putchar(mode);
		i++;
	}

	return;
}

int IsPuzzleSolved(int disk[POSTS][DISKS], int target)
{
	return(DISKS == StackHeight(disk, target));
}

int IsMoveLegal(int disk[POSTS][DISKS], int move[])
{
	return(SizeOfTopDisk(disk, move[0]) < SizeOfTopDisk(disk, move[1]));
}

int MoveDisk(int disk[POSTS][DISKS], int move[])
{
	int height, d;

	// 1) TASK: Remove disk from "from" pole.
	// 1.1) TASK: Identify position of disk on "from" pole.
	height = StackHeight(disk, move[FROM]) - 1;

	// 1.2) TASK: Get the disk size of the disk being moved.
	d = disk[move[FROM]][height];

	// 1.3) TASK: Erase disk from "from" pole.
	DrawDisk(disk, move[FROM], height, ERASEDISK);

	// 1.4) TASK: Remove disk from "from" pole's data
	disk[move[FROM]][height] = 0;

	// 2) TASK: Place disk on "to" pole.
	// 1.1) TASK: Identify position of disk on "to" pole.
	height = StackHeight(disk, move[TO]);

	// 1.2) TASK: Add disk to "to" pole's data
	disk[move[TO]][height] = d;

	// 1.3) TASK: Draw disk on "to" pole.
	DrawDisk(disk, move[TO], height, DRAWDISK);

	return(1);
}

int SizeOfTopDisk(int disk[POSTS][DISKS], int pole)
{
	return(disk[pole][StackHeight(disk, pole) - 1]);
}

long SolvePuzzleManually(int disk[POSTS][DISKS], int target)
{
	long moves;
	int move[2];

	moves = 0;
	while( !(IsPuzzleSolved(disk, target)) )
	{
		gotoxy(1,10);
		printf("Move disk from which column: ");
		scanf("%i", &move[0]);

		gotoxy(40,10);
		printf("Move disk to which column: ");
		scanf("%i", &move[1]);

		gotoxy(1,11);
		printf("                         ");

		if(IsMoveLegal(disk, move))
			moves += MoveDisk(disk, move);
		else
		{
			gotoxy(1,11);
			printf("Illegal Move - Try again,");
		}
	}

	return(moves);
}

long SolvePuzzleAutomatically(int disk[POSTS][DISKS], int target, int mode)
{
	return(MoveDisks(disk, DISKS, target, mode));
}

long MoveDisks(int disk[POSTS][DISKS], int disksize, int ToPole, int mode)
{
	long moves;
	int move[2];
	int FromPole, SparePole;
	int nextsize;

	// BASIC CONCEPT
	//
	// Move Disk N to ToPole by following approach:
	//
	// 1) TASK: Find which pole Disk N is on
	// 2) IF: (Disk is one top)
	// 2.1) TASK: Move it to target pole
	// 3) ELSE:
	// 3.1) Move disk above it to nontarget pole
	// 3.2) Move it to target pole
	// 3.3) Move disk above it to target pole

	FromPole = PoleWithDisk(disk, disksize);
	move[FROM] = FromPole;
	move[TO] = ToPole;

	if(SizeOfTopDisk(disk, FromPole) == disksize)
	{
		MoveDisk(disk, move);
		if(AUTOPAUSE == mode)
			WaitForKey();
		moves = 1;
	}
	else
	{
		moves = 0;
		nextsize = disk[FromPole][DiskHeightOnPole(disk, FromPole, disksize)];
		SparePole = OtherPole(FromPole, ToPole);
		moves += MoveDisks(disk, nextsize, SparePole, mode);
		moves += MoveDisks(disk, disksize, ToPole, mode);
		moves += MoveDisks(disk, nextsize, ToPole, mode);
	}

	return(moves);
}

int PoleWithDisk(int disk[POSTS][DISKS], int disksize)
{
	int pole;

	for(pole=0; pole < POSTS; pole++)
	{
		if(0<DiskHeightOnPole(disk, pole, disksize))
			return(pole);
	}

	return(-1); // Should never get here
}

int DiskHeightOnPole(int disk[POSTS][DISKS], int pole, int disksize)
{
	int h;

	h = StackHeight(disk, pole);
	while((0<h)&&(disksize!=disk[pole][h-1]))
		h--;

	return(h);
}

int OtherPole(int pole1, int pole2)
{
	// pole numbers add to 3, so subtracting off the sum of two pole
	// numbers from 3 will yield the number of the other pole.

	return(3-pole1-pole2);
}

int WaitForKey(void)
{
	while(kbhit())
		getch();
	while(!kbhit())
		;
	return(getch());
}