/* solver.c */
/* Last Change: 2019/07/29 (Mon) 09:32:40. */

#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#include<time.h>
#include"solver.h"
#include"io.h"
/* #include<string.h> */
/* #include<math.h> */
#define DEBUG 1
#define ABS(a) ((a) < 0 ? - (a) : (a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

/* short int connected[MAXLINE+1]={0}; //if line connected:2, if one end:1, otherwize:0 */
short int board_beta[MAXSIZE][MAXSIZE]; //big board data
//edge:1~MAXLINE, line:-1~-MAXLINE, none:0, wall:SHRT_MIN
short int rank[MAXBLOCK+1]; //ranking of point below, 0:unused, 1~
short int point[MAXBLOCK+1]; //XYZ
//X: search priority, Y: number of edges in board, Z: number of edges in block
short int first_block=1;
short int costrank[1+MAXBLOCK*MAXBLOCK][2]; //ranking of cost: block being in (costrank[ranking][0],costrank[ranking][0])
short int rdm[MAXBLOCK+1]; //random no
short int attempts=1;

void print_board_beta(void){
	short int i,j;
	short int minw=MAXSIZE-1,maxw=0,minh=MAXSIZE-1,maxh=0;
	for(i=0;i<MAXSIZE;i++){
		for(j=0;j<MAXSIZE;j++){
			if(board_beta[i][j]){
				if(i>maxw)
					maxw=i;
				if(i<minw)
					minw=i;
				if(j>maxh)
					maxh=j;
				if(j<minh)
					minh=j;
			}
		}
	}
	for(i=minh;i<=maxh;i++){
		for(j=minw;j<=maxw;j++){
			printf("%6d",board_beta[j][i]);
			if(j==maxw)
				printf("\n");
			else
				printf(",");
		}
	}
	return;
}

void shuffle_random(short int seed){ //edit this to randomly place blocks
	short int i,r,tmp;
	srand(seed);
	for(i=1;i<=blocks;i++)
		rdm[i]=i;
	for(i=1;i<=blocks;i++){
		r=rand()%blocks+1;
		tmp=rdm[i];
		rdm[i]=rdm[r];
		rdm[r]=tmp;
	}
	return;
}

void update_ranks(void){
	short int i,j,blocksrank[MAXBLOCK+1];
	for(i=1;i<=blocks;i++){
		blocksrank[i]=1;
	}
	for(i=1;i<=blocks;i++){
		for(j=1;j<=blocks;j++){
			if(point[rdm[i]]<point[rdm[j]])
				blocksrank[rdm[i]]++;
			else if(point[rdm[i]]==point[rdm[j]] && i>j)
				blocksrank[rdm[i]]++;
			/* else */
			/* printf("%d %d no\n",rdm[i],rdm[j]); */
		}
	}
	for(i=1;i<=blocks;i++)
		rank[blocksrank[i]]=i;
	return;
}

void reset(void){ //excluding init_points
	short int i,j;
	for(i=0;i<MAXSIZE;i++) //clear board
		for(j=0;j<MAXSIZE;j++)
			board_beta[i][j]=0;
	for(i=1;i<=blocks;i++){ //clear blocks' places
		if(point[i]<0)
			point[i]=-point[i];
		block_data[i][0][0]=-1;
		block_data[i][0][1]=-1;
		point[i]-=((point[i]/10)%10)*10; //reset Y
	}
	/* for(i=1;i<=MAXLINE;i++){ */
	/* connected[i]=0; */
	/* } */
	update_ranks();
	first_block=1;
	return;
}

void init_points(void){ //use only once
	short int i,j;
	for(i=1;i<=blocks;i++){
		point[i]=0;
		for(j=1;j<=4;j++)
			if(block_data[i][j][2]>0) //if edge exists
				point[i]+=2;
		if(point[i]==0)
			point[i]++;
	}
	update_ranks();
	return;
}

void add_point(short int blockid){
	short int i,j,k;
	for(i=1;i<=blocks;i++)
		if(i!=blockid&&point[i]>0)
			for(j=1;j<=4;j++)
				for(k=1;k<=4;k++)
					if(block_data[i][j][2]==block_data[blockid][k][2]&&block_data[blockid][k][2]>0)
						point[i]+=10;
	update_ranks();
	return;
}

