#define F_CPU 16934400

#include <stdio.h>
#include <stdlib.h>

#include <avr/io.h>
#include <avr/interrupt.h>
#include <avr/pgmspace.h>
#include <inttypes.h>

#include "../libnerdkits/delay.h"

//Display Vars
volatile uint8_t cCol,evenOdd,doUpdate;
volatile uint16_t rows[16];

//Game Vars
struct PIECE{
	int8_t  piece[4][4],type;
	int8_t  x,y;
};

struct PIECE currentPiece;
int8_t board[10][22];

void RotatePiece();
void right();
void left();
uint8_t Update();
void NextPiece();

//AI Stuff
#define AI_NO_MOVE	0
#define AI_LEFT		1
#define AI_RIGHT	2
#define AI_ROTATE	3

uint8_t x;
uint8_t rotate;

int8_t minofpos(int8_t a,int8_t b,int8_t c,int8_t d);

void thinkAI(int8_t board[10][22],struct PIECE *current);
int8_t makeMoveAI(struct PIECE *current);
void boardcpy(int8_t dboard[10][22],int8_t sboard[10][22]);
int16_t CalcScore(int8_t line,int8_t tboard[10][22]);
void RotateAI(struct PIECE *current);

//Display Driver
SIGNAL(SIG_OVERFLOW0) {
  //Only preform fuction every 4 timer clicks
  if(doUpdate>4) {doUpdate=0;}
  if(doUpdate!=0) {doUpdate++; return;}
  doUpdate++;
  
  //Reset Counts
  if(cCol==10) cCol=0;
  if(evenOdd==2) evenOdd=0;
  
  //Turn off LEDs
  //Cols
  DDRB &= ~( (1<<PB1)|(1<<PB2)|(1<<PB3)|(1<<PB4)|(1<<PB5) );
  DDRC &= ~( (1<<PC1)|(1<<PC2)|(1<<PC3)|(1<<PC4)|(1<<PC5) );
  
  //Rows
  DDRB &= ~(1<<PB0);
  DDRC &= ~(1<<PC0);
  DDRD &= ~( (1<<PD7)|(1<<PD6)|(1<<PD5)|(1<<PD4)|(1<<PD3)|(1<<PD2) );
  
  //Set Row
  if((rows[evenOdd] & (1<<cCol))){
    if(evenOdd) PORTC &= ~(1<<PC0); else PORTC |= (1<<PC0);
    DDRC |= (1<<PC0);
  }
  if((rows[evenOdd+2] & (1<<cCol))){
    if(evenOdd) PORTB &= ~(1<<PB0); else PORTB |= (1<<PB0);
    DDRB |= (1<<PB0);
  }
  if((rows[evenOdd+4] & (1<<cCol))){
    if(evenOdd) PORTD &= ~(1<<PD7); else PORTD |= (1<<PD7);
    DDRD |= (1<<PD7);
  }
  if((rows[evenOdd+6] & (1<<cCol))){
    if(evenOdd) PORTD &= ~(1<<PD6); else PORTD |= (1<<PD6);
    DDRD |= (1<<PD6);
  }
  if((rows[evenOdd+8] & (1<<cCol))){
    if(evenOdd) PORTD &= ~(1<<PD5); else PORTD |= (1<<PD5);
    DDRD |= (1<<PD5);
  }
  if((rows[evenOdd+10] & (1<<cCol))){
    if(evenOdd) PORTD &= ~(1<<PD4); else PORTD |= (1<<PD4);
    DDRD |= (1<<PD4);
  }
  if((rows[evenOdd+12] & (1<<cCol))){
    if(evenOdd) PORTD &= ~(1<<PD3); else PORTD |= (1<<PD3);
    DDRD |= (1<<PD3);
  }
  if((rows[evenOdd+14] & (1<<cCol))){
    if(evenOdd) PORTD &= ~(1<<PD2); else PORTD |= (1<<PD2);
    DDRD |= (1<<PD2);
  }
  
  //Set Columns
  if(cCol<5){
    if(evenOdd) PORTB |= (1<<(PB1+cCol)); else PORTB &= ~(1<<(PB1+cCol));
	DDRB |= (1<<(PB1+cCol));
  } else {
    if(evenOdd) PORTC |= (1<<(PC1+cCol-5)); else PORTC &= ~(1<<(PC1+cCol-5));
	DDRC |= (1<<(PC1+cCol-5));
  } 
    
  //Update Vars
  if(evenOdd==1) cCol++;
  evenOdd++;
}

