#include <stdio.h>
#include <stdlib.h>
typedef struct lista
{
    int valor;
    struct lista *prox;
} Lista;

typedef struct pilha
{
    Lista *topo;
}Pilha;


Pilha*Criar ()
{
    Pilha* p = (Pilha*) malloc(sizeof(Pilha));
    p->topo = NULL;
    return p;
}

void Preencher(Pilha* p, int*vetor,int i)
{
    Lista* novo = (Lista*) malloc(sizeof(Lista));
    if(novo==NULL)
    {
        printf("Erro na alocacao\n");
        exit(1);
    }
    novo->valor = vetor[i];
    novo->prox = p->topo;
    p->topo = novo;
}
void pilha_imprime (Pilha* p,FILE*saida)
{
    Lista* q;
    for (q=p->topo; q!= NULL; q = q->prox)
    {
       printf("%d ",q->valor);
    }
    printf("\n");
}
int pilha_vazia (Pilha* p)
{
    return (p->topo == NULL);
}
float pilha_pop (Pilha* pino1,Pilha* pino2,Pilha* pino3,char aux)
{
    Lista* t;
    float v;
    if(aux=='A')
    {
        if (pilha_vazia(pino1))
        {
            printf("Pilha vazia\n");
            exit(1);
        }
        t = pino1->topo;
        v = t->valor;
        pino1->topo = t->prox;
        free(t);
    }
    else if(aux=='B')
    {
        if (pilha_vazia(pino2))
        {
            printf("Pilha vazia\n");
            exit(1);
        }
        t = pino2->topo;
        v = t->valor;
        pino2->topo = t->prox;
        free(t);
    }
    else if(aux=='C')
    {
        if (pilha_vazia(pino3))
        {
            printf("Pilha vazia\n");
            exit(1);
        }
        t = pino3->topo;
        v = t->valor;
        pino3->topo = t->prox;
        free(t);
    }
return v;
}
void pilha_push (Pilha* pino1,Pilha* pino2,Pilha* pino3,char aux, float v)
{
    Lista* novo = (Lista*) malloc(sizeof(Lista));
    if(aux=='A')
    {
        novo->valor = v;
        novo->prox = pino1->topo;
        pino1->topo = novo;
    }
    else if(aux=='B')
    {
        novo->valor = v;
        novo->prox = pino2->topo;
        pino2->topo = novo;
    }
    else if(aux=='C')
    {
        novo->valor = v;
        novo->prox = pino3->topo;
        pino3->topo = novo;
    }
}
void imprimir(Pilha*Pino1,Pilha*Pino2, Pilha*Pino3,int*movimento,FILE*saida)
{
    printf("movimento eh %d \n",*movimento);
    printf("Torre A:");
    pilha_imprime (Pino1,saida);
    printf("Torre B:");
    pilha_imprime (Pino2,saida);
    printf("Torre C:");
    pilha_imprime (Pino3,saida);
    printf("\n");
}
void mover(int tamanho, Pilha*pino1,Pilha*pino2,Pilha*pino3,int *movimento,FILE*saida,char origem,char temp,char destino)
{
    *movimento += 1;
//    printf("movimento eh %d\n",*movimento);
    int aux;
    if (tamanho == 1)
    {
        aux=pilha_pop(pino1,pino2,pino3,origem);
        pilha_push(pino1,pino2,pino3,destino,aux);
        imprimir(pino1,pino2,pino3,movimento,saida);
    }
    else
    {
        mover (tamanho-1,pino1,pino2,pino3,movimento,saida,origem,destino,temp);
        aux=pilha_pop(pino1,pino2,pino3,origem);
        pilha_push(pino1,pino2,pino3,destino,aux);
        imprimir(pino1,pino2,pino3,movimento,saida);
        mover (tamanho-1,pino1,pino2,pino3,movimento,saida,temp,origem,destino);
    }
}


int main()
{
    Pilha *Pino1=Criar();
    Pilha *Pino2=Criar();
    Pilha *Pino3=Criar();
    int total,i,movimento=0;
    int*vetor;
    FILE*entrada=fopen("L6Q2.in","r");
    if (entrada==NULL)
    {
        printf("Erro ao abrir arquivo\n");
        exit(1);
    }
    FILE*saida=fopen("L6Q1.out","w");
    if (saida==NULL)
    {
        printf("Erro ao abrir arquivo\n");
        exit(1);
    }
    fscanf(entrada,"%d",&total);
    printf("total eh %d\n",total);
    vetor=(int*)malloc(total*sizeof(int));
    if(vetor==NULL)
    {
        printf("erro de alocacao\n");
        exit(1);
    }
    for(i=0;i<total;i++)
    {
        fscanf(entrada,"%d",&vetor[i]);
    }

    for(i=total-1;i!=-1;i--)
    {
        Preencher(Pino1,vetor,i);
    }
    char origem='A';
    char temp='B';
    char destino='C';
    mover(total,Pino1,Pino2,Pino3,&movimento,saida,origem,temp,destino);
    return 0;
}