/*

    This program finds all possible puzzles, constructed with n parts

    updated: 2017-05-14
            Syntax fixes for gcc

    Src:
    C:\MinGW\src\c\puzzle3
	
	compile:
	g++  -O1 -o puzzle puzzle.cpp
	g++  -O1 -o puzzle  -mcmodel=medium puzzle.cpp		// >2GByte

 
-----------------------------------------------------------------
        program:          ./puzzle version 2019-12-31
        start:            2019-12-31 15:29:20
        finish:           2019-12-31 15:52:47
        cpu-time:         23:25.34
        # parts:          12
        option:           3D world
        # unique puzzles: 18 598 427
-----------------------------------------------------------------

-----------------------------------------------------------------
        program:          ./puzzle version 2019-12-31
        start:            2019-12-31 15:22:34
        finish:           2019-12-31 15:22:37
        cpu-time:         2.79 sec
        # parts:          12
        option:           2D world
        # unique puzzles: 63 600
-----------------------------------------------------------------
 
*/


// ---- windows specific ---
// #include "stdafx.h"
// #include "string.h"

#include <stdbool.h>
#include <iostream>

#include "stdlib.h"
#include "string.h"
#include "time.h"

#define MAX         16   			// max Puzzle elements  <16
#define MAXMAX      MAX*MAX
#define MAX3        MAX*MAX*MAX
#define DMAX        MAX+MAX
#define MAXELE      126523979        // 24 (rot) + Sum(3D possibles)
									// 2d:16	 26152418
									// 2D:16     13079255
									// 3D:13	 18598427
int rotMAX =      	24; 
#define HASHMAX     MAXELE      	// HashArray can hold more than MAXELE

bool opt2D=			false;
bool opt2d=			false;
bool opt3D=			false;

int max=			8;          	// default size

int a[DMAX][DMAX][DMAX];            // test bed for creating a new puzzle

struct Astruct {                    
    bool Is2D;                       // indication for 2 D Puzzle
    int ele[MAX+1];                 // partnumber
                                    // [0] contains number of elements used
};

Astruct A[MAXELE];                  // save the good unique parts of a puzzle (no rotation products)

struct HASH {
    Astruct *p;
} hash[HASHMAX];


int aidx=0;							// index int A array


#define R(x,y,z) return (x+ MAX*y + MAXMAX*z)
 
static clock_t startClock;

//  -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -
void resetelapsedtime()
{
    startClock = clock();
}

//  -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -
char *getelapsedtimestr()
{
static  char    etime[12];
int     h=0,m=0,s=0,t;
long    etl;
double  etd;
    etd=((double)(clock() - startClock) / CLOCKS_PER_SEC);

    etl=(long)etd;
    t=int((etd-(double)etl)*100); 
    //t=(etd-etl)*10;               /* for MSDOS BORLAND */
    s = etl % 60;
    m = (etl/60) % 60;
    h = (etl/3600 );
    if (h>0)
        sprintf(etime,"%2d:%02d:%02d.%02d",h,m,s,t);
    else
        if (m>0)
            sprintf(etime,"%d:%02d.%02d",m,s,t);
        else
            sprintf(etime,"%d.%02d sec",s,t);

    return etime;
}

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

char *getNbr(int i) {
	// use BLANK for 1000 number segmentation
	// e.g.: 1 234 567
	static char str[80];
	int a=i % 1000;			// last 3 digits
	int b=(i/1000)%1000;	// next 3 digits
	int c= (i/1000000);		// next 3 digits
	if (c>0)
		sprintf (str,"%d %03d %03d",c,b,a);
	else if (b>0)
		sprintf (str,"%d %03d",b,a);
	else  
		sprintf (str,"%d",a);

	return str;
}

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

void getNow() {
	time_t now;
	time(&now);
	tm* t = localtime(&now);
	char buffer[80];
 	
	strftime(buffer, sizeof(buffer), "%Y-%m-%d %H:%M:%S", t);
	printf(buffer);
}

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

void init()
{
    int x,y,z;
    for (x=0;x<DMAX;x++)
        for (y=0;y<DMAX;y++)
            for (z=0;z<DMAX;z++)
                a[x][y][z]=false;               // Test bed is free


    for (int i =0;i<MAXELE;i++) {
        for (x=0;x<=MAX;x++) {
            A[i].Is2D = true;                   // assume its 2D
            A[i].ele[x]=88;
        }
    }
    for (int i =0;i<HASHMAX;i++) hash[i].p=NULL;
}

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

