/*
	POTM ENTRY: stalker
	My name: Mihai Badoiu
	e-mail: mihaib@lbi.sfos.ro
	URL: http://lbi.sfos.ro/~mihaib/
	mail address: str Albotei 7 bl 8/2 ap 11,
		sector 1, Bucharest, Romania cod 71547
	source: C++
	stalker version: 3.1
*/

//extern unsigned _stklen = 655200U;
#include 
#include 
#include 
#define NEUR 113
#define MZ 12
#define MY 32
#define MX 128

//#define debug
//#define debug2
char v[MZ][MY][MX]; // the maze
short t[MZ][MY][MX]; // the path

unsigned long int st1=0,st2=0,st3=0,st4=0,st5=0;
time_t timp;
short inceput_x,inceput_y,etaje,coloane,linii;
short iz,iy,ix;
short z,y,x; // the current coordonates
short bb;
short dd;
short perm[6];
short n;
short t_izyx;
short lss2=0;
short euristica=0;
char next[MZ][MY][MX]; // number of neighbors
char next2[MZ][MY][MX]; // initial number of neighbors
char ss[16002]; // the current solution
char ss2[16002]; // the best solution

const char eur[NEUR][6]={
/*
	order of steps: 0-up 1-down 2-east 3-west 4-north 5-south
*/
{0,1,2,4,5,3},
{1,3,0,5,4,2},
{0,3,5,2,4,1},
{0,4,2,3,5,1},
{0,4,3,2,5,1},
{1,0,2,4,3,5},
{1,0,3,4,2,5},
{1,4,0,2,3,5},
{1,4,0,3,2,5},
{2,3,1,4,0,5},
{3,0,1,4,5,2},
{3,0,2,4,1,5},
{3,1,2,4,5,0},
{3,1,4,5,2,0},
{4,0,1,2,5,3},
{4,0,1,3,5,2},
{4,0,2,3,5,1},
{4,0,3,1,2,5},
{4,0,3,2,5,1},
{4,1,0,2,5,3},
{4,1,0,3,5,2},
{4,1,3,2,0,5},
{4,3,0,1,2,5},
{4,3,1,2,0,5},
{4,3,2,1,5,0},
{5,0,2,4,1,3},
{5,0,3,4,1,2},
{0,2,3,4,1,5},
{0,2,3,4,5,1},
{0,2,3,5,4,1},
{0,2,4,1,3,5},
{0,2,4,1,5,3},
{0,2,4,5,3,1},
{0,2,5,1,3,4},
{0,2,5,4,1,3},
{0,2,5,4,3,1},
{0,3,2,4,1,5},
{0,3,2,4,5,1},
{0,3,2,5,4,1},
{0,4,2,1,3,5},
{0,4,2,5,1,3},
{0,4,5,2,3,1},
{0,5,2,4,1,3},
{0,5,2,4,3,1},
{0,5,3,4,2,1},
{0,5,4,1,2,3},
{0,5,4,2,1,3},
{1,0,2,5,3,4},
{1,0,3,2,5,4},
{1,0,3,5,2,4},
{1,0,5,3,2,4},
{1,3,5,0,4,2},
{1,5,0,2,3,4},
{1,5,0,2,4,3},
{1,5,0,3,2,4},
{1,5,3,0,4,2},
{2,0,1,3,5,4},
{2,0,1,5,4,3},
{2,0,3,4,1,5},
{2,0,3,4,5,1},
{2,0,3,5,4,1},
{2,0,4,1,3,5},
{2,0,4,1,5,3},
{2,0,4,3,1,5},
{2,0,4,5,1,3},
{2,0,4,5,3,1},
{2,0,5,1,4,3},
{2,0,5,4,1,3},
{2,1,4,0,5,3},
{2,1,4,5,0,3},
{2,1,5,4,0,3},
{2,3,0,4,1,5},
{2,4,0,1,5,3},
{2,4,0,5,1,3},
{2,4,1,5,0,3},
{2,4,5,1,0,3},
{2,5,4,0,3,1},
{2,5,4,1,3,0},
{3,0,2,4,5,1},
{3,1,0,4,5,2},
{3,1,5,0,4,2},
{3,5,1,0,4,2},
{3,5,1,4,2,0},
{4,0,2,5,1,3},
{4,0,5,1,2,3},
{4,0,5,2,1,3},
{4,0,5,3,2,1},
{4,1,2,5,3,0},
{4,2,0,1,5,3},
{4,2,0,5,1,3},
{4,2,0,5,3,1},
{4,2,1,0,3,5},
{4,2,1,5,0,3},
{4,2,1,5,3,0},
{4,2,5,0,3,1},
{4,2,5,1,0,3},
{4,2,5,3,0,1},
{4,5,1,2,0,3},
{4,5,2,1,0,3},
{5,0,1,2,3,4},
{5,0,3,4,2,1},
{5,0,4,3,2,1},
{5,1,2,4,3,0},
{5,1,4,2,3,0},
{5,2,0,1,3,4},
{5,2,0,4,1,3},
{5,2,3,0,4,1},
{5,2,4,0,3,1},
{5,3,0,4,2,1},
{5,3,2,0,4,1},
{5,4,0,2,1,3},
{5,4,2,0,3,1},
{5,4,2,1,3,0}

};