void updateDisplay() {
  int8_t x,y;
  uint16_t row;
  int8_t tboard[10][22];
  
  boardcpy(tboard,board);

  for (x=0;x<4;x++)
    for (y=0;y<4;y++)
      if ((currentPiece.x+x<10)&&(currentPiece.y+y<22)&&(currentPiece.piece[x][y]!=0))
        tboard[x+currentPiece.x][y+currentPiece.y]=currentPiece.piece[x][y];
					
  for(y=0;y<22;y++){
    row=0;
	  for(x=0;x<10;x++){
	    if(tboard[x][y]!=0) row|=1<<x;
	  }
	  if(21-y<16) rows[21-y]=row;
  }
}

int main() {
  uint8_t GameOver,GameState,i,j;
  //init defaults
  cCol=0;
  evenOdd=0;
  doUpdate=0;

  //Setup Timer Interupt
  TCCR0B = (1<<CS01);
  TIMSK0 = (1<<TOIE0);
  
  sei();
  
  // busy loop
  while(1) {
    GameOver=0;
	  GameState=0;
    for(i=0;i<10;i++)
      for(j=0;j<22;j++)
          board [i][j] = 0;
    
    NextPiece();
	  thinkAI(board, &currentPiece);
	
	  while(GameOver==0){
	    switch(GameState%2){
	      case 0:
		      if(Update()) {GameOver=1; }
		      break;
        case 1:
          switch (makeMoveAI(&currentPiece)){
            case AI_LEFT:
              left();
              break;
            case AI_RIGHT:
              right();
              break;
            case AI_ROTATE:
              RotatePiece();
              break;
          }
          break;
	    }
	    updateDisplay();
      GameState++;
	    delay_ms(30);
	  }
  }
  return 0;
}

uint16_t rnd_seed=1234;
uint16_t rand_int () {
  uint16_t hi,lo;

  hi = 8403 * (rnd_seed >> 8);
  lo = 8403 * (rnd_seed & 0xFF);
  lo += (hi & 0x7F) << 8;
  lo += hi >> 7;
  if (lo > 32767) lo -= 32767;
  rnd_seed = lo;
  return rnd_seed;
}

void NextPiece() {
  int8_t x,y;

  for(x=0;x<4;x++)
    for(y=0;y<4;y++)
      currentPiece.piece[x][y] = 0;

  switch (rand_int()%7){
    case 0:     //line
      currentPiece.piece[0][1]=2;
      currentPiece.piece[1][1]=2;
      currentPiece.piece[2][1]=2;
      currentPiece.piece[3][1]=2;
      currentPiece.type = 1;
      break;
    case 1:       //L
      currentPiece.piece[1][2]=3;
      currentPiece.piece[2][2]=3;
      currentPiece.piece[3][2]=3;
      currentPiece.piece[1][1]=3;
      currentPiece.type = 2;
      break;
    case 2:       //BL
      currentPiece.piece[1][2]=4;
      currentPiece.piece[2][2]=4;
      currentPiece.piece[3][2]=4;
      currentPiece.piece[2][1]=4;
      currentPiece.type = 2;
      break;
    case 3:      //T
      currentPiece.piece[1][2]=5;
      currentPiece.piece[2][2]=5;
      currentPiece.piece[3][2]=5;
      currentPiece.piece[3][1]=5;
      currentPiece.type = 2;
      break;
    case 4:  // Square
      currentPiece.piece[1][1]=6;
      currentPiece.piece[1][2]=6;
      currentPiece.piece[2][1]=6;
      currentPiece.piece[2][2]=6;
      currentPiece.type = 3;
    break;
    case 5: // z
      currentPiece.piece[0][1]=7;
      currentPiece.piece[1][2]=7;
      currentPiece.piece[1][1]=7;
      currentPiece.piece[2][2]=7;
      currentPiece.type = 1;
    break;
    case 6:// s
      currentPiece.piece[1][1]=8;
      currentPiece.piece[0][2]=8;
      currentPiece.piece[2][1]=8;
      currentPiece.piece[1][2]=8;
      currentPiece.type = 1;
    break;
  }
  currentPiece.x=3;
  currentPiece.y=0;
}

