/*  POTM ENTRY:  GrannysGhost                                */
/*  Your Name:   Ben Nye                                     */
/*  Your email:  angrim@montana.com                          */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <sys/times.h>

#define MAXTIME 595    /* <10 minutes worth of seconds */
#define CLK_TCK 100

#define MAX_SIDE 100
/* these 2 should probably be adjusted based on number of squares */
#define MAXTRB 500
#define MAXTRB2 10000

#define noNOISE 50
/* NORTH EAST SOUTH WEST */
/*  1
   4 2 
    3  
*/
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
struct ent{
	int used;
	int id; /* redundant really? */
	int last_id;
	int col[4];
};
struct ent patches[1001];
int patch_count;

/* freq of each letter (1)by blocks (2)by sides */
int freq1[27], freq2[27];
/* letters sorted by frequency(1) TODO */

struct rot_ent{
	int *used, *last_id;
/* tr1:used to detect bad squares, reset when sq is built over */
/* tr2:used to detect no progress in general, reset when backed out */
/* pr: the index at which this piece last got in trouble (PaRole) :P */
	int tr1,tr2, pr;
	int col[4];
	struct rot_ent *next, *next_0, *next_1;
} *rot_list[26][26], /* [top][left] */
  *rot_0[26], *rot_1[26];

/* the huge array in which to position the squares */
struct rot_ent *frame[MAX_SIDE][MAX_SIDE];
struct rot_ent *best_quilt[MAX_SIDE][MAX_SIDE];

long goal_time;
int goal_height=1, goal_edge=99;
int best_x=0, best_y=0, best_edge=99;
float best_score=0.0;

static void read_patches(char *path);
static void build_rotated(void);
static int quilt_44(int width, int height, int resume);
static void output_best(void);
static float eval_score(int x, int y){return (x*y+0.0)/(x+x+y+y+0.0);}
static long checktime(void);
static void reset_troubles(void);

void
main(int argc, char *argv[])
{
	int x, curr_width;

	if(argc!=2) exit(-11);
	read_patches(argv[1]);
	build_rotated();

#ifdef NOISE
	printf("starting stage 1. find max size square quilt\n");
#endif

	curr_width=1;
	goal_time=MAXTIME/2;
	do {
		goal_height=curr_width; /* height at which to stop increasing.. */
		if(curr_width*goal_height>patch_count) break;
		reset_troubles();
		if(!quilt_44(curr_width, goal_height, 0))break;
		curr_width++;
	} while(checktime()<goal_time);

#ifdef NOISE
	printf("starting stage 2. check for extreme rectangles\n");
#endif
	for(x=best_x;x>1 && x>(best_x-6);x--){
		goal_height=patch_count/x;
		if(eval_score(x,goal_height)<=best_score) break;
		while(eval_score(x,goal_height-1)>best_score) goal_height--;
		goal_time+=5;
		curr_width=x;
		reset_troubles();
		quilt_44(curr_width, goal_height, 0);
	}
	

#ifdef NOISE
	printf("starting stage 3. stretch rectangle\n");
#endif

	goal_time=MAXTIME*9/10;
	curr_width=best_x;
	reset_troubles();
	if(best_y<best_x)curr_width=best_y; else curr_width=best_x;
	do{
		if(best_y<best_x) goal_height=best_x+1; else goal_height=best_y+1;
		if(curr_width*goal_height>patch_count) break;
		if(!quilt_44(curr_width, goal_height, 0))break;
	} while(checktime()<goal_time);

#ifdef NOISE
	printf("starting stage 4, improve edge colors\n");
#endif
/* only 50 seconds for this stage, don't expect it to help much */
	goal_time=MAXTIME;
	if(best_y<best_x){
		curr_width=best_y;
		goal_height=best_x;
	} else {
		curr_width=best_x;
		goal_height=best_y;
	}
	do{
		goal_edge=best_edge-1;
		if(!quilt_44(curr_width, goal_height, 0))break;
	} while(checktime()<goal_time);

	output_best();
}