void niceDisp(int idx) {
int x,y,z,n;
int max=A[idx].ele[0];
int maxX=0,maxY=0,maxZ=0;
int box[MAX][MAX][MAX];

    // init box
    for (int z=0;z<max;z++) 
        for (int y=0;y<max;y++) 
            for (int x=0;x<max;x++) 
                box[x][y][z]=false;

    // Set parts in Test bed
    for (n=1;n<=max;n++) {
        x=A[idx].ele[n] % MAX;
        y=(A[idx].ele[n] / MAX )% MAX;
        z=A[idx].ele[n] / (MAXMAX);
        if (x>maxX) maxX=x;
        if (y>maxY) maxY=y;
        if (z>maxZ) maxZ=z;
        box[x][y][z]=true;
    }
 
    for (int y=maxY;y>=0;y--) {
		for (int z=0;z<=maxZ;z++) { 
            for (int x=0;x<=maxX;x++) {
                if (box[x][y][z]) printf("X"); else printf(".");
            }
            printf("\t");
        }
        printf("\n");
    }
	printf("\n");
}

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

void display(int pNbr, int idx)
{
int x,y,z,n;
int max=A[idx].ele[0];
int maxX=0,maxY=0,maxZ=0;
int dim=3;

    // Set parts in Test bed
    for (n=1;n<=max;n++) {
        x=A[idx].ele[n] % MAX;
        y=(A[idx].ele[n] / MAX )% MAX;
        z=A[idx].ele[n] / (MAXMAX);

        // Security check
        if (x<0 || x>=max || y<0 || y>=max || z<0 || z>=max) {
            printf("too large positions found for idx=%d: X=%d Y=%d Z=%d\n",idx,x,y,z);
            exit(1);
        }
        if (x>maxX) maxX=x;
        if (y>maxY) maxY=y;
        if (z>maxZ) maxZ=z;
    }
    
    // calc dim
    if (maxZ==0) dim--; 
    if (maxY==0) dim--;
    if (maxX==0) dim--;
    printf("%d\t%3d\t",dim,pNbr);

    printf("%2d\t%2d\t%2d\t",maxX+1,maxY+1,maxZ+1);
    for (n=1;n<=max;n++) {
        x=A[idx].ele[n] % MAX;
        y=(A[idx].ele[n] / MAX )% MAX;
        z=A[idx].ele[n] / (MAXMAX);
        if (dim==1)
            printf("[%d]",x);
        else if (dim==2)
            printf("[%d,%d]",x,y);
        else
            printf("[%d,%d,%d]",x,y,z);
    }
    printf("\n");
    if (dim==1) printf("\n");
}
 
//  -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -

int findFreeAtStone(int lvl, int & curX,int & curY,int & curZ) {
int x,y,z;
int scan=false;
/*  algoryhtmn:
    Inc curX,curY,curZ
    until FreePosition isfound and neighbour is set
 
*/
    
	if (opt3D) {
		for (x=MAX-lvl;x<MAX+lvl;x++) {       
			for (y=MAX-lvl;y<MAX+lvl;y++) {
				for (z=MAX-lvl;z<MAX+lvl;z++) {
					if (x>=curX && y>=curY && z>curZ) scan = true;	// enabled
					if (scan && a[x][y][z]==false) {
						// look left+right up+down before+after						 
						if ( a[x-1][y]  [z]   || a[x+1][y]  [z]  ||
							 a[x]  [y-1][z]   || a[x]  [y+1][z]  ||
							 a[x]  [y]  [z-1] || a[x]  [y]  [z+1] ) {
							curX=x;
							curY=y;
							curZ=z;								
							// printf("chk %2d %2d %2d\n",x-MAX,y-MAX,z-MAX); 
							return true;
                        }
                    }
                }
            }
        }
	} else {
		for (x=MAX-lvl;x<MAX+lvl;x++) {
			for (y=MAX-lvl;y<MAX+lvl;y++) {
			    if (x>=curX && y>curY ) scan = true;	// enabled
                if (scan && a[x][y][MAX]==false) {
                    // look left+right up+down before+after 
					if (a[x-1][y]  [MAX] || a[x+1][y]  [MAX]  ||
                        a[x]  [y-1][MAX] || a[x]  [y+1][MAX] ){
                        curX=x;
                        curY=y;
						curZ=MAX;	
						return true;
					}
				}
            }
        }
    }
    return false;
}

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

