import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;

class OthelloBoardTest {
	public static void main(String args[]) {
		OthelloBoard ob = new OthelloBoard();
		ob.start();
	}
}

class OthelloBoard {
	private int size;				//One side of the Othello board(8, 10, 12, 14, 16)
	private char[][] squares;		//State of each square(B:black, W:White, N:No stone)
	private int turnCount;			//Count the number of turns
	private int turnCountMax;		//Maximum number of turns(1 side*1 side-4)
	private char playerColor;		//Player stone color
	private char otherColor;		//The color of the opponent's stone
	private int playerDiscNum;		//Number of player stones
	private int otherDiscNum;		//Number of opponent's stones
	private final String alphabets = "abcdefghijklmnop";
									//Alphabet showing horizontal coordinates

	//constructor
	public OthelloBoard() {
		this.size = 8;
//		this.size = askBoardSize();
		this.squares = new char[this.size][this.size];
		this.turnCount = 1;
		this.turnCountMax = this.size*this.size - 4;

		//Put the Othello board in the state immediately after the start
		this.initializeBoard();
	}

	//Start Othello
	public void start() {
		//Processing before start
		this.askPlayerColor();
		boolean isPlayerTurn = this.getFirstMove();
		int skipCount = 0;
		//Processing of each turn
		System.out.println("Start Othello.");
		this.printBoard();
		while (this.turnCount <= turnCountMax) {
			//Determine if to skip the turn
			int skipFlag = this.checkSkipCount(isPlayerTurn, skipCount);
			if (skipFlag == 2) {
				break;
			} else if (skipFlag == 1) {
				isPlayerTurn = !isPlayerTurn;
				skipCount ++;
				continue;
			}
			//When not skipping
			skipCount = 0;
			if (isPlayerTurn) {
				//Player turn
				System.out.println("\nTurn " + turnCount + ":It's your turn.");
				this.askNewCoordinates(this.playerColor, this.otherColor);
			} else {
				//Opponent's turn
				System.out.println("\nTurn " + turnCount + ":It's your opponent's turn.");
				this.thinkNewCoordinates(this.otherColor, this.playerColor);
			}
			this.printBoard();
			//Processing for the next turn
			this.turnCount ++;
			isPlayerTurn = !isPlayerTurn;
		}
		//Judgment of victory or defeat
		this.printDiscNumber();
		this.printResult();
	}

	//Automatically narrow down where to put the next stone
	private void thinkNewCoordinates(char myColor, char enemyColor) {
		ArrayList<Candidate> candidates = new ArrayList<Candidate>();
	
		//Store a list of places where you can place stones first
		for (int y = 0; y < this.size; y ++) {
			for (int x = 0; x < this.size; x ++) {
				//Ignore subsequent processing if other stones are placed
				if (this.squares[y][x] != 'N') {
					continue;
				}
				//If the opponent's stone cannot be turned over, the subsequent processing will be ignored.
				Coordinates newDisc = new Coordinates(x, y);
				ArrayList<Coordinates> discs = this.checkDiscsTurnedOverAllLine(
					myColor, enemyColor, newDisc, this.size*this.size);
				if (discs.isEmpty()) {
					continue;
				}
				//Register in the candidate list
				candidates.add(new Candidate(newDisc));
			}
		}
	
		//Randomly choose one from each candidate
		Coordinates newDisc = candidates.get(new Random().nextInt(candidates.size()));
		ArrayList<Coordinates> discs = this.checkDiscsTurnedOverAllLine(
			myColor, enemyColor, newDisc, this.size*this.size);
		this.putDisc(myColor, newDisc);
		this.turnOverDiscs(discs);
		this.printDiscsTurnedOver(discs);
	}

	//Determine if to skip the turn
	//0 if skipping is not required, 1 if skipping is required and the previous turn was not skipped,
	//Returns 2 if skipping is required and the previous turn was also skipped
	private int checkSkipCount(boolean isPlayerTurn, int skipCount) {
		char myColor;
		char enemyColor;
		int result = 0;

		if (isPlayerTurn) {
			myColor = this.playerColor;
			enemyColor = this.otherColor;
		} else {
			myColor = this.otherColor;
			enemyColor = this.playerColor;
		}
		if (! this.checkSquaresForNewDisc(myColor, enemyColor)) {
			//Skip player's turn
			System.out.println("The turn was skipped.");
			result = 1;
			if (skipCount == 1) {
				//If the opponent's turn has already been skipped, the game ends
				result = 2;
			}
		}
		return result;
	}