void adauga(short z,short y,short x){  // inc the number of neighbors
	next[z+1][y][x]++;
	next[z-1][y][x]++;
	next[z][y+1][x]++;
	next[z][y-1][x]++;
	next[z][y][x+1]++;
	next[z][y][x-1]++;
}

void scade(short zz,short yy,short xx){  // dec the number of neighbors
/*
	if (next[zz][yy][xx]<0) // this should never happend
		puts("Oppsss......");
*/
	next[zz+1][yy][xx]--;
	next[zz-1][yy][xx]--;
	next[zz][yy+1][xx]--;
	next[zz][yy-1][xx]--;
	next[zz][yy][xx+1]--;
	next[zz][yy][xx-1]--;
}

void adaugazyx(void){  // inc the number of neighbors
	next[z+1][y][x]++;
	next[z-1][y][x]++;
	next[z][y+1][x]++;
	next[z][y-1][x]++;
	next[z][y][x+1]++;
	next[z][y][x-1]++;
}

void scadezyx(void){   // dec the number of neighbors
	next[z+1][y][x]--;
	next[z-1][y][x]--;
	next[z][y+1][x]--;
	next[z][y-1][x]--;
	next[z][y][x+1]--;
	next[z][y][x-1]--;
}

void elimina(void){
/*
	This function erases the squares with 1 neighbor!!!
*/
	short b;
	do{
		b=1;
		for (z=1;z<=etaje;z++)
			for (y=1;y<=linii;y++)
				for (x=1;x<=coloane;x++)
				if ((next[z][y][x]==1)&&(v[z][y][x]==' ')){
					v[z][y][x]='#';
					scadezyx();
					b=0;
					}
		}while (b!=1);
}

void init3(void){ // init function
	short i,j,k;
	for (k=1;k<=etaje;k++)
		for (j=1;j<=linii;j++)
			for (i=1;i<=coloane;i++){
				t[k][j][i]=0;
				}
}

void init_n2(void){ // init function
	short i,j,k;
	for (k=1;k<=etaje;k++)
		for (j=1;j<=linii;j++)
			for (i=1;i<=coloane;i++){
				next2[k][j][i]=next[k][j][i];
				if (v[k][j][i]=='#')
					next[k][j][i]=200;
				}
}

void init(void){ // init function
	short i,j,k;
	timp=time(NULL);
	for (k=0;k<=etaje+1;k++)
		for (j=0;j<=linii+1;j++)
			for (i=0;i<=coloane+1;i++){
				v[k][j][i]='#';
				next[k][j][i]=6;
				}
}

void init2(){ // init function
	t[z][y][x]=0;
	z++;
	if ((t[z][y][x]!=0)&&(t[z][y][x]<17000))
		init2();
	z-=2;
	if ((t[z][y][x]!=0)&&(t[z][y][x]<17000))
		init2();
	z++;
	y++;
	if ((t[z][y][x]!=0)&&(t[z][y][x]<17000))
		init2();
	y-=2;
	if ((t[z][y][x]!=0)&&(t[z][y][x]<17000))
		init2();
	y++;
	x++;
	if ((t[z][y][x]!=0)&&(t[z][y][x]<17000))
		init2();
	x-=2;
	if ((t[z][y][x]!=0)&&(t[z][y][x]<17000))
		init2();
	x++;
}

