/* solver.c */
/* Last Change: 2019/07/23 (Tue) 17:13:18. */

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

/* 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])

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

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

void reset(void){ //excluding init_points
	short int i,j;
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++)
			board_beta[i][j]=0;
	for(i=1;i<=blocks;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]++;
	}
	update_ranks();
	return;
}

void add_point(short int blockid,short int lineid){ //use only once
	short int i,j;
	for(i=1;i<=blocks;i++)
		if(i!=blockid)
			for(j=1;j<=4;j++)
				if(block_data[i][j][2]==lineid) //if edge exists
					point[i]+=10;
	return;
}

/* short int random(short int id){ //edit this to randomly place blocks */
/* return id; */
/* } */

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;
	if(block_data[blockid][2][2]==-1){ //if monomino
		return 1;
	}
	/* calc cost */
	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]=i-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;
				/* printf("%d, %d\n",abs(i-place[k][0]),abs(j-place[k][1])); */
				/* printf("%d\n",abs(i-place[k][0])+abs(j-place[k][1])); */
				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]=abs(i-MAXSIZE/2)+abs(j-MAXSIZE/2);
				/* cost[i][j][0]+=(short int)abs((int)(i-place[k][0]))+(short int)abs((int)(j-place[k][1])); */
				cost[i][j][0]=10000-cost[i][j][0];
				/* printf("%d\n",cost[i][j][0]); */
			}
		}
	}
	//ok
	/* 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;
}

short int try_wire(short int blockid){
	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];
		add_point(blockid,block_data[blockid][1][2]);
	}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];
				add_point(blockid,block_data[blockid][i][2]);
			}else{
				board_beta[x+block_data[blockid][i][0]] [y+block_data[blockid][i][1]]=SHRT_MIN;
			}
	}
	return;
}

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;
	return;
}

void remove_block(short int blockid){ //not for monomino
	short int i,j;
	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;
	for(i=1;i<=blocks;i++)
		if(i!=blockid)
			for(j=1;j<=4;j++){
				if(block_data[i][j][2]>0){ //if block exists
					if(block_data[i][j][2]==block_data[blockid][1][2]){ //if edge exists
						point[i]-=10;
					}else if(block_data[blockid][2][2]!=-1){ //if not monomino
						if(block_data[i][j][2]==block_data[blockid][2][2]){ //if edge exists
							point[i]-=10;
						}
						if(block_data[i][j][2]==block_data[blockid][3][2]){ //if edge exists
							point[i]-=10;
						}
						if(block_data[i][j][2]==block_data[blockid][4][2]){ //if edge exists
							point[i]-=10;
						}
					}
				}
			}
	update_ranks();
	return;
}

short int place_and_line(short int blockid){
	short int i,j;
	if(first_block==1){
		first_block--;
		place_block(blockid,MAXSIZE/2,MAXSIZE/2);
		return 1;
	}
	j=search_placable(blockid);
	for(i=1;i<=j;i++){
		place_block(blockid,costrank[i][0],costrank[i][1]);
		if(try_wire(blockid))
			return 1;
		remove_block(blockid);
	}
	return 0;
}

void solve(void){ //solver part
	short int i, flag, in_process=1;
	while(in_process){
		flag=1;
		for(i=1;i<=blocks;i++)
			if(block_data[rank[i]][0][0]<0){ //not placed
				if(!place_and_line(rank[i])){ //if not placable
					point[i]+=100;
					if(point[i]>10000){ //no answer
						printf("Too many attempts!\n");
						in_process=0; //end solver
						break;
					}
					reset();
					break; //solve from beginning
				}
				flag=0;
			}
		if(flag)
			break;
	}
	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){
	init_points();
	reset();
	solve();
	/* shape(); */
	/* print_board_beta(); */
	translate();
	return;
}