	//The first move decides which one
	//If the player is Kuroishi, the player is on the play, and if the player is Shiraishi, the opponent is on the play.
	private boolean getFirstMove() {
		if (this.playerColor == 'B') {
			return true;
		} else {
			return false;
		}

	}

	//Turn the stone over
	private void turnOverDiscs(ArrayList<Coordinates> discs) {
		for (int i = 0; i < discs.size(); i ++) {
			int x = discs.get(i).x;
			int y = discs.get(i).y;
			if (this.squares[y][x] == 'B') {
				this.squares[y][x] = 'W';
			} else if (this.squares[y][x] == 'W') {
				this.squares[y][x] = 'B';
			}
		}
	}

	//Place to put stones(A place where you can turn over other stones)Determine if there is
	private boolean checkSquaresForNewDisc(char myColor, char enemyColor) {
		for (int y = 0; y < this.size; y ++) {
			for (int x = 0; x < this.size; x ++) {
				if (this.squares[y][x] != 'N') {
					continue;
				}
				ArrayList<Coordinates> discs = this.checkDiscsTurnedOverAllLine(
						myColor, enemyColor, new Coordinates(x, y), 1);
				if (discs.size() >= 1) {
					return true;
				}
			}
		}
		return false;
	}

	//Accept input until you decide where to put the stone
	private void askNewCoordinates(char myColor, char enemyColor) {
		while (true) {
			//input
			System.out.println("\n Decide where to put the stone.");
			System.out.println("[x coordinate y coordinate](Examplea1)：");
			Scanner sc = new Scanner(System.in);
			//Determine if it is within the range of the Othello board
			Coordinates newDisc = this.checkCoordinatesRange(sc.nextLine());
			if (newDisc.equals(-1, -1)) {
				//If the coordinates are incorrect, re-enter
				System.out.println("The input is incorrect.");
				continue;
			}
			if (this.squares[newDisc.y][newDisc.x] != 'N') {
				//If a stone has already been placed, have it entered again
				System.out.println("There are already stones.");
				continue;
			}
			//Determine if the opponent's stone can be turned over
			ArrayList<Coordinates> discs = this.checkDiscsTurnedOverAllLine(
				myColor, enemyColor, newDisc, this.size*this.size);
			if (! discs.isEmpty()) {
				//If there is a stone that can be turned over, actually turn it over
				this.putDisc(myColor, newDisc);
				this.turnOverDiscs(discs);
				this.printDiscsTurnedOver(discs);
				return;
			}
			System.out.println("I can't turn over the opponent's stone.");
		}
	}

	//Determine if the coordinates entered by the player are within the range of the Othello board
	//If the judgment succeeds, the coordinates are used, and if the judgment fails, the coordinates are used.(-1, -1)return it
	private Coordinates checkCoordinatesRange(String line) {
		String[] tokens = line.split(" ");
		//Read the horizontal coordinates from the first letter of the alphabet
		int x = this.alphabets.indexOf(tokens[0]);
		if (tokens[0].length() != 1 || x < 0 || this.size <= x) {
			return new Coordinates(-1, -1);
		}
		//Read the vertical coordinates from the remaining characters
		int y;
		try {
			y = Integer.parseInt(tokens[1]);
			if (y <= 0 || this.size < y) {
				return new Coordinates(-1, -1);
			}
		} catch (NumberFormatException e) {
			return new Coordinates(-1, -1);
		}
		return new Coordinates(x, y - 1);
	}

	//Determine if the stone at the entered coordinates can turn over the opponent's stone
	//Returns the coordinates of the stone that can be turned over as an Arraylist
	//Since the maximum value of the number that can be turned over can be determined by the argument countMax,
	//If you just want to judge whether you can put a stone at that coordinate, 1 is enough
	//Size to return all the coordinates of a stone that can be flipped*to size
	private ArrayList<Coordinates> checkDiscsTurnedOverAllLine(
		char myColor, char enemyColor, Coordinates myCoordinates, int countMax)
	{
		ArrayList<Coordinates> discs = new ArrayList<Coordinates>();
		//Scan in each direction
		for (int d = 0; d < 8; d ++) {
			discs.addAll(this.checkDiscsTurnedOverOneLine(myColor, enemyColor, myCoordinates, d));
			//If the maximum value of the stone that can be turned over is exceeded, the processing will be stopped.
			if (discs.size() > countMax) {
				break;
			}
		}
		return discs;
	}