void sub_point(short int blockid){
	short int i,j,k;
	for(i=1;i<=blocks;i++)
		if(i!=blockid&&point[i]>0)
			for(j=1;j<=4;j++)
				for(k=1;k<=4;k++)
					if(block_data[i][j][2]==block_data[blockid][k][2]&&block_data[blockid][k][2]>0)
						point[i]+=10;
	update_ranks();
	return;
}


short int search_placable(short int blockid){ //calc the cost (sum of Euclidean distance of lines), returns the number of places
	short int cost[MAXSIZE][MAXSIZE][2]; //cost[x][y][0]:cost, cost[x][y][1]:rank
	short int i,j,k,l,index=0;
	short int place[5][2]; //(relative) place of edge #block_data[blockid][1-4][] (x,y)
	short int blockw=0,blockh=0;
	/* calc cost */
	if(block_data[blockid][2][2]==-1){ //if monomino
		for(i=0;i<MAXSIZE;i++)
			for(j=0;j<MAXSIZE;j++){
				cost[i][j][0]=0;
				if(board_beta[i][j]==block_data[blockid][1][2]){
					if(i+1<MAXSIZE&&board_beta[i+1][j]==0)
						cost[i+1][j][0]=1;
					if(j+1<MAXSIZE&&board_beta[i][j+1]==0)
						cost[i][j+1][0]=1;
					if(i-1>=0&&board_beta[i-1][j]==0)
						cost[i-1][j][0]=1;
					if(j-1>=0&&board_beta[i][j-1]==0)
						cost[i][j-1][0]=1;
				}
			}
	}else{
		for(k=1;k<=4;k++){
			place[k][0]=SHRT_MIN;
			place[k][1]=SHRT_MIN;
			for(i=0;i<MAXSIZE;i++){
				for(j=0;j<MAXSIZE;j++)
					if(board_beta[i][j]>0 && board_beta[i][j]==block_data[blockid][k][2]){
						place[k][0]=i-block_data[blockid][k][0];
						place[k][1]=j-block_data[blockid][k][1];
					}
			}
			/* printf("%d, %d\n",place[k][0],place[k][1]); */
		}
		for(k=1;k<=4;k++){
			if(block_data[blockid][k][0]>blockw)
				blockw=block_data[blockid][k][0];
			if(block_data[blockid][k][1]>blockh)
				blockh=block_data[blockid][k][1];
		}
		/* printf("%d: %d, %d\n",blockid,blockw,blockh); */
		for(i=0;i<MAXSIZE;i++){
			for(j=0;j<MAXSIZE;j++){
				cost[i][j][1]=1;
				if(i+blockw>=MAXSIZE || j+blockh>=MAXSIZE) //out of board
					cost[i][j][0]=-1;
				else if(   0!=board_beta[i+block_data[blockid][1][0]] [j+block_data[blockid][1][1]] //alredy something
						|| 0!=board_beta[i+block_data[blockid][2][0]] [j+block_data[blockid][2][1]]
						|| 0!=board_beta[i+block_data[blockid][3][0]] [j+block_data[blockid][3][1]]
						|| 0!=board_beta[i+block_data[blockid][4][0]] [j+block_data[blockid][4][1]])
					cost[i][j][0]=-1;
				else{
					cost[i][j][0]=0;
					for(k=1;k<=4;k++){
						if(place[k][0]!=SHRT_MIN)
							cost[i][j][0]+=ABS(i-place[k][0]);
						if(place[k][1]!=SHRT_MIN)
							cost[i][j][0]+=ABS(j-place[k][1]);
					}
					if(cost[i][j][0]==0)
						cost[i][j][0]=MAX(MAX(ABS(i-MAXSIZE/2),ABS(j-MAXSIZE/2)),MAX(ABS(i+blockw-MAXSIZE/2),ABS(j+blockh-MAXSIZE/2)));//*100+ABS(i-MAXSIZE/2)+ABS(j-MAXSIZE/2)+ABS(i+blockw-MAXSIZE/2)+ABS(j+blockh-MAXSIZE/2);
					cost[i][j][0]=10000-cost[i][j][0];
					/* printf("%d\n",cost[i][j][0]); */
				}
			}
		}
	}
	/* calc costrank */
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++)
			for(k=0;k<MAXSIZE;k++)
				for(l=0;l<MAXSIZE;l++)
					if(cost[i][j][0]<cost[k][l][0])
						cost[i][j][1]++;
					else if(cost[i][j][0]==cost[k][l][0] && (i>k || (i==k&&j>l)))
						cost[i][j][1]++;
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++){
			if(!index && cost[i][j][0]<0)
				index=cost[i][j][1];
			costrank[cost[i][j][1]] [0]=i;
			costrank[cost[i][j][1]] [1]=j;
		}
	/* printf("%d\n",cost [costrank[1][0]] [costrank[1][1]] [0]); */
	return index-1;
}

