//
//  connect4.java
//  connect4
//
//  Created by Dan DeBlasio on 7/6/07.
//
//Solution
//
import java.util.*;
import java.io.*;

public class connect4 {

    public static void main (String args[]) throws IOException{
    
		//prepare for input
		Scanner in = new Scanner(System.in);
		
		//prompt for user names
		System.out.println("Player X, what is your name?");
		String playerX = in.next();
		
		System.out.println("Player Y, what is your name?");
		String playerY = in.next();
		
		//initialize variables
		int winner;
		char board[][] = new char[7][6];
		int i=0;
		
		//use do while cause you always want to execute once
		do{
			
			//select username
			String name = (i%2==0)?playerX:playerY;
			
			//prompt/get user input
			System.out.print(name+" please select a row:");
			int row = in.nextInt();
			
			//try to place in the row wanted
			//use row-1 for the actual array index starting at 0, not user input
			boolean placed = place(board,i,(row-1));
			
			//if you couldnt place it try again
			while(!placed){
				//if out of bounds
				if(row>6 || row<0){
					System.out.println("Sorry the row is invalid");
				}else{
					System.out.print("Sorry row "+ row +" is full.\n\nplease select a row:");
				}
				
				row = in.nextInt();
				
				//try to place in the row wanted
				//use row-1 for the actual array index starting at 0, not user input
				placed = place(board,i,(row-1));
			}
			
			//find winner if one exists
			winner = findFour(board);
			
			//print status
			print(board);
			
			i++;
			
		//stop when there are four in a row or its full
		}while(!full(board) && winner==-1);
		
		//print winner statement
		if(winner==1){
			System.out.println("Congradulations "+playerY+" You Won!!");
		}else if(winner==0){
			System.out.println("Congradulations "+playerX+" You Won!!");
		}else{
			System.out.println("Sorry, no one won.");
		}
        
	}//main
	
	//function takes in the board aray and outputs one of the following:
	//  1 - player X won
	//  0 - player O won
	//  -1 - no winner yet
	//
	//brute force contant algorithm
	private static int findFour(char board[][]){
		for(int i=0;i<7;i++){
			for(int j=0;j<6;j++){
				
				//initalize the return variables
				boolean r=true,u=true,ur=true,ul=true;
				//      right  up     up/right  up/left
				
				//must be 4 in a row
				for(int k=0;k<4;k++){
				
					//if you are out of bounds then no solution up
					if(j+k<6){
						u&=board[i][j]==board[i][j+k];
					}else{
						u=false;
					}
					
					//if you are out of bounds then no solution right
					if(i+k<7){
						r&=board[i][j]==board[i+k][j];
					}else{
						r=false;
					}
					
					//if you are out of bounds then no solution up and to the right
					if(i+k<7 && j+k<6){
						ur&=board[i][j]==board[i+k][j+k];
					}else{
						ur=false;
					}
					
					//if you are out of bounds then no solution up and to the left
					if(i+k<7 && j-k>=0){
						ul&=board[i][j]==board[i+k][j-k];
					}else{
						ul=false;
					}
				}
				
				//if any of them are true at this point and not blank, then you found one
				if((r || u || ul || ur) && (board[i][j]=='X' || board[i][j]=='O')){
					//return the winner
					return (board[i][j]=='X')?0:1;
				}
			}
		}
		return -1;
		
	}//findFour
	
	//inputs: board, what turn number it is, and what column they want to choose
	private static boolean place(char board[][], int turn, int row){
	
		//if its out of bounds, then return flase
		if(row>6 || row<0){
			return false;
		}
		
		//if full cant place
		if(full(board)){
			return false;
		}
		int i=0;
		
		boolean placed = false;
		
		//look for the top of the column
		while(!placed && i<6){
			if(board[row][i]!='X' && board[row][i]!='O'){
				board[row][i] = (turn%2==0)?'X':'O';
				return true;
			}else{
				i++;
			}
		}
		return false;
	}//place
	
	//inputs: board
	//return: boolean if the board is full or not
	private static boolean full(char board[][]){
		for(int i=0;i<7;i++){
			for(int j=0;j<6;j++){
				//at least one space has not been placed, then not full
				if(board[i][j]!='X' && board[i][j]!='O') return false;
			}
		}
		//if you get to this point, no empty space was found
		return true;
	}//full
	
	//takes in the board
	//outputs the board status to the screen
	//no return
	private static void print(char board[][]){
		//column headers
		System.out.println(" 1 2 3 4 5 6 7 ");
		for(int i=5;i>=0;i--){
			//left border
			System.out.print("|");
			for(int j=0;j<7;j++){
			
				//if its non-empty space print contents
				if(board[j][i]!='X' && board[j][i]!='O'){
					System.out.print(" ");
				}else{
					System.out.print(board[j][i]);
				}
				if(j!=6) System.out.print(" ");
			}
			//right border
			System.out.println("|");
		}
		//print bottom
		System.out.println("---------------");
		
	}//print
	
}//connect4 -- class