	//Determine if the stone at the entered coordinates can turn over the opponent's stone
	//The scanning direction changes depending on the argument direction.
	// 0:0 degrees, 1:45 degrees, 2:90 degrees, 3:135 degrees, 4:180 degrees, 5:225 degrees, 6:270 degrees, 7:315 degrees
	private ArrayList<Coordinates> checkDiscsTurnedOverOneLine(
		char myColor, char enemyColor, Coordinates myCoordinates, int direction)
	{
		//Scan a stone that can be turned over
		Coordinates currentCoordinates = new Coordinates(myCoordinates);
		ArrayList<Coordinates> discs = new ArrayList<Coordinates>();
		//Keep scanning next to you while your opponent's stones continue
		while (true) {
			//Find the coordinates of the next stone
			Coordinates nextDisc = this.getNextDiscCoordinates(currentCoordinates, direction);
			if (nextDisc.equals(-1, -1)) {
				//Returns an empty list if there are no stones to flip
				discs.clear();
				break;
			}
			if (this.squares[nextDisc.y][nextDisc.x] == enemyColor) {
				//If there is an opponent's stone next to you, temporarily register it in the flip list
				discs.add(nextDisc);
			} else if (this.squares[nextDisc.y][nextDisc.x] == myColor) {
				//If you have your own stone next to it, return the list
				break;
			} else {
				//Returns an empty list if there are no stones next to it
				discs.clear();
				break;
			}
			//Proceed to the next stone
			currentCoordinates.copy(nextDisc);
		}
		return discs;
	}

	//next to(Depends on the direction)Returns the coordinates of the stone in
	//If the coordinates are out of range(-1, -1)return it
	private Coordinates getNextDiscCoordinates(Coordinates myDisc, int direction) {
		//x coordinate
		int x = myDisc.x;
		if (direction == 0 || direction == 1 || direction == 7) {
			x ++; //0 degrees,45 degrees,315 degrees
		} else if (direction == 3 || direction == 4 || direction == 5) {
			x --;  //135 degrees,180 degrees,225 degrees
		}
		//y coordinate
		int y = myDisc.y;
		if (direction == 1 || direction == 2 || direction == 3) {
			y --; //45 degrees,90 degree,135 degrees
		} else if (direction == 5 || direction == 6 || direction == 7) {
			y ++;  //225 degrees,270 degrees,315 degrees
		}
		if (x < 0 || this.size <= x || y < 0 || this.size <= y) {
			//When the coordinates are out of range
			return new Coordinates(-1, -1);
		}
		return new Coordinates(x, y);
	}

	//Accepts input until the size of the Othello board is decided
	//This method is the constructor of this.If you paste it on the right side of size,
	//You can add a process to enter the size of the Othello board
	private int askBoardSize() {
		while (true) {
			System.out.println("");
			System.out.println("Please decide the length of one side of the Othello board.");
			System.out.print("[8, 10, 12, 14,Any of 16]：");
			Scanner sc = new Scanner(System.in);
			String line = sc.nextLine();
			if ("8".equals(line) || "10".equals(line) || "12".equals(line) ||
				"14".equals(line) || "16".equals(line)) {
				System.out.println("The length of one side of the Othello board is" + line + "is.");
				return Integer.parseInt(line);
			}
			System.out.println("The input is incorrect.");
		}
	}

	//Accept input until the color of the player's stone is decided
	private void askPlayerColor() {
		while (true) {
			System.out.println("\n Decide on your stone.");
			System.out.println("[b (black), w (White)Any of]：");
			Scanner sc = new Scanner(System.in);
			String line = sc.nextLine();
			if ("b".equals(line)) {
				System.out.println("Your stone is black.");
				this.playerColor = 'B';
				this.otherColor = 'W';
				return;
			} else if ("w".equals(line)) {
				System.out.println("Your stone is white.");
				this.playerColor = 'W';
				this.otherColor = 'B';
				return;
			}
			System.out.println("The input is incorrect.");
		}
	}

