import java.io.*;

interface TTTConstants {
  static final int N = 3;
  static final int SIZE = N*N;
  static final byte BLANK = 0;
  static final byte X = 1;
  static final byte O = -X;
}

interface TTTGameI {
  void move(int i, int j);  
  //  place next player's symbol in square[i,j] and update game state

  void move(int k);         
  //  same as above where k = i*N + j

  int winner();  
  // determine is if either player has won the game; returns BLANK, X,  or O

  int bestMove();
  // determines best move available for next player

  boolean gameOver();
  // returns true if game is over
}

interface Listener {
  // Listener interface for simulated buttons
  void actionPerformed(int move);
  boolean gameOver();  // not found in an AWT button
}

class IllegalMoveException extends RuntimeException {
  IllegalMoveException(String s) { super("Illegal move: " + s); }
}

class TTTGame implements TTTGameI, Cloneable, /*imports*/ TTTConstants {
  public byte[] squares;
  public int numOfMoves;
  public byte next = X;

  TTTGame() {
    // create an empty board
    squares = new byte[SIZE];
    // default byte value is BLANK
    numOfMoves = 0;
  }

  TTTGame(TTTGame s) {
    // clone an existing board
    squares = new byte[SIZE];
    System.arraycopy(s.squares,0,squares,0,SIZE);
    numOfMoves = s.numOfMoves;
    next = s.next;
  }

  public void move(int i, int j) {
    move(index(i,j));
  }

  public void move(int k) {
    if (numOfMoves == SIZE) throw new IllegalMoveException(
      "board is full implying that the game is over");
    if (squares[k] != BLANK) 
      throw new IllegalMoveException(
       "square [" + k/N + "," + k%N + "] occupied");
    squares[k] = next;
    next = opposite(next);  
    numOfMoves++;
  }

  public int winner() {
    // not parameterized with respect to N, SIZE
    // returns X if X has won the game
    //         O (capital O) if O has won the game
    //         BLANK otherwise

    byte bl = BLANK;
    if (squares[index(0,0)] != bl) {
      if ((squares[index(0,1)] == squares[index(0,0)] &&
	   squares[index(0,2)] == squares[index(0,0)])    ||
	  (squares[index(1,0)] == squares[index(0,0)] &&
	   squares[index(2,0)] == squares[index(0,0)]))    
	return squares[index(0,0)];
    }
    if (squares[index(2,2)] != bl) {	  
      if ((squares[index(2,1)] == squares[index(2,2)] &&
	   squares[index(2,0)] == squares[index(2,2)])    ||
	  (squares[index(1,2)] == squares[index(2,2)] &&
	   squares[index(0,2)] == squares[index(2,2)]))
	return squares[index(2,2)];
    }
    if (squares[index(1,1)] != bl) {	  
      if ((squares[index(0,0)] == squares[index(1,1)] &&
	   squares[index(2,2)] == squares[index(1,1)])    ||
	  (squares[index(0,2)] == squares[index(1,1)] &&
	   squares[index(2,0)] == squares[index(1,1)])    ||
	  (squares[index(0,1)] == squares[index(1,1)] &&
	   squares[index(2,1)] == squares[index(1,1)])    ||
	  (squares[index(1,0)] == squares[index(1,1)] &&
	   squares[index(1,2)] == squares[index(1,1)]))
	return squares[index(1,1)];
    }
    return bl;
  }


  public int bestMove() {
    if (numOfMoves == SIZE) throw new RuntimeException("No move is possible");
    int bestValue = next == X ? -1 : 1;
    int bestMove = -1;

    for (int i = 0; i < SIZE; i++)
      if (squares[i] == BLANK) {
	// i is legal move
	TTTGame b = new TTTGame(this);
	b.move(i);
	int value = b.eval();
	if (next == X) {
	  if (value > bestValue) {
	    bestMove = i;
	    bestValue = value;
	  }
	}
	else
	  if (value < bestValue) {
	    bestMove = i;
	    bestValue = value;
	  }
      }
    return bestMove;
  }

  private int eval() {

    // provided as support for writing bestMove()
    // returns X (+1) if X can force a win
    //         O (-1) if O can force a win
    //         0 otherwise

    // analysis determines outcome assuming that each player chooses best
    // possible move
    //   X chooses move with largest possible value
    //   O chooses move with smallest possible value

    int win = winner();
    if (win != 0 || numOfMoves == SIZE) return win;

    int bestValue = next == X ? -1 : 1;

    for (int i = 0; i < SIZE; i++)
      if (squares[i] == BLANK) {
	// i is legal move
	TTTGame b = new TTTGame(this);
	b.move(i);
	int value = b.eval();
	if (next == X) {
	  if (value > bestValue) {
	    bestValue = value;
	  }
	}
	else
	  if (value < bestValue) {
	    bestValue = value;
	  }
      }
    return bestValue;
  }

  public boolean gameOver() { return numOfMoves >= SIZE || winner() != 0; }

  public String toString() {
    StringBuffer result = new StringBuffer();

    result.append("+-+-+-+\n");
    for (int i = 0; i < N; i++) {
      result.append("|");
      for (int j = 0; j < N; j++) {
	byte sq = squares[index(i,j)];
	result.append( sq == X ? "X|" :
		       sq == O ? "O|" :
		       " |");
      }
      result.append("\n");
      result.append("+-+-+-+\n");
    }
    return result.toString();
  }

