/* Problem tzv. "hanojskih kula": data su tri vertikalna štapa, na jednom se nalazi n diskova
poluprečnika 1,2,3,... do n, tako da se najveći nalazi na dnu, a najmanji na vrhu. Ostala dva štapa su prazna.
Potrebno je premestiti diskove na drugi štap tako da budu u istom redosledu, premeštajući jedan po
jedan disk, pri čemu se ni u jednom trenutku ne sme staviti veći disk preko manjeg.

*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TOWER 100
#define MAX_NAME 64
/* Stuktura definise jednu hanojsku kulu */
typedef struct
{
    int s[MAX_TOWER]; /* Stap sa diskovima */
    int n; /* Broj diskova na stapu */
    char name[MAX_NAME]; /* Naziv kule */
} Tower;
/* Funkcija postavlja naziv kule na dato ime, a zatim na stap postavlja
diskove velicine n, n-1, ..., 2, 1 redom */
void init_tower(Tower * tower, char * name, int n)
{
    int i;
    strcpy(tower->name, name);
    tower->n = n;
    for(i = 0; i < n; i++)
        tower->s[i] = n - i;
}
/* Funkcija prikazuje sadrzaj na datoj kuli */
void print_tower(Tower * tower)
{
    int i;
    printf("%s: ", tower->name);
    for(i = 0; i < tower->n; i++)
        printf("%d ", tower->s[i]);
    putchar('\n');
}
/* Funkcija premesta jedan disk sa vrha prve kule na vrh druge kule */
void move(Tower *from, Tower * to)
{
    /* Proveravamo da li je potez ispravan */
    if(from->n == 0 || (to->n > 0 && from->s[from->n - 1] >= to->s[to->n - 1]))
    {
        printf("Ilegal move: %d from %s to %s!!\n",
               from->s[from->n - 1],
               from->name,
               to->name );
        exit(1);
    }
    else
    {
        /* Prikaz opisa poteza */
        printf("Moving disc %d from %s to %s\n",
               from->s[from->n - 1],
               from->name,
               to->name);
        /* Premestanje diska */
        to->s[to->n++] = from->s[--from->n];
    }
}
/* Rekurzivna funkcija koja premesta n diska sa kule x na kulu y. Kao
pomocna kula koristi se kula z. */
void hanoi(Tower *x, Tower *y, Tower * z, int n)
{
    /* Izlaz iz rekurzije */
    if(n == 0)
        return;
    /* Rekurzivno premestamo n - 1 disk sa x na z, pomocu kule y */
    hanoi(x, z, y, n - 1);
    /* Premestamo jedan disk sa x na y */
    move(x,y);
    /* Prikaz stanja kula nakon poteza */
    print_tower(x);
    print_tower(y);
    print_tower(z);
    /* Premestamo n - 1 disk sa z na y, pomocu kule x */
    hanoi(z, y, x, n - 1);
}
/* Test program */
int main()
{
    Tower x, y, z;
    int n;
    /* Ucitavamo dimenziju problema */
    scanf("%d", &n);
    /* Inicijalizujemo kule. Kula x ima n diskova, ostale su prazne */
    init_tower(&x, "X", n);
    init_tower(&y, "Y", 0);
    init_tower(&z, "Z", 0);
    /* Prikaz kula na pocetku */
    print_tower(&x);
    print_tower(&y);
    print_tower(&z);
    /* Poziv funkcije hanoi() */
    hanoi(&x, &y, &z, n);
    return 0;
}