/* could macro this if setup time is a problem */
static int popularity(register struct rot_ent *e)
{
	if(!e) return 10000000;
	return( (freq1[e->col[RIGHT] ]<<9) + freq1[e->col[DOWN] ]);
}

static void
add_rot_patch(int id, int c1, int c2, int c3, int c4)
{
	register struct rot_ent *scan, *new;
	register int tmp_pop;

/* look for a match in the rot_list, and if its *last_id != passed in id then
   have a new match, inc used and change id2 to the current one */
	scan=rot_list[c1][c4]; /* [top][left] */
	while(scan!=NULL){
		if(scan->col[0]==c1 && scan->col[1]==c2 &&
		   scan->col[2]==c3 && scan->col[3]==c4 ) break;
		scan=scan->next;
	}
	if(!scan){
		/* add new entry */
		new=(struct rot_ent *)malloc(sizeof(struct rot_ent));
		memset(new, 0, sizeof(struct rot_ent));
		new->used= &(patches[id-1].used);
		patches[id-1].used = 1;
		new->last_id= &(patches[id-1].last_id);
		patches[id-1].last_id = id;
		new->col[0]=c1; new->col[1]=c2; new->col[2]=c3; new->col[3]=c4; 

		/* now insert in main list */
		tmp_pop = popularity(new);
		scan=rot_list[c1][c4]; /* [top][left] */
		if(tmp_pop<=popularity(scan)){ /* handles scan==NULL also */
			new->next=rot_list[c1][c4];
			rot_list[c1][c4]=new;
		} else {
			while(scan->next){
				if(tmp_pop<=popularity(scan->next)) break;
				scan=scan->next;
			}
			new->next=scan->next;
			scan->next=new;
		}

		/* now insert into next_0 list */
		scan=rot_0[c1];
		if(tmp_pop<=popularity(scan)){ /* handles scan==NULL also */
			new->next_0=rot_0[c1];
			rot_0[c1]=new;
		} else {
			while(scan->next_0){
				if(tmp_pop<=popularity(scan->next_0)) break;
				scan=scan->next_0;
			}
			new->next_0=scan->next_0;
			scan->next_0=new;
		}

		/* now insert into next_1 list */
		scan=rot_1[c4];
		if(tmp_pop<=popularity(scan)){ /* handles scan==NULL also */
			new->next_1=rot_1[c4];
			rot_1[c4]=new;
		} else {
			while(scan->next_1){
				if(tmp_pop<=popularity(scan->next_1)) break;
				scan=scan->next_1;
			}
			new->next_1=scan->next_1;
			scan->next_1=new;
		}
	} else {
		if(*(scan->last_id) == id) return; /* handle rgrg gggg etc */
		*(scan->last_id) = id;
		(*(scan->used)) ++;
	}
}

static void
build_rotated(void)
{
	int loop;

	memset(rot_list, 0, sizeof(rot_list));
	memset(rot_0, 0, sizeof(rot_0));
	memset(rot_1, 0, sizeof(rot_1));
	for(loop=0;loop< patch_count; loop++){
		add_rot_patch(loop+1,
			patches[loop].col[0], patches[loop].col[1],
			patches[loop].col[2], patches[loop].col[3]);
		add_rot_patch(loop+1,
			patches[loop].col[1], patches[loop].col[2],
			patches[loop].col[3], patches[loop].col[0]);
		add_rot_patch(loop+1,
			patches[loop].col[2], patches[loop].col[3],
			patches[loop].col[0], patches[loop].col[1]);
		add_rot_patch(loop+1,
			patches[loop].col[3], patches[loop].col[0],
			patches[loop].col[1], patches[loop].col[2]);
	}
}

