/*

	ハノイの塔

	       |              |              |
	       |              |              |
	       |              |              |
	       |              |              |
	     22222            |              |
	  55555555555         |              |
	 6666666666666        0           3333333
	777777777777777      111         444444444

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

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

		-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 は空であることの印。）
*/
#include <stdio.h>

#define N 16	/* 円盤の数。6*N-4 がコンソールのカラム数を越えないよう。  */
				/* （最大の円盤のカラム数は 2*N-1 なので、それが隙間なしに */
				/* 並ぶと 6*N-3 だが、最大の円盤は右端の棒にはささらないの */
				/* で、6*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];

main() {
	init_show();		/* 初期化と表示 */
	hanoi(N-1, 0, 1);
	gotoxy(N+1, 1);		/* 終了後、プロンプトが適切な位置に出るように */
}


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

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

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


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