/* wuerfel.c

gcc -g -o wuerfel wuerfel.c

./wuerfel <blau.parts >out.pov
povray +i wuerfel.pov +o blau.png -W1000 -H750 +FN16
xv blau.png

Debug:

gdb wuerfel
run <blau.parts
backtrace
quit

28 dec 2004 Koepken
*/

#include<stdio.h>
#include<math.h>

#define N1 3
#define Ntot (N1*N1*N1)
#define Nmax 100000
#define SIGN (Ntot)

#define Nsolmax 500

// im Element Ntot wird jeweils das Vorzeichen gespeichert (1 bzw. -1)
struct Spart {
    int a[Ntot+1],b[Ntot+1],c[Ntot+1];
    int *x, *y, *z;
    int n;
    int conv[Nmax];
    int rx[Nmax],ry[Nmax],rz[Nmax];
    int dx[Nmax],dy[Nmax],dz[Nmax];
    int Nc;
    int fit;
};

typedef struct Spart PART;

int readparts(PART *part) {
    int Nparts;
    int i, ip;
    int t,x,y,z;

    for(i=0;i<Ntot;i++) {
	part[i].x=part[i].a;
	part[i].y=part[i].b;
	part[i].z=part[i].c;
	part[i].n=0;
	part[i].x[SIGN]=1;
	part[i].y[SIGN]=1;
	part[i].z[SIGN]=1;
	part[i].Nc=0;
	part[i].fit=-1;
    }
    for(i=0;i<Ntot;i++) {
	scanf("%d %d %d %d",&t,&x,&y,&z);
	ip=part[t].n;
	part[t].x[ip]=x;
	part[t].y[ip]=y;
	part[t].z[ip]=z;
	part[t].n=ip+1;
	if(t+1>Nparts)
	    Nparts=t+1;
    }

    return Nparts;
}

#define swap(a,b) {int *t; t=a;a=b;b=t;}

int convertpart(PART *p) {
    int rx,ry,rz;
    int dx,dy,dz;
    int mask;
    int i, ind, j;
    int x,y,z;
    for(rx=0;rx<4;rx++) {
	swap(p->y,p->z);
	p->y[SIGN]=-p->y[SIGN];
	for(ry=0;ry<4;ry++) {
	    swap(p->x,p->z);
	    p->z[SIGN]=-p->z[SIGN];
	    for(rz=0;rz<4;rz++) {
		swap(p->x,p->y);
		p->x[SIGN]=-p->x[SIGN];
		for(dx=-2;dx<=4;dx++) {
		    for(dy=-2;dy<=4;dy++) {
			for(dz=-2;dz<=4;dz++) {
			    mask=0;
			    for(i=0;i<p->n;i++) {
				x=p->x[i]*p->x[SIGN]+dx;
				if((x<0)||(x>=N1))
				    break;
				y=p->y[i]*p->y[SIGN]+dy;
				if((y<0)||(y>=N1))
				    break;
				z=p->z[i]*p->z[SIGN]+dz;
				if((z<0)||(z>=N1))
				    break;
				ind=x+N1*(y+N1*z);
				mask|=1<<ind;
			    }
			    if(i==p->n) {
				for(j=0;j<p->Nc;j++) {
				    if(p->conv[j]==mask)
					break;
				}
				if(j==p->Nc) {
				    p->conv[p->Nc]=mask;
				    p->rx[p->Nc]=rx;
				    p->ry[p->Nc]=ry;
				    p->rz[p->Nc]=rz;
				    p->dx[p->Nc]=dx;
				    p->dy[p->Nc]=dy;
				    p->dz[p->Nc]=dz;
				    if(++p->Nc>=Nmax)
					return -1;
				}
				    
			    }
			}
		    }
		}
	    }
	}
    }
		
    return p->Nc;
}

int writeparts(int Nparts, PART *part, int prio[]) {
    int i,j;
    int bit;
    for(i=0;i<Nparts;i++) {
//	fprintf(stderr,"part[%d]: Nc=%5d ",i,part[i].Nc);
	printf("#declare ind%d= %d;\n",prio[i],i);
	printf("#declare part%d= union{\n",prio[i]);
	for(j=0;j<part[i].n;j++) {
//	    fprintf(stderr,"%d %d %d  ",part[i].x[j],part[i].y[j],part[i].z[j]);
	    printf("box {<%d,%d,%d>,<%d,%d,%d>}\n",
		   part[i].x[j],part[i].y[j],-part[i].z[j],
		   part[i].x[j]+1,part[i].y[j]+1,-(part[i].z[j]+1));
	}
	printf("}\n");
//	fprintf(stderr,"\n");
   }
    return 0;
}

