/* solver.c */
/* Last Change: 2019/05/21 (Tue) 18:09:17. */

#include<limits.h>
#include"solver.h"
#include"io.h"
#include<stdio.h>
#include <list>
#include <bits/stdc++.h>
#include "router/router.hpp"
/* #include<stdlib.h> */
/* #include<string.h> */
/* #include<math.h> */
/* #include<time.h> */

#define SPACE 1

short int connected[MAXLINE]={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];
short int done_block[MAXBLOCK+1];
short int board_str[900];
vector <int> mino_order;

void reset_board(void){
	int i,j;
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++)
			board_beta[i][j]=0;
	return;
}

void show_blocks(){
	int data[4][4];
	int i,j,k;
	for(i=1;i<blocks;i++){
		printf("block #%d\n",i);
		for(j=1;j<=4;j++){
			printf("x:%d y:%d edge:%d\n",block_data[i][j][0],block_data[i][j][1],block_data[i][j][2]);
		}
	}
	return;
}

void read_data(void){
	//show_blocks();
	return;
}


void translate(void){
	int i,j;
	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]-=minw; */
		/* block_data[i][1]-=minh; */
	}
	for(i=0;i<maxw-minw;i++){
		for(j=0;j<maxh-minh;j++){
			board_data[i][j]=board_beta[i+minw][j+minh];
		}
	}
	return;
}

void init_mino(void){
	int i;
	for(i=1;i<MAXBLOCK+2;i++){
		done_block[i]=0;
	}
}

int check_around(int x,int y){
	if(board_data[x+1][y] || board_data[x][y+1] || board_data[x-1][y] || board_data[x][y-1]||
	board_data[x+1][y+1]||board_data[x+1][y-1]||board_data[x-1][y-1]||board_data[x-1][y+1]) return 1;
	else{
		return 0;
	}
}
void del_mino(int mino){
	int x,y;
	x=block_data[mino][0][0];
	y=block_data[mino][0][1];
	for(int i=1;i<5;i++){
		board_data[x+block_data[mino][i][0]][y+block_data[mino][i][1]]=0;
	}
	block_data[mino][0][0]=-1;
	block_data[mino][0][1]=-1;
}

int check_put_mino(int i,int x, int y){// check block#i can put on x,y
	for(int j=1;j<5;j++){
		if(x+block_data[i][j][0]>W-1){
			return 0;
		}
		if(y+block_data[i][j][1]>H-1){
			return 0;
		}
		if(board_data[x+block_data[i][j][0]][y+block_data[i][j][1]]!=0){
			return 0;
		}
		if(check_around(x+block_data[i][j][0],y+block_data[i][j][1])){
			return 0;
		}
	}
	return 1;
}


void data_mino(int i, int x,int y){
	std::cout << "put mino "<< i << "on" << x <<" " << y << std::endl;
	for(int j=0;j<100;j++){
		if(check_put_mino(i,x,y)){
			for(int l=1;l<5;l++){
				if(l==2 && block_data[i][l][2]==-1){
					block_data[i][0][0]=x;
					block_data[i][0][1]=y;
					return;
				}
				if(block_data[i][l][2]!=0){
					board_data[x+block_data[i][l][0]][y+block_data[i][l][1]]=block_data[i][l][2];
				}else{
					board_data[x+block_data[i][l][0]][y+block_data[i][l][1]]=-1;
				}
			}
			block_data[i][0][0]=x;
			block_data[i][0][1]=y;
			 return;
		}
		x+=(j%2)*SPACE;
		y+=((j+1)%2)*SPACE;
		if(x>W || y>H) return;
	}
}