void init_sch(void){ // init function
	short i,j,k;
	for (k=etaje;k>0;k--)
		for (j=linii;j>0;j--)
			for (i=coloane;i>0;i--){
				if (t[k][j][i]<17000)
					t[k][j][i]=0;
				}
}

void load(const char * s){ // load function
	FILE * f;
	short k;
	char ch;
	int a1,a2,a3,a4;  // for portability
	f=fopen(s,"r");
	fscanf(f,"%d %d %d %d",&a1,&a2,&a3,&a4);
	z=a1;
	linii=a2;
	coloane=a3;
	etaje=a4;
	init();
	for (k=0;kB path is found.
*/
	short i,j,k,r,nn;
	short t_izyx2;
	if (t[z2][y2][x2]<=(t_izyx2=t_izyx))
		return;
	nn=n+t_izyx2-(r=t[z2][y2][x2]);
	bb=0;
	for (k=etaje;k>0;k--)
		for (j=linii;j>0;j--)
			for (i=coloane;i>0;i--)
				if (t[k][j][i]>t_izyx2)
					if (t[k][j][i]>r){
						t[k][j][i]+=nn;
						}
					else{
						t[k][j][i]=0;
						adauga(k,j,i);
						}
	t_izyx2++;
	for (n--;n>0;n--){
		t[z2][y2][x2]=t_izyx2+n;
		scade(z2,y2,x2);
		if (t[z2][y2][x2+1]==n){
			x2++;
			}
		else
		if (t[z2][y2][x2-1]==n){
			x2--;
			}
		else
		if (t[z2][y2+1][x2]==n){
			y2++;
			}
		else
		if (t[z2][y2-1][x2]==n){
			y2--;
			}
		else
		if (t[z2+1][y2][x2]==n){
			z2++;
			}
		else
		if (t[z2-1][y2][x2]==n){
			z2--;
			}
		else{
//			printf("Error 2!! (take a break!!)\n");  // this should never happend
			}
		}
	t[z2][y2][x2]=t_izyx2+n;
	scade(z2,y2,x2);
	init_sch();
}

void bk(void){
/*
	Backtracking function (heuristics 2)
*/
	static short tzyx;
	if ((tzyx=t[z][y][x])!=0){
		if ((tzyx>17000)&&(n>tzyx-t_izyx)&&(n>2)){
			schimba_dr(n,z,y,x);
			}
		return;
		}
	if ((bb==0)/*||(tzyx>n)*/)
		return;
	t[z][y][x]=n++;
	v[z][y][x]='#';
	scadezyx();
	for (char j=0;j<6;j++){
		switch (perm[j]){
			case 0:
				z++;
				if (v[z][y][x]!='#')
					bk();
				z--;
				break;
			case 1:
				z--;
				if (v[z][y][x]!='#')
					bk();
				z++;
				break;
			case 2:
				y++;
				if (v[z][y][x]!='#')
					bk();
				y--;
				break;
			case 3:
				y--;
				if (v[z][y][x]!='#')
					bk();
				y++;
				break;
			case 4:
				x++;
				if (v[z][y][x]!='#')
					bk();
				x--;
				break;
			case 5:
				x--;
				if (v[z][y][x]!='#')
					bk();
				x++;
			}
		}
	adaugazyx();
	v[z][y][x]=' ';
	n--;
}

void back(void){
/*
	Backtracking function (heuristics 1)
*/
	static short tzyx;
	if ((tzyx=t[z][y][x])!=0){
		if ((tzyx>17000)&&(n>tzyx-t_izyx)&&(n>2)){
			schimba_dr(n,z,y,x);
			}
		return;
		}
	if ((bb==0)/*||(tzyx>n)*/)
		return;
	t[z][y][x]=n++;
	v[z][y][x]='#';
	scadezyx();
	short k=next2[z][y][x];
	for (char i=0;i<6;i++){
		for (char j=0;j<6;j++){
		switch (perm[j]){
			case 0:
				z++;
				if ((next[z][y][x]==i)){
					if (v[z][y][x]!='#')
						back();
					if (--k<=0){
						z--;
						goto exit_for;
						}
					}
				z--;
				break;
			case 1:
				z--;
				if ((next[z][y][x]==i)){
					if (v[z][y][x]!='#')
						back();
					if (--k<=0){
						z++;
						goto exit_for;
						}
					}
				z++;
				break;
			case 2:
				y++;
				if ((next[z][y][x]==i)){
					if (v[z][y][x]!='#')
						back();
					if (--k<=0){
						y--;
						goto exit_for;
						}
					}
				y--;
				break;
			case 3:
				y--;
				if ((next[z][y][x]==i)){
					if (v[z][y][x]!='#')
						back();
					if (--k<=0){
						y++;
						goto exit_for;
						}
					}
				y++;
				break;
			case 4:
				x++;
				if ((next[z][y][x]==i)){
					if (v[z][y][x]!='#')
						back();
					if (--k<=0){
						x--;
						goto exit_for;
						}
					}
				x--;
				break;
			case 5:
				x--;
				if ((next[z][y][x]==i)){
					if (v[z][y][x]!='#')
						back();
					if (--k<=0){
						x++;
						goto exit_for;
						}
					}
				x++;
			}
			}
		}
exit_for:;
	adaugazyx();
	v[z][y][x]=' ';
	n--;
}

void pleaca(short z2,short y2,short x2){
/*
	Preparing function before calling the function back(or bk)
*/
	for (;;){
		n=1;
		bb=1;
		z=z2;
		y=y2;
		x=x2;
		if (euristica)
			back();
		else
			bk();
		if (bb!=0){
			if ((t[z][y][x]<17000)&&(t[z][y][x]!=0))
				init2();
			return;
			}
		};
}

void stalk(void){
	for (short k=0;k<=1;k++)
	{
	iz=1;
	iy=inceput_y;
	ix=inceput_x; //iz iy ix are the coordonates for the square A
	t_izyx=t[iz][iy][ix];
	for(;;){
		if (v[iz+1][iy][ix]!='#')
			pleaca(iz+1,iy,ix);
		if (v[iz-1][iy][ix]!='#')
			pleaca(iz-1,iy,ix);
		if (v[iz][iy+1][ix]!='#')
			pleaca(iz,iy+1,ix);
		if (v[iz][iy-1][ix]!='#')
			pleaca(iz,iy-1,ix);
		if (v[iz][iy][ix+1]!='#')
			pleaca(iz,iy,ix+1);
		if (v[iz][iy][ix-1]!='#')
			pleaca(iz,iy,ix-1);
		t_izyx++;  // select the next square of the cycle
		if (t[iz][iy][ix+1]==t_izyx)
			ix++;
		else
		if (t[iz][iy][ix-1]==t_izyx)
			ix--;
		else
		if (t[iz][iy+1][ix]==t_izyx)
			iy++;
		else
		if (t[iz][iy-1][ix]==t_izyx)
			iy--;
		else
		if (t[iz+1][iy][ix]==t_izyx)
			iz++;
		else
		if (t[iz-1][iy][ix]==t_izyx)
			iz--;
		else
			break;  // END of path
		};
	}
}

void scrie(void){
/*
	This function determines the length of the cycle and UPS.
*/
	short i=0,count=0;
	short r;
	iy=inceput_y;
	ix=inceput_x;
	iz=1;
	r=t[iz][iy][ix];
	for(;;){
		r++;
		adauga(iz,iy,ix);
		if (t[iz][iy+1][ix]==r){
			ss[i++]='s';
			iy++;
			}
		else
		if (t[iz][iy-1][ix]==r){
			ss[i++]='n';
			iy--;
			}
		else
		if (t[iz][iy][ix+1]==r){
			ss[i++]='e';
			ix++;
			}
		else
		if (t[iz][iy][ix-1]==r){
			ss[i++]='w';
			ix--;
			}
		else
		if (t[iz+1][iy][ix]==r){
			ss[i++]='u';
			iz++;
			}
		else
		if (t[iz-1][iy][ix]==r){
			ss[i++]='d';
			iz--;
			}
		else
			break;
		count++;
		};
	if (t[iz][iy+1][ix]==17000){
		ss[i++]='s';
		iy++;
		}
	else
	if (t[iz][iy-1][ix]==17000){
		ss[i++]='n';
		iy--;
		}
	else
	if (t[iz][iy][ix+1]==17000){
		ss[i++]='e';
		ix++;
		}
	else
	if (t[iz][iy][ix-1]==17000){
		ss[i++]='w';
		ix--;
		}
	else
	if (t[iz+1][iy][ix]==17000){
		ss[i++]='u';
		iz++;
		}
	else
	if (t[iz-1][iy][ix]==17000){
		ss[i++]='d';
		iz--;
		}
	ss[i]=0;
}

void scrie2(void){ // used for debug
	short i,j,k;
	for (k=1;k<=etaje;k++){
		for (j=1;j<=linii;j++){
			for (i=1;i<=coloane;i++){
				if (v[k][j][i]=='#')
					printf("####");
				else
				if (t[k][j][i]==0)
					printf("    ");
				else
					printf("%4d",t[k][j][i]-17000);
				}
			printf("\n");
			}
		printf("\n");
		}
}

void sol(void){
// Determine which is the best solution.
	short l=strlen(ss);
#ifndef debug
	if (llss2){
		strcpy(ss2,ss);
		dd=d;
		lss2=l;
/*		if ((lss2==86)&&(dd==1))  // for debug
			scrie2();*/
		}
	else
	if ((l==lss2)&&(dd570)  // 'itme' or 'time'?
			break;
#ifdef debug
		printf("\n");
#endif
		euristica=1;
		init3();
		t[1][inceput_y-1][inceput_x]=17001;   // NS
		t[1][inceput_y][inceput_x]=17000;
		scade(1,inceput_y-1,inceput_x);
		scade(1,inceput_y,inceput_x);
		stalk();
		scrie();
		sol();

		if (time(NULL)-timp>570)
			break;
		init3();
		t[1][inceput_y+1][inceput_x]=17001;   // SN
		t[1][inceput_y][inceput_x]=17000;
		scade(1,inceput_y+1,inceput_x);
		scade(1,inceput_y,inceput_x);
		stalk();
		scrie();
		sol();

		if (time(NULL)-timp>570)
			break;
		init3();
		t[1][inceput_y][inceput_x+1]=17001;    // EW
		t[1][inceput_y][inceput_x]=17000;
		scade(1,inceput_y,inceput_x+1);
		scade(1,inceput_y,inceput_x);
		stalk();
		scrie();
		sol();

		if (i<30){
			if (time(NULL)-timp>570)
				break;
			euristica=0;
			init3();
			t[1][inceput_y-1][inceput_x]=17001;     // NS
			t[1][inceput_y][inceput_x]=17000;
			scade(1,inceput_y-1,inceput_x);
			scade(1,inceput_y,inceput_x);
			stalk();
			scrie();
			sol();

			if (time(NULL)-timp>570)
				break;
			init3();
			t[1][inceput_y+1][inceput_x]=17001;     // SN
			t[1][inceput_y][inceput_x]=17000;
			scade(1,inceput_y+1,inceput_x);
			scade(1,inceput_y,inceput_x);
			stalk();
			scrie();
			sol();

			if (time(NULL)-timp>570)
				break;
			init3();
			t[1][inceput_y][inceput_x+1]=17001;       // EW
			t[1][inceput_y][inceput_x]=17000;
			scade(1,inceput_y,inceput_x+1);
			scade(1,inceput_y,inceput_x);
			stalk();
			scrie();
			sol();
			}
		}
	printf("%s\n",ss2);
#ifdef debug2
	printf("%d    %d\n",strlen(ss2),dd);
#endif
}

int main(int argc,char * argv[]){
	if (argc==1){
		printf("NO INPUT FILE!!!\n");
		return 0;
		}
	load(argv[1]);
	calcul();
/*	printf("Stat 1=%ld\n",st1);
	printf("Stat 2=%ld\n",st2);
	printf("Stat 3=%ld\n",st3);
	printf("Stat 4=%ld\n",st4);
	printf("Stat 5=%ld\n",st5);*/
	return 0;
}












Make your own free website on Tripod.com