uint8_t Update() {
	int8_t x,y,i,change_all=0,game_over=0,loop=1,line=0;
	int8_t tboard [10] [22];

	boardcpy(tboard,board);

  //Piece Reached Bottom of board must Place
	for (x=0;x<4;x++)
		for (y=0;y<4;y++)
			if((currentPiece.piece[x][y]!=0)&&(currentPiece.y+y==21))
				change_all=1;

  //Check if moving piece down would make overlap with board if so place in current location
	if (change_all!=1)
		for (x=0;x<4;x++)
			for (y=0;y<4;y++)
				if ((currentPiece.x+x<10)&&(currentPiece.y+y+1<22)&&(currentPiece.piece[x][y]!=0))
					if (tboard[x+currentPiece.x][y+currentPiece.y+1]!=0)
						change_all=1;

  //Write Piece to board if need
	if (change_all==1){
		for (x=0;x<4;x++)
			for (y=0;y<4;y++)
				if ((currentPiece.x+x<10)&&(currentPiece.y+y>=0)&&(currentPiece.piece[x][y]!=0))
					tboard[x+currentPiece.x][y+currentPiece.y]=currentPiece.piece[x][y];

    boardcpy(board,tboard);
		NextPiece();
  }

  //check if any pieces is in the game over section of the board
	for (x=0;x<10;x++)
		for (y=0;y<6;y++)
			if (tboard[x][y]!=0)
				game_over=1;

	y=21;

  //Check for and remove all completed lines
	if ((change_all==1)&&(game_over!=1))
		while(loop){
			if ((board[0][y]!=0)&&(board[1][y]!=0)&&(board[2][y]!=0)&&(board[3][y]!=0))
				if ((board[4][y]!=0)&&(board[5][y]!=0)&&(board[6][y]!=0)&&(board[7][y]!=0))
					if ((board[8][y]!=0)&&(board[9][y]!=0)){
						for (x=0;x<10;x++)
							for (i=y-1;i>0;i--){
								board[x][i+1]=board[x][i];
								board[x][i]=0;
							}
							y++;
							line++;
					}
			y--;
			if (y<=0)	loop=0;
		}

  //Move Piece down or calculate where new piece will go
	if(change_all==0)
		currentPiece.y++;
	else
		thinkAI(board, &currentPiece);

  //Let program know game over has occured
	return game_over;
}

void left() {
	int8_t x,y,can_move=1;
	int8_t tboard [10] [22];

	boardcpy(tboard,board);
	
	for (x=0;x<4;x++)
		for (y=0;y<4;y++)
			if ((currentPiece.x+x<10)&&(currentPiece.y+y<22)&&(currentPiece.piece[x][y]))
				tboard[x+currentPiece.x][y+currentPiece.y]=1;

	for (y=0;y<22;y++)
		if (tboard[0][y]==1)
			can_move=0;

	for (x=1;x<10;x++)
		for (y=0;y<22;y++)
			if ((tboard[x][y]==1)&&(tboard[x-1][y]>1))
				can_move=0;

	if (can_move==1)
		currentPiece.x--;
}