int isEqual(int aidx,int i) {
  
    for (int j=0;j<=A[aidx].ele[0];j++) 
        if (A[i].ele[j]!=A[aidx].ele[j]) return false;
	
    // seems to be equal  
    return true; 
}

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

long getHashIndx1(int aidx) {
	long hi=0;			// hashIndex init
	for (int j=0;j<=A[aidx].ele[0];j++) 
        hi = abs(A[aidx].ele[j]+(hi*max)) % HASHMAX;
	
	return hi;
}

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

long getHashIndx2(int aidx) {
	long hi=0;			// hashIndex init
	for (int j=A[aidx].ele[0];j>0;j--) 
        hi = abs(A[aidx].ele[j]+(hi*max)) % HASHMAX;
	
	return hi;
}

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

int doesExist(int aidx) {
bool found;
    if (aidx==0) return false;          // first one is accepted

	long hi=getHashIndx1(aidx);
		
    // loop in list
    do {
        if (hash[hi].p==NULL) {
			return false;             	// not found at expected position! 
										// So it does not exist
		}
		
		found=true;						// init
		for (int j=0;j<=A[aidx].ele[0];j++) 
			if (hash[hi].p->ele[j]!=A[aidx].ele[j]) {
				found=false;
				break;
			}
	
		if (found) {
			return true;    			// something found and 
										// it seems to be the real one
		}
										// continue to search   
		hi=(hi+getHashIndx2(aidx))%HASHMAX; 
    }  while (hash[hi].p!=NULL);
    return false;                       // reaching end of list
}


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

int compare( const void *arg1, const void *arg2 ){
   /* Compare all of both strings: */
   
    int a=*(int *)arg1;
    int b=*(int *)arg2;

    if (a<b) return -1;
    if (a>b) return 1;
    return 0;
}

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

void Qsort(int aidx) {
    qsort( (void *) &A[aidx].ele[1],                // Start of target array
            (size_t) A[aidx].ele[0],                // Array size in elements
            sizeof(  A[aidx].ele[0]),               // Element size in bytes
            compare );                              // Comparison function
}

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

int rot(int r,                                              // rotation Nbr 0..23
        int x,      int y,      int z,                      // current x,y,z
        int xmin,   int ymin,   int zmin,                   // min value of cube
        int xmax,   int ymax,   int zmax) {                 // max value of cube
#define X_positiv (x-xmin)
#define X_negativ (xmax-x)
#define Y_positiv (y-ymin)
#define Y_negativ (ymax-y)
#define Z_positiv (z-zmin)
#define Z_negativ (zmax-z)


/*

  Idea: define 6 Start Positions, and then keep z constant and rotate x,y



  Start Postions:

  0     x,y,z as defined                r=0
  1     z-> y;  x-> x;  y->-z;          r=4
  2     z->-z;  x-> x;  y->-y;          r=8
  3     z->-y;  x-> x;  y-> z;          r=12
  4     z-> x;  x->-z;  y->y;           r=16
  5     z->-x;  x-> z;  y->y;           r=20


  Rotate:

  y             
                z constant, rotate means:
  ^   z     
  | /           x ->  y  or Y' = x
  +--> x        y -> -x     X' = y


*/
    switch (r) {
    case 0:  R( X_positiv, Y_positiv, Z_positiv);           // normal position
    case 1:  R( Y_negativ, X_positiv, Z_positiv);
    case 2:  R( X_negativ, Y_negativ, Z_positiv);
    case 3:  R( Y_positiv, X_negativ, Z_positiv);

    case 4:  R( X_positiv, Z_positiv, Y_negativ);           // 1. Start Postion
    case 5:  R( Z_negativ, X_positiv, Y_negativ);
    case 6:  R( X_negativ, Z_negativ, Y_negativ);
    case 7:  R( Z_positiv, X_negativ, Y_negativ);

    case 8:  R( X_positiv, Y_negativ, Z_negativ);           // 2. Start Postion
    case 9:  R( Y_positiv, X_positiv, Z_negativ);
    case 10: R( X_negativ, Y_positiv, Z_negativ);
    case 11: R( Y_negativ, X_negativ, Z_negativ);

    case 12: R( X_positiv, Z_negativ, Y_positiv);           // 3. Start Postion
    case 13: R( Z_positiv, X_positiv, Y_positiv);
    case 14: R( X_negativ, Z_positiv, Y_positiv);
    case 15: R( Z_negativ, X_negativ, Y_positiv);

    case 16: R( Z_positiv, Y_positiv, X_negativ);           // 4. Start Postion
    case 17: R( Y_negativ, Z_positiv, X_negativ);
    case 18: R( Z_negativ, Y_negativ, X_negativ);
    case 19: R( Y_positiv, Z_negativ, X_negativ);

    case 20: R( Z_negativ, Y_positiv, X_positiv);           // 5. Start Postion
    case 21: R( Y_negativ, Z_negativ, X_positiv);
    case 22: R( Z_positiv, Y_negativ, X_positiv);
    case 23: R( Y_positiv, Z_positiv, X_positiv);
    }
    printf("Wrong Rotation\n\n");
    exit(1);
    return 1;
}

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

