#include <iostream>
#include <math.h>

// format vstupnich dat:
//	objem kyblu
// pocatek
// konec

using namespace std;

#define N 5	// pocet kyblu

#define EMPTY 1	// operace s kyblama
#define FILL 2
#define POUR 3

FILE *src,*dest;	// in/out soubory

char metoda=0;	// metoda reseni

unsigned int visitedNodes;	// pocet navstivenych bodu stavoveho prostoru
unsigned int manipulBucket;		// delka cesty k reseni (pocet manipulaci s kybly)

int bucketCapacity[N];		// kapacita kyblu
int bucketDesired[N];	// koncovy stav
int actual[N];		// aktualni stav kyblu

typedef struct Tnode {
	int buck[N];	// aktualni stav
	int source;		// zdrojovy kybl
	int dest;	// cilovy kybl
	int how;		//jakou operaci bylo soucasneho stavu dosazeno
	long sort;	// cena podle ktere se radi ve fronte
	Tnode *next;	// ukazatel na dalsi uzel ve fronte
	Tnode *prev;	// ukazatel na predchudce ve stromu
};

Tnode *oStart, *oAct;	// otevrene uzly
Tnode *cStart, *cAct;	// uzavrene uzly

//---------------------------------------------------------------------------------

bool CheckSolution(void) { // je aktualni stav resenim?
	for (int i=0; i<N; i++)
		if (bucketDesired[i]!=actual[i])
			return false;
	return true;
}

int Heurestic(void) {	// oceni aktualni stav
	long sort,sort2;
	int tmp,i;
	
	sort=0; sort2=0;
	
	switch (metoda) {
	case 0:
		for (i=0; i<N; i++) {
			if (actual[i]==bucketDesired[i])
				sort++;
		}
		return sort;
	case 1:
		for (i=0; i<N; i++) {
			tmp=bucketDesired[i]-actual[i];
			sort+=tmp*tmp;	// sumi(SQR(Xi-Ri)
		}
		return (long) -sort; // SQRT(sumi(SQR(Xi-Ri)))
	case 2:
		for (i=0; i<N; i++) {
			tmp=bucketDesired[i]-actual[i];
			sort+=tmp*tmp;	// sumi(SQR(Xi-Ri))
			sort2+=abs(tmp);	// sumi(Xi-Ri)
		}
		return (long) -(sort+sort2*sort2/N);	// sumi(SQR(Xi-Ri))+SQR(sumi(Xi-Ri))/n		
	}
}

Tnode* MakeNode(void) { // novy uzel do fronty naplneny actualem
	Tnode *novy;
	int i;
	int sort=0;
	int tmp;

	novy=new Tnode;
	for (i=0; i<N; i++) {
		novy->buck[i]=actual[i];
	}
	
	novy->sort=Heurestic();
	novy->next=NULL;
	novy->prev=cStart;
	return (novy);
}

bool CheckQueue(void) { //prohleda fronty vsech uzlu, zda stav nebyl jiz zpracovavan
	Tnode *tmp;
	bool found;
	int i;

	tmp=oStart;	// otevrene uzly
	while (tmp!=NULL) {
		found=true;
		i=0;
		while ((i<N) && (found)) {
			if (tmp->buck[i]!=actual[i])
				found=false;
			i++;
		}
		if (found)
			return true;
		else
			tmp=tmp->next;
	}

	tmp=cStart;	// zavrene uzly
	while (tmp!=NULL) {
		found=true;
		i=0;
		while ((i<N) && (found)) {
			if (tmp->buck[i] != actual[i])
				found=false;
			i++;
		}
		if (found)
			return true;
		else
			tmp=tmp->next;
	}
	
	return false;
}

void Put(Tnode *novy) {	// zatridi uzel do fronty oterenych
	Tnode *tmp,*prevtmp;
	bool found=false;
	
	tmp=oStart;
	if (tmp!=NULL) {
		if (novy->sort > tmp->sort) {
			novy->next=oStart;
			oStart=novy;
		} else {
			prevtmp=tmp;
			tmp=tmp->next;
			while ((tmp!=NULL) && (!found)) {
				if (novy->sort > tmp->sort) {
					novy->next=tmp;
					prevtmp->next=novy;
					found=true;
				} else {
					prevtmp=tmp;
					tmp=tmp->next;
				}
			}
			if (!found) {
				prevtmp->next=novy;
				novy->next=NULL;
			}
		}
	} else {
		oStart=novy;
		oStart->next=NULL;
	}
}

void Empty(int which)	// vyliti kyble
{
	int tmp;
	Tnode *novy;

	if (actual[which]!=0) {	// neni uz prazdnej
		tmp=actual[which];
		actual[which]=0;
		if (!CheckQueue()) {	// kdyz je uz tento stav nekde ve fronte tak neresi
			novy=MakeNode();
			novy->source=which;
			novy->how=EMPTY;
			Put(novy);
		}
		actual[which]=tmp;
	}
}

void Fill(int which)	// naplneni kyble
{
	int tmp;
	Tnode *novy;

	if (actual[which]!=bucketCapacity[which]) {	// neni uz plnej
		tmp=actual[which];
		actual[which]=bucketCapacity[which];
		if (!CheckQueue()) {	// neni ve fronte
			novy=MakeNode();
			novy->dest=which;
			novy->how=FILL;
			Put(novy);
		}
		actual[which]=tmp;
	}
}