void right() {
	int8_t x,y,can_move=1;
	int8_t tboard [10] [22];

	boardcpy(tboard,board);

	for (x=0;x<4;x++)
		for (y=0;y<4;y++)
			if ((currentPiece.x+x<10)&&(currentPiece.y+y<22)&&(currentPiece.piece[x][y]))
				tboard[x+currentPiece.x][y+currentPiece.y]=1;

	for (y=0;y<22;y++)
		if (tboard[9][y]==1)
			can_move=0;

	for (x=0;x<9;x++)
		for (y=0;y<22;y++)
			if ((tboard[x][y]==1)&&(tboard[x+1][y]>1))
				can_move=0;

	if (can_move==1)
		currentPiece.x++;
}

void RotatePiece() {
	int8_t x,y,can_rotate=1;
	int8_t temp [4][4];

	for(x=0;x<4;x++)
		for(y=0;y<4;y++)
			temp[x][y] = 0;

	switch(currentPiece.type) {
		case 1:
      for(x=0;x<4;x++)
        for(y=0;y<4;y++)
					temp[y][3-x] = currentPiece.piece[x][y];
			break;
		case 2:
			for(x=1;x<4;x++)
				for(y=0;y<3;y++)
					temp[y+1][3-x] = currentPiece.piece[x][y];
			break;
		case 3:
			can_rotate=0;
			break;
	}

	for(x=0;x<4;x++)
		for(y=0;y<4;y++)
			if (temp[x][y]!=0)
				if((x+currentPiece.x<0)||(x+currentPiece.x>9)||(y+currentPiece.y>21)||
					(board[x+currentPiece.x][y+currentPiece.y]!=0))
					can_rotate=0;
  
	if (can_rotate==1){
		for(x=0;x<4;x++)
			for(y=0;y<4;y++)
				currentPiece.piece[x][y] = temp[x][y];
  
	}
}

int8_t makeMoveAI(struct PIECE *current) {
	int8_t tx,i,j,hit=0;

	if (rotate){
		rotate--;
		return AI_ROTATE;
	}
	/*** Detimaning if need to move left or right ********************/
	tx=x;
	for (i=0;i<4;i++){
		for (j=0; j<4; j++){
			if(current->piece[i][j]!=0){
				hit=1;
				break;
			}
		}
		if (hit){
			tx = current->x + i;
			break;
		}
	}
	
	if(tx > x) return AI_LEFT;
	if (tx < x)	return AI_RIGHT;

	/*** No shift or rotation is need ********************************/
	return AI_NO_MOVE;
}

void thinkAI(int8_t tboard[10][22],struct PIECE *tcurrent) {
	int16_t x2,y,i,change_all=0,loop=1,line=0,crotate=0;
	int16_t hit,j,t,q=0,score=0,a=10000;
	int16_t wLow=0,wHigh=0;
	int16_t temp;
	int8_t board[10][22];
	struct PIECE current;

	rotate = 0;
	/*** The AI will start be getting some basic info **********/
	current.x = tcurrent->x;
	current.y = tcurrent->y;
	current.type = tcurrent->type;
	for(x2=0;x2<4;x2++)
		for(y=0;y<4;y++)
			current.piece[x2][y] = tcurrent->piece[x2][y];

	/*** Checking all piece placment spots ***********************/
	//will need to run threw all Rotations
	for(q=0;q<4;q++){
		hit=0;
		for(i=0;i<4;i++){
			for(j=0;j<4;j++){
				if(current.piece[i][j]!=0){
					hit = 1;
					break;
				}
			}
			if(hit){
				wLow = i;
				break;
			}
		}
		hit=0;
		for(i=3;i>=0;i--){
			for(j=0;j<4;j++){
				if(current.piece[i][j]!=0){
					hit = 1;
					break;
				}
			}
			if(hit){
				wHigh = i;
				break;
			}
		}
		temp = 10 - wHigh;
		for(i=0-wLow;i<temp;i++){
			//Copies origanl board
			boardcpy(board,tboard);
			change_all=0;
			loop=1;
			line=0;
			t=0;

			//looping untill piece hits bottem of other blocks
			while(!change_all){
				for (x2=0;x2<4;x2++)
					for (y=0;y<4;y++)
						if((current.piece[x2][y]!=0)&&(current.y+y+t==21))
							change_all=1;
				if (change_all!=1)
					for (x2=0;x2<4;x2++)
						for (y=0;y<4;y++)
							if ((x2+i<10)&&(current.y+y+1+t<22)&&(current.piece[x2][y]!=0))
								if (board[x2+i][y+current.y+1+t]!=0)
									change_all=1;
				if(change_all==0)
					t++;
			}
			for (x2=0;x2<4;x2++)
				for (y=0;y<4;y++)
					if ((x2+i<10)&&(current.y+t+y>=0)&&(current.piece[x2][y]!=0))
						board[x2+i][y+current.y+t]=current.piece[x2][y];
			y=21;
			//Removes Lines
			while(loop){
				if ((board[0][y]!=0)&&(board[1][y]!=0)&&(board[2][y]!=0)&&(board[3][y]!=0))
					if ((board[4][y]!=0)&&(board[5][y]!=0)&&(board[6][y]!=0)&&(board[7][y]!=0))
						if ((board[8][y]!=0)&&(board[9][y]!=0)){
							for (x2=0;x2<10;x2++)
								for (j=y-1;j>0;j--){
									board[x2][j+1]=board[x2][j];
									board[x2][j]=0;
								}
								y++;
								line++;
						}
				y--;
				if (y==0)
					loop=0;
			}
			score = CalcScore(line,board);

			if (score < a){
				x = i +wLow;
				rotate = crotate;
				a = score;
			}
		}
		crotate++;
		RotateAI(&current);
	}
}

