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

#define N 1000

void InitStacks(int Left[],int Right[],int height)
{
	int i;
	for(i=0;i<=height-1;i++)
	{
		Left[i]=1;//i;
		Right[i]=0;//i+height;
	}
	for(i=height;i<=N-1;i++)
	{
		Left[i]=-1;
		Right[i]=-1;
	}
}

void PrintStacks(int Left[],int Right[],int height)
{
	int i;
	for(i=height-1;i>=0;i--)
	{
		printf("%d %d\n",Left[i],Right[i]);
	}
	printf("\n");
}

void PrintCombined(int Combined[],int height)
{
	printf("-----Combined----\n");
	int i=0;
	for(i=2*height-1;i>=0;i--)
		printf("%d [i=%d]\n",Combined[i],i);
	printf("-----------------\n");
}
	
void PrintStacksStaggered(int Left[],int Right[],int height)
{
	int i;
	printf("----------------------------\n");
	for(i=height-1;i>=0;i--)
	{
		printf("%d  \n",Left[i]);
		printf("  %d\n",Right[i]);
	}
	printf("----------------------------\n");
}	
	
void CombineStacks(int Left[],int Right[],int Combined[],int height)
{
	int i;
	for(i=0;i<=height-1;i++)
	{
		Combined[2*i]=Right[i];
		Combined[2*i+1]=Left[i];
	}
	for(i=2*height;i<=2*N-1;i++)
		Combined[i]=-1;
}

void SplitStacks(int Left[],int Right[],int Combined[],int height)
{
	int i;
	for(i=0;i<=height-1;i++)
		Left[i]=Combined[i];
	for(i=height;i<=2*height-1;i++)
		Right[i-height]=Combined[i];
}

int CompareStacks(int Left[],int Right[],int LeftOrig[],int RightOrig[],int height)
{
	int i=0,flag=0;
	
	while ((i<=height-1) && (flag!=1))
	{
		if ((Left[i]!=LeftOrig[i]) || (Right[i]!=RightOrig[i]))
			flag=1;
		i++;
	}
	return flag;
}
int SolveStack(int Left[],int Right[],int LeftOrig[],int RightOrig[],int Combined[],int height)
{

	int j=0;
	do
	{
		CombineStacks(Left,Right,Combined,height);	
		SplitStacks(Left,Right,Combined,height);
		j++;
	} while (CompareStacks(Left,Right,LeftOrig,RightOrig,height)!=0);

	return j;
}


void SolveAll(int Left[],int Right[],int LeftOrig[],int RightOrig[],int Combined[],int Results[],int height)
{
	int j;
	for(j=1;j<=height;j++)
	{
		InitStacks(Left,Right,j);
		InitStacks(LeftOrig,RightOrig,j);
		Results[j-1]=SolveStack(Left,Right,LeftOrig,RightOrig,Combined,j);
	}
}

int main()
{
	int Left[N],LeftOrig[N],LeftClean[N];
	int Right[N],RightOrig[N],RightClean[N];
	int Combined[2*N];
	int Results[N];
	int height;
	int select;
	int j;

	//------------------------Intro "Grpahics"	
	system("clear");
	printf("*********************************************************\n");
	printf("***********************Welcome To:***********************\n");
	printf("****************Chip Stack Solver 0.5********************\n");
	printf("**********************by Leav Oz-Ari*********************\n");
	printf("*********************************************************\n\n\n");
	//------------------------End Intro "Graphics"
	printf("--------Select-Action--------\n");
	printf("1)Generate List of shuffles per stack for stacks under a certain height\n");
	printf("2)Find number of shuffles for a particular stack height\n");
	printf("3)Determine whether your stack will ever solve\n");
	printf("4)Show Sequence for Specific Stack Height\n");
	scanf("%d",&select);
	switch(select)
	{
		case 1:
			printf("\nUp to what stack height do you want the list?\n");
			scanf("%d",&height);
			SolveAll(Left,Right,LeftOrig,RightOrig,Combined,Results,height);
			for(j=1;j<=height;j++)
				printf("\n%d;%d",j,Results[j-1]);
			printf("\n\n");
			break;
		case 2:
			printf("\n\nHow high is each stack?\n");
			scanf("%d",&height);
			InitStacks(Left,Right,height);
			InitStacks(LeftOrig,RightOrig,height);
			Results[height-1]=SolveStack(Left,Right,LeftOrig,RightOrig,Combined,height);
			printf("\nYou will need %d shuffles to solve a stack %d chips high.\n\n\n",Results[height-1],height);
			break;
		case 3:
			printf("\n\nHow high is each stack?\n");
			scanf("%d",&height);
			printf("\n\nPlease enter the 1 and 0 for the chip colors.\n");
			printf("Start from left stack, bottom chip first:\n");
			for(j=0;j<=height-1;j++)
			{
				scanf("%d",&Left[j]);
				LeftOrig[j]=Left[j];
			}
			printf("And now the right stack, bottom chip first:\n");
			for(j=0;j<=height-1;j++)
			{
				scanf("%d",&Right[j]);
				RightOrig[j]=Right[j];
			}
			InitStacks(LeftClean,RightClean,height);
			j=0;
			do
			{	
				CombineStacks(Left,Right,Combined,height);	
				SplitStacks(Left,Right,Combined,height);
				j++;
				PrintStacks(Left,Right,height);
				sleep(1);
			} while ((CompareStacks(Left,Right,LeftOrig,RightOrig,height)!=0) && (CompareStacks(Left,Right,LeftClean,RightClean,height)!=0));
			if(CompareStacks(Left,Right,LeftOrig,RightOrig,height)==0)
				printf("Proved Unsolveable after %d steps\n\n\n",j);
			if(CompareStacks(Left,Right,LeftClean,RightClean,height)==0)
				printf("Solved after %d steps!\n\n\n",j);
			break;
		case 4:
			j=0;
			printf("\n\nWhich stack height would you like to print?\n");
			scanf("%d",&height);
			InitStacks(Left,Right,height);
			InitStacks(LeftOrig,RightOrig,height);
			do
			{
				printf("\n\n\n-------Shuffle Number %d-----------\n",j);
				PrintStacks(Left,Right,height);
				CombineStacks(Left,Right,Combined,height);	
				SplitStacks(Left,Right,Combined,height);
				printf("----------------------------------");
				j++;
			} while (CompareStacks(Left,Right,LeftOrig,RightOrig,height)!=0);

			printf("\n\n\n-------Shuffle Number %d-----------\n",j);
			PrintStacks(Left,Right,height);
			printf("----------------------------------\n\n\n");
			break;
						
	}
	
	return 0;
}