int box=0;
int sol[Nsolmax][Ntot];
int solfit[Nsolmax][Ntot];
int solprio[Nsolmax][Ntot];
int Nsol=0;

int solve(int Nparts, PART *part, int i) {
    int j,k;
    int bit;
    
    for(j=0;j<part[i].Nc;j++) {
	if(box & part[i].conv[j])
	    continue;
	else {
	    box |= part[i].conv[j];
	    part[i].fit=j;
	    if(i==Nparts-1) {
//		fprintf(stderr,"solution %3d: ",Nsol);
		for(bit=0;bit<Ntot;bit++)
		    for(k=0;k<Nparts;k++)
			if(part[k].conv[part[k].fit] & (1<<bit)) {
			    sol[Nsol][bit]=k;
			    solfit[Nsol][k]=part[k].fit;
//			    fprintf(stderr,"%d ",k);
			}
		for(k=0;k<Nparts;k++)
/*		    fprintf(stderr," r%d<%d,%d,%d> d%d<%d,%d,%d>",
			    k,part[k].rx[solfit[Nsol][k]],
			      part[k].ry[solfit[Nsol][k]],
			      part[k].rz[solfit[Nsol][k]],
			    k,part[k].dx[solfit[Nsol][k]],
			      part[k].dy[solfit[Nsol][k]],
				  part[k].dz[solfit[Nsol][k]]);
			fprintf(stderr,"\n");
*/		Nsol++;
		if(Nsol==Nsolmax)
		    break;
	    }
	    else {
		solve(Nparts,part,i+1);
	    }
	    box &= ~part[i].conv[j];
	    part[i].fit=-1;
	}
    }
    return Nsol;
}

const int prios[Ntot]={2,3,4,1,2,3,0,1,2, 3,4,5,2,3,4,1,2,3, 4,5,6,3,4,5,2,3,4};

int *calcprio(int Nparts, PART *part, int i) {

    int k,bit,pr,kmin;
    float prio[Ntot], minprio;

    for(k=0;k<Nparts;k++) {
	prio[k]=0.0;
	for(bit=0;bit<Ntot;bit++)
	    if(sol[i][bit]==k)
		prio[k]+=prios[bit];
	prio[k]/=part[k].n;
//	fprintf(stderr,"prio[%d]=%3.1f\n",k,prio[k]);
    }
    for(pr=0;pr<Nparts;pr++) {
	minprio=999.0;
	for(k=0;k<Nparts;k++) {
	    if(prio[k]<minprio) {
		minprio=prio[k];
		kmin=k;
		solprio[i][k]=pr;
	    }
	}
	prio[kmin]=999.0;
    }
	
    
    return &solprio[i][0];
}

int writesol(int Nparts, PART *part, int i,int prio[]) {
    
    int k;

    for (k=0;k<Nparts;k++) {
	printf("//prio%d=%d\n",k,solprio[i][k]);
	printf("#declare rot%d = <%d,%d,%d>;\n",
	       prio[k],-90*(part[k].rx[solfit[i][k]]+1),
	       -90*(part[k].ry[solfit[i][k]]+1),
	       90*(part[k].rz[solfit[i][k]]+1));
	printf("#declare tran%d = <%d,%d,%d>;\n",
	       prio[k],part[k].dx[solfit[i][k]],
	       part[k].dy[solfit[i][k]],
	       -part[k].dz[solfit[i][k]]);
    }
    return 0;
}

int main(void) {

    PART part[Ntot];
    int Nparts;
    int i;
    int *prio;

    Nparts=readparts(part);
    for (i=0;i<Nparts;i++) {
	convertpart(&part[i]);
    }
    solve(Nparts,part,0);
    
    prio=calcprio(Nparts,part,0);
    writeparts(Nparts,part,prio);
    writesol(Nparts,part,0,prio);

    return 0;
}