static void /* updates the globals, so no output params */
read_patches(char *path)
{
	FILE *patchfile;
	char buf[1024]; /* tons to spare */
	int id; /* should just be a counter? */
	int loop;
	char c1,c2,c3,c4;

	patchfile=fopen(path, "r");
	if(!patchfile) exit(-55);

	patch_count=0;
/* freq of each letter (1)by blocks (2)by sides */
	memset(freq1, 0, sizeof(freq1));
	memset(freq2, 0, sizeof(freq2));
	memset(patches, 0, sizeof(patches));
	while(!feof(patchfile) && patch_count<1000){
		if(!fgets(buf, 512, patchfile)) break;
		if(5==sscanf(buf, "%d %c %c %c %c\n", &id, &c1, &c2, &c3, &c4)){
			c1 -= 'A'; c2 -= 'A'; c3 -= 'A'; c4 -= 'A';
			patches[patch_count].id=id;
			patches[patch_count].col[0]=c1;
			patches[patch_count].col[1]=c2;
			patches[patch_count].col[2]=c3;
			patches[patch_count].col[3]=c4;
			patch_count++;
			/* update the stats */
			freq2[(int)c1]++; freq2[(int)c2]++; freq2[(int)c3]++; freq2[(int)c4]++;
			for(loop=0;loop<26;loop++){
				if( (c1==loop)||(c2==loop)||(c3==loop)||(c4==loop) ) freq1[loop]++;
			}
		} else {
			fprintf(stderr, "bad line, '%s'\n", buf);
		}
	}
#ifdef NOISE
	/* dump some stats */
	for(id=0;id<=25;id++){
		if(freq2[id]){
			printf("letter %c occured %d times on %d blocks\n", 'A'+id,
				freq2[id], freq1[id]);
		}
	}
#endif
}
static void
output_best(void)
{
	int x,y;
	int idx;
	register struct rot_ent *scan;
	register struct ent *src;

	for(idx=0;idx<patch_count;idx++) patches[idx].used=0;

	/* for each square in the quilt, find a square in the source that matches */
	for(y=0;y<best_y;y++){
	for(x=0;x<best_x;x++)
	{
		scan=best_quilt[x][y];
		for(idx=0;idx<patch_count;idx++){
			src=&(patches[idx]);
			if(src->used) continue;
			if( (src->col[0]==scan->col[0]) && (src->col[1]==scan->col[1]) &&
				  (src->col[2]==scan->col[2]) && (src->col[3]==scan->col[3]) ){
				printf("%d,0 ", idx+1);
				src->used =1;
				break;
			}
			if( (src->col[0]==scan->col[1]) && (src->col[1]==scan->col[2]) &&
				  (src->col[2]==scan->col[3]) && (src->col[3]==scan->col[0]) ){
				printf("%d,90 ", idx+1);
				src->used =1;
				break;
			}
			if( (src->col[0]==scan->col[2]) && (src->col[1]==scan->col[3]) &&
				  (src->col[2]==scan->col[0]) && (src->col[3]==scan->col[1]) ){
				printf("%d,180 ", idx+1);
				src->used =1;
				break;
			}
			if( (src->col[0]==scan->col[3]) && (src->col[1]==scan->col[0]) &&
				  (src->col[2]==scan->col[1]) && (src->col[3]==scan->col[2]) ){
				printf("%d,270 ", idx+1);
				src->used =1;
				break;
			}
		} /* for each patch it might have been */
		if(idx == patch_count) fprintf(stderr, "ERR #1\n");
	}
		printf("\n");
	}
#ifdef NOISE
	printf("result is %d by %d score %f with %d colors\n",
		best_x, best_y, best_score, best_edge);
#endif
}

static long checktime(void)
{
	int seconds;                                                          
	static struct tms TMS;                                               

	times(&TMS);                                                          
	/* add the elapsed system and user times                        */
	/* calculation comes out to the nearest second - rounded down   */
	seconds = (TMS.tms_stime + TMS.tms_utime)/CLK_TCK ;                  
	return seconds+1;
}