int8_t pDiff(int8_t a,int8_t b){
  if(a>b) return a-b;
  return b-a;
}

int16_t CalcScore(int8_t line,int8_t tboard[10][22]){
  int8_t holeCount=0,topDist=0,Heigh=0;
  int8_t y,x,active,lastHeigh=0;
  
  for(x=0;x<10;x++){
    active=0;
    for(y=0;y<22;y++){
      if(active){
        if(tboard[x][y]==0) holeCount++;
      }else{
        if(tboard[x][y]!=0) active=22-y;
      }
    }
    if(x==0){
      lastHeigh=active;
      Heigh=active;
    } else {
      topDist+=1+pDiff(active,lastHeigh);
      if(active>Heigh) Heigh=active;
      lastHeigh=active;
    }
  }

  if(Heigh>10){
    if(Heigh>15) return holeCount*5+topDist-line*4+500;
    return holeCount*5+topDist-line*4;
  } else {
    return holeCount*5+topDist-line*2;
  }
}


int8_t minofpos(int8_t a,int8_t b,int8_t c,int8_t d) {
	int temp;

	if (a < b) temp = a; else	temp = b;
	if (c < temp)	temp = c;
	if (d < temp)	temp = d;

	return temp;
}

void boardcpy(int8_t dboard[10][22],int8_t sboard[10][22]) {
	int i,j;
	for (i=0;i<10;i++){
		for (j=0;j<22;j++){
			 dboard[i][j] = sboard[i][j];
		}
	}
}


void RotateAI(struct PIECE *current) {
  int8_t x,y,can_rotate=1;
	char temp [4][4];

	for(x=0;x<4;x++)
		for(y=0;y<4;y++)
			temp[x][y] = 0;

	switch(current->type) {
		case 1:
			for(x=0;x<4;x++)
				for(y=0;y<4;y++)
          temp[y][3-x] = current->piece[x][y];
			break;
		case 2:
			for(x=1;x<4;x++)
				for(y=0;y<3;y++)
					temp[y+1][3-x] = current->piece[x][y];
			break;
		case 3:
			for(x=0;x<4;x++)
				for(y=0;y<4;y++)
					temp[x][y] = current->piece[x][y];
			can_rotate=0;
			break;
	}

	for(x=0;x<4;x++)
		for(y=0;y<4;y++)
			current->piece[x][y] = temp[x][y];
			
}