  static int index(int i, int j) { return i*N + j; }

  static byte opposite(byte player) { return player == X ? O : X; }

}


public class TTTControl implements /* imports */ TTTConstants{
  
  private OSLayer myOS;  //  TTTControl is not a subclass of the applet
                         //  interface simulated by OSLayer; hence,
                         //  the init call must pass this information.
                         //  Unnecessary in GUI version

  private TTTGame game;
  private TTTView dView;

  public void init(OSLayer oS) {
    myOS = oS;
    game = new TTTGame();
    dView = new TTTView(myOS);

      dView.addListener(new Listener(){ // ANONYMOUS CLASS
      public void actionPerformed(int move) {

	// move is valid because the event loop checks this;
        // in the GUI View, disabling the buttons for occupied squares 
	// ensures that only valid moves (button actions) will be  
        // received

	// System.err.println("Listener called with move value " + move);
	dView.setSquare(move,"X");
	dView.disableSquare(move);
	game.move(move);
	System.err.println("You made move " + move);
	if (!game.gameOver()) {
	  int k = game.bestMove();
	  System.err.println("My response is " + k);
	  game.move(k);
	  dView.setSquare(k,"O");
	  dView.disableSquare(k);
	}

        // You should attach a separate listener to each button in your 
	// GUI view.  Each anonymous class can refer to a final local
        // variable containing the button index.

	if (game.numOfMoves == SIZE || game.winner() != 0) {
	  int winner = game.winner();
	  String result = (winner == 1) ? "You won." :
                          (winner == -1) ? "I won." : "It was a draw.";

          // the GUI view can include a label that is updated to dislay
          //   game status including game complteion and the winner

	  System.out.println("Game Over. " + result);
	}
      }
      public boolean gameOver() { return game.gameOver(); }
      });
  } 
}

class TTTView implements /*imports*/ TTTConstants {

  // the GUI view is automatically updated by method invocations that
  // modify its components, but our simulation must print it our

  // the actual view will contain panels containing buttons and some labels

  public String[] squares = new String[9];
  OSLayer myApplet;

  public TTTView(OSLayer oS) {

  // oS simluates the OS interface provided the enclosing applet
  // that the View interacts with 

    myApplet = oS;
    for (int i = 0; i < 9; i++) squares[i] = " ";

    // print banner
    System.out.println("Play Tic Tac Toe");
    System.out.println(this);
    System.out.println("\nSelect any square index in the range 0-8\n");
  }    

  void addListener(Listener l) {
    myApplet.addListener(l);
  }

  void setSquare(int i, String val) { 
    squares[i] = val; 
    System.out.println(this);
  }

  void disableSquare(int i) { myApplet.disable(i); }

  public String toString() {
    StringBuffer result = new StringBuffer();

    result.append("+-+-+-+\n");
    for (int i = 0; i < N; i++) {
      result.append("|");
      for (int j = 0; j < N; j++) result.append(squares[index(i,j)] + "|");
      result.append("\n");
      result.append("+-+-+-+\n");
    }
    return result.toString();
  }

  static int index(int i, int j) { return i*N + j; }

}

class OSLayer implements /*imports*/ TTTConstants {

  // simulates OSLayer including AWT event loop thread and user program thread

  Listener moveListen; // listener at event loop level
  boolean[] disabled;  // records status of simulated buttons

  OSLayer() {
    disabled = new boolean[SIZE];
    for (int i = 0; i < SIZE; i++) disabled[i] = false;
  }

  void addListener(Listener m) { moveListen = m; } 
  // only accommodates one listener; a true event loop
  // would accommodate many; these listeners are passed
  // down to the event loop thread by AWT components

  // AWT components must pass down status information about button diabling 
  //    to OS level code (mouse tracking code, etc.) 

  void disable(int i) { disabled[i] = true; }

  static StreamTokenizer in = new StreamTokenizer(
    new BufferedReader(new InputStreamReader(System.in)));

  public void eventLoop() {

    int move = -1;  // invalid value in case of IOException

    // event loop processes event (simulated button pushes) until
    // the game is over; in AWT even loop does not stop until the
    // JVM or applet shuts down
   
    do {

      System.out.println("What is your move[a number 0-8]?");
      // message makes tty interface more tolerable; it has no analog in
      //     AWT event loop
      

      // get next move  
      do {
	try {
	  int token = in.nextToken();
	  while ((token != in.TT_NUMBER)) token = in.nextToken();
	  move = (int) in.nval;
	  System.err.println("move = " + move);
	}       
	catch(IOException e) { 
        System.out.println("I/O Exception!");
        continue; 
	}  // restart loop on IOException
      }
      while ((move < 0) || (move > 8) || disabled[move]);
      
      moveListen.actionPerformed(move);  // invoke listener on the move

    } while (! moveListen.gameOver());
  }

  public static void main(String[] args) { 
    
    OSLayer os = new OSLayer();
    TTTControl ttc = new TTTControl();  

    // execute ttc.init(os); requires a separate thread in general, but
    //   not here since ttc.init(os) quickly terminates after setting
    //   up the View, the Game, and installing listeners
    ttc.init(os);

    // run the event loop thread
    os.eventLoop();
  }
}