void erase_line(short int lineid){
	short int i,j;
	if(lineid==0)
		return;
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++)
			if(board_beta[i][j]==-lineid)
				board_beta[i][j]=0;
	if(DEBUG)
		printf("#%d     Line %d disconnected\n",attempts,lineid);
	return;
}


short int avail[MAXSIZE][MAXSIZE]={}; //start=3,path=2,avail=1,nonavail=0,goal=-1
short int goalx,goaly,goalz;


void connect(short int lineid){ //connect line
	short int i,j;
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++)
			if(avail[i][j]==2){
				if(board_beta[i][j]==0)
					board_beta[i][j]=-lineid;
				else{
					printf("something wrong");
					return;
				}
			}
	if(DEBUG)
		printf("#%d     Line %d connected\n",attempts,lineid);
	return;
}

short int available(short int nowx,short int nowy, short int start){ //return 1 when (nowx,nowy) can be connected to goal
	if(avail[nowy][nowx]==-1) //goal
		return 1;
	if(avail[nowy][nowx]!=1&&start==0)
		return 0;
	short int isbranch=-1;
	if(nowx>0&&avail[nowy][nowx-1]>=2)
		isbranch++;
	if(nowy>0&&avail[nowy-1][nowx]>=2)
		isbranch++;
	if(nowx<MAXSIZE-1&&avail[nowy][nowx+1]>=2)
		isbranch++;
	if(nowy<MAXSIZE-1&&avail[nowy+1][nowx]>=2)
		isbranch++;
	if(isbranch>0){
		avail[nowy][nowx]=1;
		return 0;
	}
	if(avail[nowy][nowx]==1)
		avail[nowy][nowx]=2;
	short int i,src=0;
	short int searchorder[4]; //x+-,y+-
	/* for(i=0;i<4;i++) */
	/* searchorder[i]=-1; */
	if(nowx>goalx){
		searchorder[src]=0;
		src++;
	}else
		searchorder[3+src]=0;
	if(nowy>goaly){
		searchorder[src]=1;
		src++;
	}else
		searchorder[2+src]=1;
	if(nowx<goalx){
		searchorder[src]=2;
		src++;
	}else
		searchorder[1+src]=2;
	searchorder[src]=3;
	if(nowy<goaly)
		src++;
	/* shuffle(searchorder,0,src); */
	/* shuffle(searchorder,src,4); */
	/* printf("1: "); */
	/* for(i=0;i<4;i++) */
	/* 	printf("%d ",searchorder[i]); */
	/* printf("\n"); */
	short int j,t;
	for(i=0;i<src;i++){
		j=rand()%(src);
		t=searchorder[i];
		searchorder[i]=searchorder[j];
		searchorder[j]=t;
	}
	for(i=src;i<4;i++){
		j=src+rand()%(4-src);
		t=searchorder[i];
		searchorder[i]=searchorder[j];
		searchorder[j]=t;
	}
	/* printf("2: "); */
	/* for(i=0;i<4;i++) */
	/* 	printf("%d ",searchorder[i]); */
	/* printf("\n"); */
	for(i=0;i<4;i++)
		switch(searchorder[i]){
			case 0:
				if(nowx>0&&available(nowx-1,nowy,0))
					return 1;
				break;
			case 1:
				if(nowy>0&&available(nowx,nowy-1,0))
					return 1;
				break;
			case 2:
				if(nowx<MAXSIZE-1&&available(nowx+1,nowy,0))
					return 1;
				break;
			case 3:
				if(nowy<MAXSIZE-1&&available(nowx,nowy+1,0))
					return 1;
				break;
			default:
				break;
		}
	if(avail[nowy][nowx]==2)
		avail[nowy][nowx]=0;
	return 0;
}