int addThis(int lvl){
    // first move parts to left lower edge
    // then build all 24 rotations and look if it exists in the list.
    // If not found, append this part into the list
    

int x,y,z,r,n;
int X[DMAX];
int Y[DMAX];
int Z[DMAX];

    
    for (x=0;x<DMAX;x++) {
		X[x]=false;
        Y[x]=false;
		Z[x]=false;
	}
    
    // try to define X and Y boundaries

    for (x=MAX-lvl;x<MAX+lvl;x++) {
        for (y=MAX-lvl;y<MAX+lvl;y++) {
            for (z=MAX-lvl;z<MAX+lvl;z++) {
                if (a[x][y][z]) {
                    X[x]=true;
                    Y[y]=true;
                    Z[z]=true;
                }
            }
        }
    }

    // define min and max boundaries

    int xmin=0;         while (!X[xmin]) xmin++;
    int ymin=0;         while (!Y[ymin]) ymin++;
    int zmin=0;         while (!Z[zmin]) zmin++;

    int xmax=DMAX-1;    while (!X[xmax]) xmax--;
    int ymax=DMAX-1;    while (!Y[ymax]) ymax--;
    int zmax=DMAX-1;    while (!Z[zmax]) zmax--;

    if (opt2d) rotMAX = 4;
    else if (opt2D) rotMAX = 12;

    for (r=0;r<rotMAX;r++) A[aidx+r].ele[0]=lvl+1;          // Setup how many parts are in use
    
    int i=1;
    // create New rotations
    for (y=ymin;y<=ymax;y++) {
        for (x=xmin;x<=xmax;x++) {
            for (z=zmin;z<=zmax;z++) {
                if (a[x][y][z]) {
                    for (r=0;r<rotMAX;r++) A[aidx+r ].ele[i]=rot(r,x,y,z,xmin,ymin,zmin,xmax,ymax,zmax);
                    i++;
                }
            }
        }
    }

    for (r=0;r<rotMAX;r++) {
        Qsort(aidx+r);                          // sort Rot Product r    
        if (doesExist(aidx+r))  return false;   // check if this entry already exists
    }
   
    // great, we found a new one
    // save only one solutions and not ALL rotation
 
    // setup Is2D
	A[aidx].Is2D=true;  // init
	if (opt3D) {
        for (n=1;n<=A[aidx].ele[0];n++) 
			if (A[aidx].ele[n]>=MAXMAX) {
				A[aidx].Is2D=false;
				break;
			}
		}
	
    // Setup Hash Index
	long hi=getHashIndx1(aidx);
    while (hash[hi].p!=NULL) {
		// use double hashing to avoid clustering!!
		hi=(hi+getHashIndx2(aidx))%HASHMAX; 
	}
	
    hash[hi].p = &A[aidx];
    aidx++;
 
    return true;
}

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

void create(int lvl) {
    int x,y,z;
    if (lvl>=max)   {               // reaching the deepest level, so stop recursion
        return;
    }

    // try to create the puzzle (by recursive attaching parts)

    if (lvl==0 ) {
        a[MAX][MAX][MAX]=true;      // first time use centre to set it
        addThis(0);
        create(1);
    }
    else {							// find all partners
        x=0;y=0;z=0;

        while (findFreeAtStone(lvl, x,y,z)) {			
			a[x][y][z]=true;        // set position
			if (addThis(lvl)) {
				create(lvl+1);
			}
			a[x][y][z]=false;       // rset position
        }
    }
}

