/*

	ハノイの塔

          27:    ....2567|    ......01|    ......34|

	このスタイルで、一ステップにつき一行で表示する。この例は、27 ステップ目、
	棒 0 には円盤 2, 5, 6, 7 が、棒 1 には円盤 0, 1 が、棒 2 には円盤 3, 4 が
	ささっている、と読む。（円盤は番号が小さいほど小さい。）

	二重配列 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		/* 円盤の数。16 以下（表示の都合）*/

void init(void);
void hanoi(int n, int from, int to);
void move(int n, int from, int to);
void show(void);

int a[3][N];
int count = 0;		/* 何ステップ目かのカウンタ */

main() {
	init(); show();
	hanoi(N-1, 0, 1);
}


/* 初期化 */
void init(void) {
	int i;

	for (i = 0; i < N; i++) {
		a[0][i] = i;
	}
	for (i = 0; i < N; i++) {
		a[1][i] = a[2][i] = -1;
	}
}


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


/* 円盤 n が棒 from の一番上にあると仮定し、それを棒 to へ移す */
void move(int n, int from, int to) {
	int i;

	for (i = 0; a[from][i] == -1; i++) {		/* 円盤 n を探す */
		;
	}
	a[from][i] = -1;							/* それを消す */
	for (i = 0; i < N && a[to][i] == -1; i++) {	/* 収まるべき位置を探す */
		;
	}
	a[to][i-1] = n;								/* そこに置く */
}


/* 円盤の配置を表示 */
void show(void) {
	int i, j;

	printf("%12d:", count);
	for (j = 0; j < 3; j++) {			/* j は棒の番号 */
		printf("    ");
		for (i = 0; i < N; i++) {		/* i は円盤の番号 */
			if (a[j][i] == -1) {
				printf(".");			/* 空きの印 */
			} else {
				printf("%x", a[j][i]);	/* 十六進で表示 */
			}
		}
		printf("|");					/* 床の印 */
	}
	printf("\n");
}