static void reset_troubles(void)
{
	register int x,y;
	register struct rot_ent *sc;

	for(x=0;x<26;x++) for(y=0;y<26;y++)
		for(sc=rot_list[x][y];sc;sc=sc->next) {
		sc->tr2=0; sc->tr1=0; sc->pr= -1;
	}
}

static int count_edges(int x_edge, int y_edge)
{
	register int x,y;
	int seen[26];

	memset(seen, 0, sizeof(seen));
	for(x=0;x<x_edge;x++) {
		seen[ frame[x][0]->col[UP]           ]++;
		seen[ frame[x][y_edge-1]->col[DOWN]  ]++;
	}
	for(y=0;y<y_edge;y++) {
		seen[ frame[0][y]->col[LEFT]         ]++;
		seen[ frame[x_edge-1][y]->col[RIGHT] ]++;
	}

	x=0;
	for(y=0;y<26;y++) if(seen[y]) x++;
	return x;
}

static int
quilt_44(int width, int height, int resume)
/* if resume, then load the state from the global best_quilt */
/* useing resume seems like a neat idea, but its HARD */
{
	static int calls=0;
	int max_y=0, mmx=0;
	int col_left[MAX_SIDE][MAX_SIDE], col_up[MAX_SIDE][MAX_SIDE];
	register int cleft, cup; /* temp holders for above */
	register int cx, cy;
	register struct rot_ent *scan=NULL;

	struct rot_ent Alpha;
	int U;

	max_y=height-2;
	cx=cy=0;
	memset(frame, 0, sizeof(frame));
	memset(&Alpha, 0, sizeof(Alpha)); Alpha.used= &U; U=0;
#ifdef NOISE
printf("trying to make a %d wide by %d high with <=%d edge\n",
	width, height, goal_edge);
#endif

	do{
		/* timing and call counting */
		calls++;
		if(0==(calls&524287)){ /* 2^19=524288 every .55 seconds on my machine */
			if(checktime()>=goal_time) {
#ifdef NOISE
				printf("out of time after %d calls(loops)\n", calls);
#endif
				while(cy>=0) { /* always maintain value of *used */
					if(frame[cx][cy]) (*frame[cx][cy]->used)++;
					cx--;if(cx<0){cx=width-1;cy--;}
				}
				return 1;
			}
		}

		/* try to put a piece at cx,cy */
		scan=frame[cx][cy];
		if(!scan){ /* just entering this square */
			if(cx==0){
				cleft=0;
			} else cleft=frame[cx-1][cy]->col[RIGHT];
			if(cy==0){
				cup=0;
			} else {
				cup=frame[cx][cy-1]->col[DOWN];
				if( frame[cx][cy-1]->tr1++ >=MAXTRB ||
						frame[cx][cy-1]->tr2++ >=MAXTRB2 )
				{
					register int tmp;
					if(frame[cx][cy-1]->tr1>=MAXTRB) frame[cx][cy-1]->pr=((cy-1)<<8)+cx;
#ifdef NOISE
printf("trouble square %d at %d,%d tr1=%d tr2=%d unwinding(%d)\n",
*(frame[cx][cy-1]->last_id), cx,cy-1,
frame[cx][cy-1]->tr1, frame[cx][cy-1]->tr2, calls);
#endif
					/* unwind one row */
					for(tmp=0;tmp<cx;tmp++){
						(*frame[tmp][cy]->used)++;frame[tmp][cy]=NULL;
					}
					cy--;
					for(tmp=cx+1;tmp<width;tmp++) {
						(*frame[tmp][cy]->used)++;frame[tmp][cy]=NULL;
					}
					continue; /* to start of loop */
				}
			}
			col_left[cx][cy]=cleft;
			col_up[cx][cy]=cup;
			if(cx==0){
				Alpha.next_0=rot_0[cup];
			} else if(cy==0){
				Alpha.next_1=rot_1[cleft];
			} else {
				Alpha.next=rot_list[cup][cleft];
			}
			scan=&Alpha;
		} else {
			cleft=col_left[cx][cy];
			cup=col_up[cx][cy];
		}
		/* scan points to the square before the first square to try */
		(*scan->used)++; /* no longer using this piece */
		if(cx==0){
			if(cy==0){ /* 0,0 special case */
				while(scan){
					scan=scan->next_0; /* keys off col_up */
					if(!scan && cup<26){
						cup++; col_up[0][0]++;
						scan=rot_0[cup];
					}
					if(!scan) break;
					if(*scan->used ==0) continue;
					if(scan->pr != -1){
						if(scan->pr == (cy<<8)+cx) continue;
						scan->pr = -1;
					}
/* TODO check edge colors */
					break; /* this one should do */
				}
			} else { /* 0,y */
				while(scan){
					scan=scan->next_0;
					if(!scan) break;
					if(*scan->used ==0) continue;
					if(scan->pr != -1){
						if(scan->pr == (cy<<8)+cx) continue;
						scan->pr = -1;
					}
/* TODO check edge colors */
					break; /* this one should do */
				}
			}
		} else if(cy==0){
			while(scan){
				scan=scan->next_1;
				if(!scan) break;
				if(*scan->used ==0) continue;
				if(scan->pr != -1){
					if(scan->pr == (cy<<8)+cx) continue;
					scan->pr = -1;
				}
/* TODO check edge colors */
				break; /* this one should do */
			}
		} else { /* x,y non 0 */
			while(scan){
				scan=scan->next;
				if(!scan) break;
				if(*scan->used ==0) continue;
				if(scan->pr != -1){
					if(scan->pr == (cy<<8)+cx) continue;
					scan->pr = -1;
				}
/* TODO check edge colors */
				break; /* this one should do */
			}
		}

		/* if got here, scan should point to a new piece to try dropping */
		/* or be NULL in which case we need to back out a bit */
		if(scan){
			frame[cx][cy]=scan;
			(*scan->used)--;
			scan->tr1=0; scan->tr2=0;
			if(cy>0){
				frame[cx][cy-1]->tr1=0;
			}
			cx++;
			if(cx>=width){
				cx=0; cy++;
				frame[cx][cy]=NULL;
				/* note: had to finish a row to get here, check score */
				if(cy>=max_y){
					register float curr_score;
					max_y=cy;
					curr_score = eval_score(width,cy);
					if(curr_score>=best_score)
					{
						register int curr_edge;
						curr_edge=count_edges(width,cy);
						if(curr_score>best_score || curr_edge<best_edge)
						{
#ifdef NOISE
printf("*\n");
#endif
							memcpy(best_quilt, frame, sizeof(frame));
							best_x=width;
							best_y=cy;
							best_score=curr_score;
							best_edge = curr_edge;
							if(cy>=height && curr_edge<=goal_edge){
#ifdef NOISE
printf("goal reached, %d by %d (%d) after %d calls returning\n",
width,cy, curr_edge, calls);
sleep(1);
#endif
								while(cy>=0) { /* always maintain value of *used */
									if(frame[cx][cy]) (*frame[cx][cy]->used)++;
									cx--;if(cx<0){cx=width-1;cy--;}
								}
								return 1;
							} else if(cy>=height){ /* too many colors */
								cy--; cx=width-1;
								(*scan->used)++; /* decided not to use it after all */
							}
						}
					}
#ifdef NOISE
mmx++;
if(mmx<NOISE){
printf("%d by %d (%d) after %d calls\n",
          width,cy, count_edges(width,cy), calls);
}
#endif
				} /* end cy>=max_y */
			} else frame[cx][cy]=NULL;
		} else {
			frame[cx][cy]=NULL;
			cx--;
			if(cx<0){
				cx=width-1; cy--;
				/* enumerated all paths of this width and didn't reach the goal */
				if(cy<0) return 0;
			}
		}
	} while(1);
	return 0;
}