/*

	ハノイの塔

	        |       22|22       |
	        |        1|1        |
	        |         |         |
	        |         |         |
	     333|333      |         |
	  666666|666666   |         |
	 7777777|7777777  |     4444|4444
	88888888|88888888 |    55555|55555

	このスタイルで表示する。（実際は左の端から表示する。）

	二重配列 a[3][N+1] には、それぞれの棒にささっている円盤の番号が右詰めで格納
	されている。上の状態では

		?, -1, -1, -1, -1,  2,  5,  6,  7
		?, -1, -1, -1, -1, -1, -1,  0,  1
		?, -1, -1, -1, -1, -1, -1,  3,  4

	である。（-1 は空であることの印。また、a[i][0] は使わない。）
*/
#include <stdio.h>

#define N 16	/* 円盤の数。4*N+4 がコンソールのカラム数を越えないよう。*/ 
				/* （どうして 4*N+4 なのかは省略。）*/

#define gotoxy(X, Y)	printf("\033[%d;%dH", (X), (Y))
	/* X 行 Y カラム目へカーソルを移動するエスケープシーケンスを出力 */

#define clear_screen()	printf("\033[2J")
	/* 画面クリアのエスケープシーケンスを出力 */

void init_show(void);
void hanoi(int n, int from, int to);
void move_show(int n, int from, int to);

int a[3][N+1];

main() {
	init_show();
	hanoi(N, 0, 1);
	gotoxy(N+1, 1);
}


/* 初期化と表示 */
void init_show(void) {
	int i, j;

	clear_screen();					/* 画面クリア */

	for (i = 1; i <= N; i++) {		/* 配列 a[][] の初期化 */
		a[0][i] = i;
	}
	for (i = 1; i <= N; i++) {
		a[1][i] = a[2][i] = -1;
	}
	for (i = 1; i <= N; i++) {		/* 画面の表示 */
		gotoxy(i, N-i+1);
		for (j = 0; j < i; j++) {
			printf("%x", i%16);		/* 十六進で下一けただけを表示 */
		}
		printf("|");				/* 棒 0 の印 */
		for (j = 0; j < i; j++) {
			printf("%x", i%16);
		}
		gotoxy(i, 2*N+3); printf("|");	/* 棒 1 の印 */
		gotoxy(i, 3*N+5); printf("|");	/* 棒 2 の印 */
	}
}


/* 円盤 1 から円盤 n までを、棒 from から棒 to へ移す */
void hanoi(int n, int from, int to) {
	if (n == 1) {
		move_show(1, from, to);
	} else {
		hanoi(n-1, from, 3-from-to);
		move_show(n, from, to);
		hanoi(n-1, 3-from-to, to);
	}
}


/* 円盤 n が棒 from の一番上にあると仮定し、それを棒 to へ移す。表示も変える */
/* （棒を再度書くのは、もう一度エスケープシーケンスを出すよりたぶん速いため）*/
void move_show(int n, int from, int to) {
	int i, j;

	for (i = 1; a[from][i] == -1; i++) {	/* 円盤 n を探す */
		;
	}
	a[from][i] = -1;						/* それを消す */
	if (from == 1) {						/* 表示を消すためのカーソル移動 */
		gotoxy(N+1-i, (from+1)*N+2*from-n+1);
	} else {
		gotoxy(i, (from+1)*N+2*from-n+1);
	}
	for (j = 0; j < n; j++) {				/* 実際に消す（左半分）*/
		printf(" ");
	}
	printf("|");							/* 棒を書く */
	for (j = 0; j < n; j++) {				/* 実際に消す（右半分）*/
		printf(" ");
	}
	for (i = 1; i <= N && a[to][i] == -1; i++) {	/* 収まるべき位置を探す */
		;
	}
	a[to][i-1] = n;							/* そこに置く*/
	if (to == 1) {							/* 表示するためのカーソル移動 */
		gotoxy(N+2-i, (to+1)*N+2*to-n+1);
	} else {
		gotoxy(i-1, (to+1)*N+2*to-n+1);
	}
	for (j = 0; j < n; j++) {				/* 実際に書く（左半分）*/
		printf("%x", n%16);
	}
	printf("|");							/* 棒を書く */
	for (j = 0; j < n; j++) {				/* 実際に書く（右半分）*/
		printf("%x", n%16);
	}
}