short int connectable(short int linea,short int lineb){ //return 1 if linea can be connected when lineb is deleted
	short int startx=-1,starty=-1,notfound=1;
	short int i,j;
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++)
			if(board_beta[i][j]==linea){
				if(notfound){ //start
					starty=i;
					startx=j;
					avail[i][j]=3;
					notfound=0;
					/* printf("1\n"); */
				}else{ //goal
					goaly=i;
					goalx=j;
					avail[i][j]=-1;
					notfound=2;
					/* printf("2\n"); */
				}
			}else if(board_beta[i][j]==0||board_beta[i][j]==-lineb||board_beta[i][j]==-linea){
				avail[i][j]=1;
			}else{
				avail[i][j]=0;
			}
	if(startx==-1||starty==-1||notfound!=2){
		printf("Error: Line %d\n",linea);
		return 0;
	}
	return available(startx,starty,1);
}

short int try_wires(short int blockid){
	if(block_data[blockid][2][2]==-1){ //if monomino
		return 1;
	}
	if(DEBUG)
		printf("#%d   try wire: block %d\n",attempts,blockid);
	short int line[4],lines=0,i,j,k,found;
	for(i=1;i<=4;i++)
		if(block_data[blockid][i][2]>0){
			found=0;
			for(j=0;j<MAXSIZE&&found<=1;j++)
				for(k=0;k<MAXSIZE&&found<=1;k++)
					if(board_beta[j][k]==block_data[blockid][i][2])
						found++;
			if(found==2){
				line[lines]=block_data[blockid][i][2];
				if(DEBUG)
					printf("#%d   Block %d requires line %d\n",attempts,blockid,block_data[blockid][i][2]);
				lines++;
			}
		}
	for(i=0;i<lines;i++){
		if(connectable(line[i],0))
			connect(line[i]);
		else if(i==0)
			return 0;
		else
			for(j=0;j<i;j++){
				if(connectable(line[i],line[j])){
					erase_line(line[j]);
					connect(line[i]);
					if(connectable(line[j],0)){
						connect(line[j]);
						break;
					}else{
						erase_line(line[i]);
						connect(line[j]);
					}
				}
				if(j==i-1){
					for(j=0;j<i;j++)
						erase_line(line[j]);
					return 0;
				}
			}
	}
	if(DEBUG){
		printf("#%d   Block %d placed @(%d,%d)\n",attempts,blockid,block_data[blockid][0][0],block_data[blockid][0][1]);
		print_board_beta();
	}
	return 1;
}

void place_block(short int blockid,short int x,short int y){
	short int i;
	/* printf("%d: %d %d\n",blockid,x,y); */
	block_data[blockid][0][0]=x;
	block_data[blockid][0][1]=y;
	if(block_data[blockid][1][2]>0){
		board_beta[x+block_data[blockid][1][0]] [y+block_data[blockid][1][1]]=block_data[blockid][1][2];
		update_ranks();
	}else{
		board_beta[x+block_data[blockid][1][0]] [y+block_data[blockid][1][1]]=SHRT_MIN;
	}
	if(block_data[blockid][2][2]!=-1){ //if not monomino
		for(i=2;i<=4;i++)
			if(block_data[blockid][i][2]>0){
				board_beta[x+block_data[blockid][i][0]] [y+block_data[blockid][i][1]]=block_data[blockid][i][2];
				update_ranks();
			}else{
				board_beta[x+block_data[blockid][i][0]] [y+block_data[blockid][i][1]]=SHRT_MIN;
			}
	}
	add_point(blockid);
	return;
}