	//Show the outcome of the game
	private void printResult() {
		if (playerDiscNum > otherDiscNum) {
			System.out.println("You win.");
		} else if (playerDiscNum == otherDiscNum) {
			System.out.println("It's a draw.");
		} else {
			System.out.println("You lose.");
		}
	}

	//Show the number of stones of the player and opponent
	private void printDiscNumber() {
		this.playerDiscNum = this.countDisc(this.playerColor);
		this.otherDiscNum = this.countDisc(this.otherColor);
		System.out.print("you= " + playerDiscNum + "  ");
		System.out.println("Opponent= " + otherDiscNum);
	}

	//Count stones of the specified color
	private int countDisc(char myColor) {
		int count = 0;
		for (int y = 0; y < this.size; y ++) {
			for (int x = 0; x < this.size; x ++) {
				if (this.squares[y][x] == myColor) {
					count ++;
				}
			}
		}
		return count;
	}

	//Put the Othello board in the state immediately after the start
	private void initializeBoard() {
		for (int y = 0; y < this.size; y ++) {
			for (int x = 0; x < this.size; x ++) {
				squares[y][x] = 'N';
			}
		}
		//Place stones only in the central 4 squares
		this.putDisc('B', this.size/2 - 1, this.size/2 - 1);
		this.putDisc('B', this.size/2, this.size/2);
		this.putDisc('W', this.size/2, this.size/2 - 1);
		this.putDisc('W', this.size/2 - 1, this.size/2);
	}

	//Place a stone at the specified coordinates on the Othello board
	private void putDisc(char discColor, int x, int y) {
		this.squares[y][x] = discColor;
	}
	private void putDisc(char discColor, Coordinates c) {
		this.putDisc(discColor, c.x, c.y);
	}

	//Show all coordinates of flipped stones
	private void printDiscsTurnedOver(ArrayList<Coordinates> discs) {
		System.out.println("I flipped the next stone.");
		int count = 0;
		for (int i = 0; i < discs.size(); i ++) {
			System.out.print(this.alphabets.substring(discs.get(i).x, discs.get(i).x + 1) +
				(discs.get(i).y + 1) + " ");
			count ++;
			if (count == 8) {
				System.out.println("");
				count = 0;
			}
		}
		System.out.println("");
	}

	//Display the Othello board on the console
	private void printBoard() {
		this.printBoardAlphabetLine();					//Alphabet line
		this.printBoardOtherLine("┏", "┳", "┓");		//Top edge
		for (int y = 0; y < this.size - 1; y ++) {
			this.printBoardDiscLine(y);					//Line to display stones
			this.printBoardOtherLine("┣", "╋", "┫");	//Line spacing
		}
		this.printBoardDiscLine(this.size - 1);			//Line to display stones
		this.printBoardOtherLine("┗", "┻", "┛");		//lower end
	}

	//Display the alphabet indicating the row of Othello board
	private void printBoardAlphabetLine() {
		String buf = "  ";
		for (int x = 0; x < this.size; x ++) {
			buf += "   " + this.alphabets.charAt(x);
		}
		System.out.println(buf);
	}

	//Display one line with stones on the Othello board
	private void printBoardDiscLine(int y) {
		String buf = String.format("%2d┃", y+1);
		for (int x = 0; x < this.size; x ++) {
			if (this.squares[y][x] == 'B') {
				buf += "●┃";
			} else if (this.squares[y][x] == 'W') {
				buf += "○┃";
			} else {
				buf += "　┃";
			}
		}
		System.out.println(buf);
	}

	//Display one line of ruled lines representing the frame of the Othello board
	private void printBoardOtherLine(String left, String middle, String right) {
		String buf = "  " + left;
		for (int x = 0; x < this.size - 1; x ++) {
			buf += "━" + middle;
		}
		System.out.println(buf + "━" + right);
	}
}

class Candidate extends Coordinates {
	public int priority;

	public Candidate(Coordinates c) {
		super(c);
	}
}

class Coordinates {
	public int x;
	public int y;

	Coordinates(int x, int y)  {
		this.x = x;
		this.y = y;
	}

	Coordinates(Coordinates c)  {
		this.x = c.x;
		this.y = c.y;
	}

	public void copy(Coordinates c) {
		this.x = c.x;
		this.y = c.y;
	}

	public boolean equals(int x, int y) {
		if (this.x == x && this.y == y) {
			return true;
		} else {
			return false;
		}
	}
}