//  -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -
 
void usage() {
    printf("missing arguments\n");
    printf("-size\tto define # parts\n");
    printf("-list\tto list all solutions\n");
	printf("-nice\tto list nice solutions\n");
	printf("-sum\tto display summary\n");
    printf("2D / 3D / 2d\tvarious Options\n");
    exit(1);
}
 
//  -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -   -

int main(int argc, char* argv[]){
	char version[]="version 2019-12-31";
    char dash[]= "-----------------------------------------------------------------\n";
    int n;
    bool optList=false;
	bool optNice=false;
	bool optSum=false;
    if (argc>1) {
        for (int i=1;i<argc;i++) {
            if (strcmp(argv[i],"-size") == 0)
                {max=atoi(argv[++i]);}
            else if (strcmp(argv[i],"-list") == 0) optList=true;
            else if (strcmp(argv[i],"2D") == 0) opt2D=true;
            else if (strcmp(argv[i],"2d") == 0) opt2d=true;
            else if (strcmp(argv[i],"3D") == 0) opt3D=true;
			else if (strcmp(argv[i],"-sum") == 0) optSum=true;
			else if (strcmp(argv[i],"-nice") == 0) optNice=true;
            else {
                printf("unknown >%s<\n",argv[i]);
                exit(1);
            }
        }

        if (max>MAX) {
            printf("Sorry, size is too big.");
            exit(1);
        }
        if (max<=0) max=5; 		// use default size
    } else usage();
	

	// nothing selected, use 2D as default
    if ((opt2D ||opt2d || opt3D) == false) opt2D=true;
	
	
	printf("%s",dash);
	printf("\tprogram:          %s %s\n",argv[0],version);
	printf("\tstart:            ");getNow();printf("\n");
	
    resetelapsedtime();
 
    //init();
    create(0);						// recursive building task
	

    /////////////////////  report ////////////////////////////////

    int j,i,cnt3D=0,cnt2D=0;
	
	if (optSum) {
		printf("\t\t\t  parts\t");
		if (opt3D) printf("%11s\t","3D puzzles");
		if (opt2d)
				printf("%11s","2d puzzles");
			else
				printf("%11s","2D puzzles");
		printf("\n");
	}
	for (j=1;j<=max;j++) {
		if (optSum) printf("\t\t\t%6d\t",j);
		if (opt3D) {
			cnt3D=0;
			for ( i=0;i<aidx;i++) if (A[i].ele[0]==j) cnt3D++;
			if (optSum) printf("%11s\t",getNbr(cnt3D));
		} 
		cnt2D=0;
		for ( i=0;i<aidx;i++) if (A[i].ele[0]==j && A[i].Is2D ) cnt2D++;
		if (optSum)  {
			if (opt2d)
				printf("%11s\n",getNbr(cnt2D));
			else
				printf("%11s\n",getNbr(cnt2D));
		}
	}
	

	// meta data header output 
	n=max;
	
	printf("\tfinish:           ");getNow();printf("\n");
	printf("\tcpu-time:         %s\n",getelapsedtimestr());
	printf("\t# parts:          %d\n",n);
	printf("\toption:           ");
	if (opt2D) printf("2D world\n\t# unique puzzles: %s\n",getNbr(cnt2D));
	if (opt2d) printf("2d no flip 2D solutions\n\t# unique puzzles: %s\n",getNbr(cnt2D));
	if (opt3D) printf("3D world\n\t# unique puzzles: %s\n",getNbr(cnt3D));
    printf("%s",dash);

    if (optList||optNice) {       // list option
        if (optList) {
			printf("dim\tpNbr\tmaxX\tmaxY\tmaxZ\tpuzzle definition [x,y,z]\n");
			printf("%s",dash);
		}
        int pNbr=1;
        for ( i=0;i<aidx;i++) if (A[i].ele[0]==n &&  A[i].Is2D)  
			if (optNice) niceDisp(i); else display(pNbr++,i);
        printf("\n");
        
        for ( i=0;i<aidx;i++) if (A[i].ele[0]==n &&  A[i].Is2D==false) 
			if (optNice) niceDisp(i); else display(pNbr++,i);
		printf("%s",dash);
    }
}