#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int k;	//紀錄有幾個Plate 
int *a, *b, *c; //用來製作三個Stack 

void hanoi(int n, int *form, int *mid, int *to, char a, char b, char c);
int pop(int *pillar); 
void push(int temp, int *pillar);
void print(int *a, int *b, int *c, int n);

void hanoi(int n, int *form, int *mid, int *to, char ta, char tb, char tc)
{
	if(n == 0)
		return ;
    hanoi(n-1, form, to, mid, ta, tc, tb);
    push(pop(form), to);
    printf("Move disks %d from %c -> %c\n",n , ta, tc);
    print(a, b, c, k-1);
    printf("\n");
	hanoi(n-1, mid, form, to, tb, ta, tc); 
}

int pop(int *pillar)
{
	int temp;
	int i = 0;

	while(*(pillar+i) != 0)
		i++;
	i--;
	temp = *(pillar+i);
	*(pillar+i) = 0;
	return temp;
}

void push(int temp, int *pillar)
{
	int i = 0;
	while(pillar[i] != 0)
		i++;
	*(pillar+i) = temp;
}

void print(int *a, int *b, int *c, int n)
{	
	int i, j;
	
	printf("Tower A:  ");
	for(i = 0; i < n; i++)
		printf("%d  ", a[i]);
	printf("\n");
	
	printf("Tower B:  ");
	for(i = 0; i < n; i++)
		printf("%d  ", b[i]);
	printf("\n");
	
	printf("Tower C:  ");
	for(i = 0; i < n; i++)
		printf("%d  ", c[i]);
	printf("\n");
}

int main()
{
    int i, n;
    
    printf("《Tower of Brahma puzzle》\n\n");
    printf("Enter the number of disks: ");
    scanf("%d",&n); //輸入圓盤的數量 
    k = n+1;
    
 	//創造三個空堆節 
    a = (int*)malloc(sizeof(int)*k);
    b = (int*)malloc(sizeof(int)*k);
    c = (int*)malloc(sizeof(int)*k);
    memset(a, 0, sizeof(int)*k);
    memset(b, 0, sizeof(int)*k);
    memset(c, 0, sizeof(int)*k);
	
	for(i = 0; i < n; i++)
		a[i] = n - i;
    
    print(a, b, c, n);
    printf("\n");
    hanoi(n, a, b, c, 'A', 'B', 'C');
    printf("End of the world");
    
	return 0;    
}