void Pour(int from, int to)	// preliti kyblu
{
	int fromTmp, toTmp;
	int howMuch;	// kolik se preleje vody
	Tnode *novy;

	if ((actual[from]!=0) && (actual[to]!=bucketCapacity[to])) {	// je co kam prelejt
		fromTmp=actual[from]; 
		toTmp=actual[to];
		howMuch=bucketCapacity[to]-actual[to];
		if ((actual[from]-howMuch)>=0) {	// cilovej se naplni
			actual[from]-=howMuch;
			actual[to]+=howMuch;
		} else 
		{	// preleje se vse ale neni plnej
			actual[to]+=actual[from];
			actual[from]=0;
		}
		if (!CheckQueue()) {
			novy=MakeNode();
			novy->source=from;
			novy->dest=to;
			novy->how=POUR;
			Put(novy);
		}
		actual[from]=fromTmp;
		actual[to]=toTmp;
	}
}

void GenerateStates(void) { // generace vsech stavu
	int i, j;

	for (i=0; i<N; i++)	// vyliti
		Empty(i);
	for (i=0; i<N; i++)	// naplneni
		Fill(i);
	for (i=0; i<N; i++)	// preliti
		for (j=0; j<N; j++)
			if (i!=j)
				Pour(i,j);
}

//---------------------------------------------------------------------------------

int main(int argc, char *argv[])
{
	char str[20];
	Tnode *tmp, *turn;
	int i;
	bool found;

	printf("Buckets problem 2005 by GS.\n");
  	printf("Input file: buck_[0-99].txt\n");
  	printf("Output file: output_[parameter]_[0-99].txt\n");
  	printf("Possible parameter: [0-1] (default 0)\n");
	printf(" 0: price = number of buckets in desired state\n");
	printf(" 1: price = euclid distance\n");
  	printf("\n");

	if (argc>1) metoda= (unsigned char) atoi(argv[1]);
	if (metoda<0 || metoda>1) metoda=0;
	printf("  %d selected. Working.....\n\n",metoda);

  	for (int nr=0; nr<=99; nr++) {
    	sprintf(str,"buck_%d.txt",nr);
		if ((src=fopen(str,"r"))==NULL) continue;
    	sprintf(str,"output_%d_%d.txt",metoda,nr);
    	if ((dest=fopen(str,"w"))==NULL) {
			printf("Error opening %s output file. Skipping.\n",str);
      		fclose(src);
      		continue;
    	}
		printf("  now solving buck_%d.txt\n",nr);
		
		// nacteni dat ze souboru
	   for (i=0; i<N; i++)
			fscanf(src,"%d\t",&bucketCapacity[i]);
	   for (i=0; i<N; i++)
			fscanf(src,"%d\t",&actual[i]);
	   for (i=0; i<N; i++)
			fscanf(src,"%d\t",&bucketDesired[i]);
			
		// vystup do souboru
	   for (i=0; i<N; i++)
			fprintf(dest,"%d\t",i+1);
		fprintf(dest,"\n");
	   for (i=0; i<N; i++)
			fprintf(dest,"%d\t",bucketCapacity[i]);
		fprintf(dest,"\n\n");
		
		// init promennych
		cStart=NULL;
		cAct=NULL;
		oStart=MakeNode();
		
		oStart->source=-1;
		oStart->dest=-1;
		oStart->how=-1;
		
		oAct=oStart;
		
		visitedNodes=0;
		manipulBucket=0;
		
		found=false;
		//----------------
		
		while ((oStart!=NULL) && (!found)) {
			oAct=oStart->next;	// prvni z fronty otevrenych na zacatek fronty uzavrenych
			oStart->next=cStart;
			cStart=oStart;
			oStart=oAct;

			for (i=0; i<N; i++)
				actual[i]=cStart->buck[i];

			if (!CheckSolution())
				GenerateStates();
			else
				found=true;
				
			visitedNodes++;
			if (visitedNodes%500==0) printf("\n%d",visitedNodes);
		}
		
		if (found) {
			// otocit smer prev
			cAct=cStart;
			turn=cStart;
			tmp=NULL;
			while (cAct->prev!=NULL) {
				turn=cAct->prev;
				cAct->prev=tmp;
				tmp=cAct;
				cAct=turn;
				manipulBucket++;
			}
			cAct->prev=tmp;
			
			// vypis reseni
			while (cAct!=NULL) {
				for (i=0; i<N; i++)
					fprintf(dest,"%d\t",cAct->buck[i]);
				switch (cAct->how) {
					case EMPTY:
						fprintf(dest,"empty %d\n",cAct->source+1);
						break;
					case FILL:
						fprintf(dest,"fill %d\n",cAct->dest+1);
						break;
					case POUR:
						fprintf(dest,"pour %d to %d\n",cAct->source+1,cAct->dest+1);
						break;
					default:
						fprintf(dest,"\n");
						break;
				}
				cAct=cAct->prev;
			}

			fprintf(dest,"\n%d manipulations\n%d visited nodes\n",manipulBucket,visitedNodes);
		} else
			fprintf(dest, "Solution not found.\n");		
				

		//	smazani promennych
		oAct=oStart;
		while (oAct!=NULL) {
			tmp=oAct;
			oAct=oAct->next;
			delete tmp;
		}
		cAct=cStart;
		while (cAct!=NULL) {
			tmp=cAct;
			cAct=cAct->next;
			delete tmp;
		}
		
   	fclose(dest); 
		fclose(src);
  	}
	printf("\n  ...............done.\n\n");  
//	system("PAUSE");
  	return EXIT_SUCCESS;
}