void remove_block(short int blockid){ //not for monomino
	if(point[blockid]<0)
		point[blockid]=-point[blockid];
	board_beta[block_data[blockid][0][0]+block_data[blockid][1][0]] [block_data[blockid][0][1]+block_data[blockid][1][1]]=0;
	erase_line(block_data[blockid][1][2]);
	if(block_data[blockid][2][2]!=-1){ //if not monomino
		board_beta[block_data[blockid][0][0]+block_data[blockid][2][0]] [block_data[blockid][0][1]+block_data[blockid][2][1]]=0;
		board_beta[block_data[blockid][0][0]+block_data[blockid][3][0]] [block_data[blockid][0][1]+block_data[blockid][3][1]]=0;
		board_beta[block_data[blockid][0][0]+block_data[blockid][4][0]] [block_data[blockid][0][1]+block_data[blockid][4][1]]=0;
		erase_line(block_data[blockid][2][2]);
		erase_line(block_data[blockid][3][2]);
		erase_line(block_data[blockid][4][2]);
	}
	block_data[blockid][0][0]=-1;
	block_data[blockid][0][1]=-1;
	sub_point(blockid);
	return;
}

short int place_and_line(short int blockid){
	short int i,j;
	if(DEBUG){
		printf("#%d   RANKS (rank: block, point)\n",attempts);
		for(i=1;i<=blocks;i++){
			printf("      %d: %d, %d\n",i,rank[i],point[rank[i]]);
		}
	}
	if(first_block==1){
		first_block--;
		place_block(blockid,MAXSIZE/2,MAXSIZE/2);
		point[blockid]=-point[blockid];
		update_ranks();
		if(DEBUG){
			printf("#%d   Block %d placed @(%d,%d)\n",attempts,blockid,block_data[blockid][0][0],block_data[blockid][0][1]);
			print_board_beta();
		}
		return 1;
	}
	j=search_placable(blockid);
	for(i=1;i<=j;i++){
		/* printf("place: block %d\n",blockid); */
		place_block(blockid,costrank[i][0],costrank[i][1]);
		if(try_wires(blockid)){
			point[blockid]=-point[blockid];
			update_ranks();
			return 1;
		}
		remove_block(blockid);
	}
	return 0;
}

void solve(short int seed){ //solver part
	short int i, in_process=1;
	srand(seed);
	while(in_process){
		if(DEBUG){
			printf("\n#%d attempt\n",attempts);
		}
		while(1){
			i=rank[1];
			if(block_data[i][0][0]<0){ //not placed
				if(!place_and_line(i)){ //if not placable
					point[i]+=100;
					if(point[i]>10000||attempts>=100){ //no answer
						printf("Too many trials!\n");
						in_process=0; //end solver
						break;
					}
					shuffle_random(rand());
					reset();
					break; //solve from beginning
				}
			}else
				return;
		}
		attempts++;
	}
	return;
}

/* void shape(void){ */
/* 	return; */
/* } */

void translate(void){ //translate bigboard to minimal board
	short int i,j;
	short int minw=MAXSIZE-1,maxw=0,minh=MAXSIZE-1,maxh=0;
	for(i=0;i<MAXSIZE;i++){
		for(j=0;j<MAXSIZE;j++){
			if(board_beta[i][j]){
				if(i>maxw)
					maxw=i;
				if(i<minw)
					minw=i;
				if(j>maxh)
					maxh=j;
				if(j<minh)
					minh=j;
				if(board_beta[i][j]==SHRT_MIN)
					board_beta[i][j]=0;
				else if(board_beta[i][j]<0)
					board_beta[i][j]=-board_beta[i][j];
			}
		}
	}
	for(i=1;i<=blocks;i++){
		block_data[i][0][0]-=minw;
		block_data[i][0][1]-=minh;
	}
	/* printf("%d %d %d %d\n",minw,maxw,minh,maxh); */
	if(minh<maxh&&minw<maxw)
		for(i=minw;i<=maxw;i++){
			for(j=minh;j<=maxh;j++){
				board_data[i-minw][j-minh]=board_beta[i][j];
			}
		}
	w=maxw-minw+1;
	h=maxh-minh+1;
	if(w<0)
		w=0;
	if(h<0)
		h=0;
	return;
}

void solver(void){
	short int seed=time(NULL); //edit here
	/* short int seed=1; //edit here */
	shuffle_random(seed);
	init_points();
	reset();
	solve(seed);
	/* shape(); */
	/* print_board_beta(); */
	translate();
	return;
}