void put_mino(){
	int i,j,k,now;
	std::vector<int> order_w;
	std::vector<int> order_h;
	int map_w[4]={0,0,0,0};
	int map_h[4]={0,0,0,0};
	int len[MAXBLOCK+1];
	int check_block[100];//block in the order_w
	int done_block[100];//fixed block in the order_w
	int end;
	int flag=0;
	order_w.push_back(1); // start from block#1
	int index=0;
	int next=0;
	int x=0;
	int another=0;
	auto itr=order_w.begin();
	while(true){
		another=0;
		for(index=order_w.size()-1;index>=0;index--){ // find next block
			if(done_block[order_w[index]]==0){
				next=order_w[index];
				another=1;
				//done_block[next]=1;
				//check_block[next]=1;
				break;
			}
		}
		if(index==-1){
			for(index=blocks;index>0;index--){
				if(done_block[index]==0){
					next=index;
					break;
				}
			}
			if(index==0) break; // if all blocks are searched
		}
		if(index==-1) break; // if all blocks are searched
		if(another){
			itr=order_w.begin();
			for(int i=0;i<index;i++){//remove index itretor
				itr++;
			}
			order_w.erase(itr);
		}else{
			itr=order_w.end();
		}
		std::cout << "block#"<<next << std::endl;
		//make block order
		if(block_data[next][1][0]==block_data[next][2][0]){
			std::cout << "patern 1"<< std::endl;
			if(block_data[next][2][0]==block_data[next][3][0] || block_data[next][2][1]==block_data[next][4][1]){//for I-mino1,L-mino1,T-mino1,S-mino1,Lf-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][4][2];
			}else{
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][4][2];
				map_w[3]=block_data[next][3][2];
			}
		}else if(block_data[next][1][1]==block_data[next][4][1]){//I-mino2
			std::cout << "patern 2"<< std::endl;			
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][4][2];
		}else if(block_data[next][1][1]==block_data[next][2][1]){
			std::cout << "patern 3"<< std::endl;
			if(block_data[next][1][0]==block_data[next][4][0]){//L-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][4][2];
				map_w[2]=block_data[next][2][2];
				map_w[3]=block_data[next][3][2];
			}else{//S-mino2,Sf,mino2,O-mino,L-mino3,Lf-mino1,Lf-mino3,T-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][3][2];
				map_w[2]=block_data[next][4][2];
				map_w[3]=block_data[next][2][2];
			}
		}else if(block_data[next][2][1]==block_data[next][3][1]&&block_data[next][3][0]==block_data[next][4][0]){
			//std::cout << "patern 4"<< std::endl;
				map_w[0]=block_data[next][2][2];
				map_w[1]=block_data[next][4][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][1][2];
		}else{
			//std::cout << "patern 5"<< std::endl;
			map_w[0]=block_data[next][1][2];
			map_w[1]=block_data[next][2][2];
			map_w[2]=block_data[next][3][2];
			map_w[3]=block_data[next][4][2];
		}
		for(int k=0;k<4;k++){
			std::cout << map_w[k]<<" ";
		}
		std::cout << std::endl;
		for(int k=0;k<4;k++){
			if(map_w[k]==0) continue;
			flag=0;
			for(int i=1;i<=blocks;i++){
				if(i==next) continue;
				for(int j=1;j<=4;j++){// find pair block
					if(block_data[i][j][2]==map_w[k]){
						std::cout << k << " " << map_w[k]<< "found at " << i << std::endl;
						if(check_block[i]==1 || done_block[i]==1){
							map_w[k]=0;
						}else{
							check_block[i]=1;
							map_w[k]=i;
						}
						flag=1;
						break;
					}
					//if(j==4) std::cout << "not found " << map_w[k] <<std::endl;
				}
				if(flag==1) break;
			}
		}
		for(int i=0;i<4;i++){
			if(i==2){
				itr=order_w.insert(itr,next);
				itr++;
			}
			if(map_w[i]==0|| map_w[i]==-1) continue;
			itr=order_w.insert(itr,map_w[i]);
			itr++;
		}
		done_block[next]=1;
		for(int i=0;i<order_w.size();i++){
			printf("%d ",order_w[i]);
		}
		printf("\n");
		x++;
		if(x==10)break;
	}//end of while ture for width
	printf("answer is \n");
	for(int i=0;i<order_w.size();i++){
		printf("%d ",order_w[i]);
	}
	printf("\n");




	printf("\n\nstart making order of height\n");
	for(int i=1;i<=blocks;i++){//init status
		check_block[i]=0;
		done_block[i]=0;
	}
	next=0;
	itr=order_h.begin();
	order_h.push_back(1);
	another=0;
	while(true){//start of while true for height
		another=0;
		for(index=order_h.size()-1;index>=0;index--){ // find next block
			if(done_block[order_h[index]]==0){
				next=order_h[index];
				another=1;
				break;
			}
		}
		if(index==-1){
			std::cout << "left block search" << std::endl;
			for(index=blocks;index>0;index--){
				if(done_block[index]==0){
					next=index;
					break;
				}
			}
			if(index==0) break; // if all blocks are searched
		}
		//std::cout << "now" << std::endl;
		if(another==1){
			itr=order_h.begin();
			for(int i=0;i<index;i++){//remove index itretor
				itr++;
			}
			order_h.erase(itr);
		}else{
			itr=order_h.end();
		}
		std::cout << "block#"<<next << std::endl;
		for(int k=1;k<=4;k++){
			std::cout << block_data[next][k][0];
		}
		std::cout << std::endl;
		//make block order
		if(block_data[next][1][1]==block_data[next][2][1]){
			std::cout << "patern 1"<< std::endl;
			if(block_data[next][3][1]==block_data[next][4][1]){//for I-mino2,S-mino2,Sf-mino2,O-mino
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][3][2];
			}else{//for L-mino3,L-mino4,Lf-mino2,Lf-mino3,T-mino4
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
			}
		}else if(block_data[next][1][0]==block_data[next][4][0]){//I-mino1
			std::cout << "patern 2"<< std::endl;			
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
		}else if(block_data[next][1][0]==block_data[next][2][0]){
			std::cout << "patern 3"<< std::endl;
			if(block_data[next][3][1]==block_data[next][4][1]){//L-mino1,Lf-mino1
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][3][2];
			}else{//T-mino1,Lf-mino4,S-mino1
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][3][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][2][2];
			}
		}else if(block_data[next][1][0]==block_data[next][3][0]&&block_data[next][4][1]!=1){//T-mino3,Sf-mino1
			std::cout << "patern 4"<< std::endl;
				map_h[0]=block_data[next][2][2];
				map_h[1]=block_data[next][1][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
		}else{//L-mino2,T-mino2
			std::cout << "patern 5"<< std::endl;
			map_h[0]=block_data[next][2][2];
			map_h[1]=block_data[next][1][2];
			map_h[2]=block_data[next][4][2];
			map_h[3]=block_data[next][3][2];
		}
		for(int k=0;k<4;k++){
			std::cout << map_h[k]<<" ";
		}
		std::cout << std::endl;
		for(int k=0;k<4;k++){
			if(map_h[k]==0) continue;
			flag=0;
			for(int i=1;i<=blocks;i++){
				if(i==next) continue;
				for(int j=1;j<=4;j++){// find pair block
					if(block_data[i][j][2]==map_h[k]){
						std::cout << k << " " << map_h[k]<< "found at " << i << std::endl;
						if(check_block[i]==1 || done_block[i]==1){
							map_h[k]=0;
						}else{
							check_block[i]=1;
							map_h[k]=i;
						}
						flag=1;
						break;
					}
					//if(j==4) std::cout << "not found " << map_w[k] <<std::endl;
				}
				if(flag==1) break;
			}
		}
		for(int i=0;i<4;i++){
			if(i==2){
				itr=order_h.insert(itr,next);
				itr++;
			}
			if(map_h[i]==0|| map_h[i]==-1) continue;
			itr=order_h.insert(itr,map_h[i]);
			itr++;
		}
		for(int i=0;i<order_h.size();i++){
			printf("%d ",order_h[i]);
		}
		printf("\n");
		done_block[next]=1;
		//x++;
		//if(x==1)break;
	}//end of while ture for height

	printf("width is \n");
	for(int i=0;i<order_w.size();i++){
		printf("%d ",order_w[i]);
	}
	printf("\n");

	printf("height is \n");
	for(int i=0;i<order_h.size();i++){
		printf("%d ",order_h[i]);
	}
	printf("\n");

	int put_block[100];
	int height_c=0,width_c=1;
	int next_put=1;
	int max_w=0;
	int max_h=0;
	for(int i=0;i<blocks;i++){
		height_c=height_c+SPACE;
		width_c=SPACE;
		max_w=0;
		max_h=0;
		next_put = order_h[i];
		for(int j=0;j<blocks;j++){
			if(order_w[j]==next_put) break;
			for(k=1;k<5;k++){
				if(block_data[order_w[j]][k][0]>max_w) max_w = block_data[order_w[j]][k][0];	
			}
			//std::cout<< "add " << order_w[j] << " mino " << max_w << std::endl;
			width_c+=max_w+SPACE;
		}
		//std::cout << width_c << std::endl;
		//std::cout << height_c << std::endl;
		if(max_w==0) data_mino(next_put,width_c,height_c);
		else data_mino(next_put,width_c+SPACE,height_c);
		for(int k=1;k<5;k++){
			if(block_data[next_put][k][1]>max_h) max_h = block_data[next_put][k][1];
		}
		height_c+=max_h+1;
	}
	print_answer();
	//int next;
	int mino_x,mino_y;
	/*for(int i=0;i<blocks;i++){
		next=mino_order[i];
		mino_x=block_data[i][0][0];
		mino_y=block_data[i][0][1];
		del_mino(next);
		if(i%2){
			for(int j=mino_x-1;j>1;j--){
				if(check_put_mino(next,j,mino_y)){
					mino_x=j;
				}else{
					break;
				}
			}
		}else{
			for(int j=mino_y-1;j>1;j--){
				if(check_put_mino(next,mino_x,j)){
					mino_y=j;
				}else{
					break;
				}
			}

		}
		data_mino(next,mino_x,mino_y);
	}*/
}
void make_board_str(int size_x,int size_y){
	for(int y = 0; y < size_y; y++) {
		for(int x = 0; x < size_x; x++) {
			int idx = y * size_x + x;
			board_str[idx] = board_data[x][y];
		}
	}
}
void fix_to_board(int size_x, int size_y){
	for(int y = 0; y < size_y; y++) {
		for(int x = 0; x < size_x; x++) {
			int idx = y * size_x + x;
			board_data[x][y] = board_str[idx];
		}
	}
}


void line(){
	make_board_str(W,H);
	std::cout <<  lfsr <<std::endl;
	int status = router(W, H, line_num, board_str);
	if(status){
		std::cout << "success to line" << std::endl;
	}else{
		std::cout << "failed to line" << std::endl;
	}
	fix_to_board(W,H);
}

void solve(void){
	init_mino();
	put_mino();
	line();
	return;
}

void solver(void){
	read_data();
	solve();
	/* shape(); */
	translate();
	return;
}