/*
 * Towers of Hanoi
 *
 * This program solves the "Towers of Hanoi" problem, which is to move a stack
 * of different sized rings from one of three towers to another. Only one ring
 * may be moved at a time, and a ring may not be placed on top of a smaller
 * ring.
 *
 * Original Author Unknown
 *
 * Compile command: cc hanoi -fop
 */
#include <stdio.h>		/* Standard I/O definitions */
#include <video.h>		/* Video    I/O definitions */

#define POST			0xB3
#define POST_BASE		0xC1
#define BASE			0xC4
#define RING			0xDC

#define SCREEN_WIDTH	80
#define SCREEN_HEIGHT	25

#define RING_WIDTH		((((SCREEN_WIDTH-2)/3)&0xFE)-1)
#define LEFT_POST		(RING_WIDTH/2+1)
#define CENTER_POST		(LEFT_POST+RING_WIDTH)
#define RIGHT_POST		(LEFT_POST+2*RING_WIDTH)

#define MOVING_ROW		2
#define BASE_ROW		15
#define POST_HEIGHT		11

char top[3] = { BASE_ROW-1, BASE_ROW-1, BASE_ROW-1 };

/*
 * Main program, draw the posts & begin moving rings
 */
main(int argc, char *argv[])
{
	int nrings, i;

	if(argc != 2)
		abort("\nUse: hanoi <rings>\n");

	nrings = atoi(argv[1]);						/* Number of rings */

	vopen();

	/* Draw the posts */
	for(i = MOVING_ROW+2; i < BASE_ROW; ++i) {
		putxy(LEFT_POST, i, POST);
		putxy(CENTER_POST, i, POST);
		putxy(RIGHT_POST, i, POST); }

	/* Draw the base */
	vgotoxy(0, BASE_ROW);
	for(i = 1; i < SCREEN_WIDTH; ++i)
		vputc(BASE);

	/* Draw the post-base connections */
	putxy(LEFT_POST, BASE_ROW, POST_BASE);
	putxy(CENTER_POST, BASE_ROW, POST_BASE);
	putxy(RIGHT_POST, BASE_ROW, POST_BASE);

	/* Draw the title */
	vgotoxy(30, BASE_ROW+2);
	V_ATTR = REVERSE;
	vputs(" TOWERS OF HANOI ");
	V_ATTR = NORMAL;

	/* Draw the initial ring positions */
	for(i = nrings; i > 0; --i)
		draw(i, LEFT_POST, top[0]--, RING);

	/* Perform the movements */
	hanoi(nrings, 0, 2, 1);
	vgotoxy(0, 20);
}

/*
 * Performs towers of hanoi movements by recursing from the current
 * position to the bottom of the ring stack, moving a single ring,
 * and walking back up again, re-arranging the movements with each
 * recursion.
 */
hanoi(char n, char a, char b, char c)
{
	if(n) {
		hanoi(n-1, a, c, b);
		movering(n, a, b);
		hanoi(n-1, c, b, a); }
}

/*
 * Place a character on the screen at a specified X/Y address
 */
putxy(int x, int y, char c)
{
	vgotoxy(x,y);
	vputc(c);
}

/*
 * Draw a ring at a position on the screen
 */
draw(char ring, char centre, char y, char c)
{
	char i;

	vgotoxy(centre-ring, y);

	for(i=0; i<ring; ++i)
		vputc(c);

	vgotoxy(centre+1, y);

	for(i=0; i<ring; ++i)
		vputc(c);
}

/*
 * Move a ring between two posts by repeatedly drawing and erasing it
 */
movering(char ring, char from, char to)
{
	char fromc, toc;
	char fromy, toy;

	fromc = LEFT_POST + from * RING_WIDTH;
	toc = LEFT_POST + to * RING_WIDTH;
	fromy = ++top[from];
	toy = top[to]--;

	while(fromy != MOVING_ROW) {
		draw(ring, fromc, fromy, ' ');
		draw(ring, fromc, --fromy, RING);
		delay(50); }

	if(fromc < toc)
		while(fromc != toc) {
			putxy(fromc-ring, fromy, ' ');
			putxy(fromc, fromy, RING);
			putxy(fromc+1, fromy, ' ');
			putxy(fromc+ring+1, fromy, RING);
			++fromc;
			delay(50); }
	else if (fromc > toc)
		while(fromc != toc) {
			putxy(fromc+ring, fromy, ' ');
			putxy(fromc, fromy, RING);
			putxy(fromc-1, fromy, ' ');
			putxy(fromc-ring-1, fromy, RING);
			--fromc;
			delay(50); }

	while(fromy != toy) {
		draw(ring, fromc, fromy, ' ');
		draw(ring, fromc, ++fromy, RING);
		delay(50); }
}