import java.util.*;
import java.awt.*;
import java.applet.Applet;


////// Move Manager Class

class Move {

 char board[]     = new char[64];    // internal board
 char rot_board[] = new char[64];    // rotated board
 int val[][]      = new int[76][2];  // internal move values
 int count;                          // move counter
 int last_human;                     // previous human move
 int last_machine;                   // previous machine move
 int rotation;                       // rotation view value
 boolean game_over;                  // true if game is over
 boolean human_won;                  // true if human has won
 boolean machine_won;                // true if machine has won
 boolean no_winner;                  // true if game over and no winner

 final static int weight[] = {
   1, 100, 1000, 90000, 10, 505, 10000 };   // internal weights

 final static int path[][] = {
 {0,16,32,48,56,64,72,-1}, {1,17,32,57,-1,-1,-1,-1}, {2,18,32,58,-1,-1,-1,-1},
 {3,19,32,52,59,65,73,-1}, {4,16,33,49,-1,-1,-1,-1}, {5,17,33,64,-1,-1,-1,-1},
 {6,18,33,65,-1,-1,-1,-1}, {7,19,33,53,-1,-1,-1,-1}, {8,16,34,50,-1,-1,-1,-1},
 {9,17,34,65,-1,-1,-1,-1}, {10,18,34,64,-1,-1,-1,-1},{11,19,34,54,-1,-1,-1,-1},
 {12,16,35,51,60,65,74,-1},{13,17,35,61,-1,-1,-1,-1},{14,18,35,62,-1,-1,-1,-1},
 {15,19,35,55,63,64,75,-1},

 {0,20,36,66,-1,-1,-1,-1}, {1,21,36,48,-1,-1,-1,-1}, {2,22,36,52,-1,-1,-1,-1},
 {3,23,36,67,-1,-1,-1,-1}, {4,20,37,56,-1,-1,-1,-1}, {5,21,37,49,57,66,72,-1},
 {6,22,37,53,58,67,73,-1}, {7,23,37,59,-1,-1,-1,-1}, {8,20,38,60,-1,-1,-1,-1},
 {9,21,38,50,61,67,74,-1}, {10,22,38,54,62,66,75,-1},{11,23,38,63,-1,-1,-1,-1},
 {12,20,39,67,-1,-1,-1,-1},{13,21,39,51,-1,-1,-1,-1},{14,22,39,55,-1,-1,-1,-1},
 {15,23,39,66,-1,-1,-1,-1},

 {0,24,40,68,-1,-1,-1,-1}, {1,25,40,52,-1,-1,-1,-1}, {2,26,40,48,-1,-1,-1,-1},
 {3,27,40,69,-1,-1,-1,-1}, {4,24,41,60,-1,-1,-1,-1}, {5,25,41,53,61,68,75,-1},
 {6,26,41,49,62,69,74,-1}, {7,27,41,63,-1,-1,-1,-1}, {8,24,42,56,-1,-1,-1,-1},
 {9,25,42,54,57,69,73,-1}, {10,26,42,50,58,68,72,-1},{11,27,42,59,-1,-1,-1,-1},
 {12,24,43,69,-1,-1,-1,-1},{13,25,43,55,-1,-1,-1,-1},{14,26,43,51,-1,-1,-1,-1},
 {15,27,43,68,-1,-1,-1,-1},

 {0,28,44,52,60,70,75,-1}, {1,29,44,61,-1,-1,-1,-1}, {2,30,44,62,-1,-1,-1,-1},
 {3,31,44,48,63,71,74,-1}, {4,28,45,53,-1,-1,-1,-1}, {5,29,45,70,-1,-1,-1,-1},
 {6,30,45,71,-1,-1,-1,-1}, {7,31,45,49,-1,-1,-1,-1}, {8,28,46,54,-1,-1,-1,-1},
 {9,29,46,71,-1,-1,-1,-1}, {10,30,46,70,-1,-1,-1,-1},{11,31,46,50,-1,-1,-1,-1},
 {12,28,47,55,56,71,73,-1},{13,29,47,57,-1,-1,-1,-1},{14,30,47,58,-1,-1,-1,-1},
 {15,31,47,51,59,70,72,-1},
 };                                          // weighted paths


//// Move Constructor

 Move() {
  initialize();
 }


//// initialize board variables

 void initialize() {

  int i, row, col;

  count = 0;
  rotation = 1;                     // front view
  game_over = false;
  human_won = false;
  machine_won = false;
  no_winner = false;

  for(row=0; row<76; row++)         // initialize who moved array
    for(col=0; col<2; col++)
      val[row][col] = 0;

  for (i=0; i<64; i++)              // initialize internal move board
    board[i] = '-';

 }


//// Make move

 boolean make_move(int pos) {

  int human_pos, machine_pos;

  human_pos = translate(pos);

  if (check_if_game_over() == true)  return false ;

  if (check_if_legal_move(human_pos) == false)  return false ;

  record_human_move(human_pos);

  if (check_if_human_won(human_pos) == true)  return true ;

  machine_pos = make_machine_move();

  record_machine_move(machine_pos);

  if (check_if_machine_won(machine_pos) == true)  return true ;

  if (check_if_no_winner() == true) return true ;

  return true ;

 }


//// Check If human

 boolean isHuman(int pos) {

 if (rot_board[pos] == 'O')
	return true ;
 else
	return false ;
 }


//// Check If machine

 boolean isMachine(int pos) {

 if (rot_board[pos] == 'X')
  return true ;
 else
  return false ;
 }


//// Check If Legal Move

 boolean check_if_legal_move(int pos) {
 
  if ( board[pos] == '-' )
	return true ;                        // legal human move
  else
	return false ;                       // illegal human move
 }


//// Check if the game is over

 boolean check_if_game_over()
 {
  if ( game_over == true )
	return true ;                          // game is over
  else
   return false ;                         // game is not over
 }


//// Check if there is no winner

 boolean check_if_no_winner()
 {

 if ((count++) == 64) {
  game_over = true;
  no_winner = true;
  return true ; }
 else
  return false ;

 }


//// Is the game over and is there no winner

 boolean is_no_winner()
 {

 if (no_winner == true) 
  return true ; 
 else
  return false ;

 }


//// Check if human won

 boolean check_if_human_won(int pos)
 {
  int maxcnt, cnt, tpath;

  maxcnt = 0;

  for (cnt=0; ((tpath = path[pos][cnt]) >= 0) ; cnt++)

    if ((val[tpath][0] += 1) > maxcnt)
     maxcnt = val[tpath][0];

  if ( maxcnt > 3 ) {
   game_over = true;                                  // human won
   human_won = true;
   return true ; }

  else
   return false ;    

 }


//// Did human win

 boolean is_human_won()
 {

 if (human_won == true)
  return true ;
 else
  return false ;

 }


//// Check if machine won

 boolean check_if_machine_won(int pos)
 {
  int maxcnt, cnt, tpath;

  maxcnt = 0;

  for (cnt=0; ((tpath = path[pos][cnt]) >= 0) ; cnt++)

    if ((val[tpath][1] += 1) > maxcnt)
     maxcnt = val[tpath][1];

  if ( maxcnt > 3 ) {
   game_over = true;                                    // machine won
   machine_won = true;
   return true ; }

  else
   return false ;

 }


//// Did machine win

 boolean is_machine_won()
 {

 if (machine_won == true)
  return true ;
 else
  return false ;

 }


//// Get the last human move

 int get_last_human()
 {
  return(last_human);
 }


//// Get the last machine move

 int get_last_machine()
 {
   return(last_machine);
 }


//// Record human position

 void record_human_move(int human_pos)
 {
   board[human_pos] = 'O';            // record human move
   last_human = human_pos;            // save last human move
 }


//// Record machine position

 void record_machine_move(int machine_pos)
 {
   board[machine_pos] = 'X';           // record machine move
   last_machine = machine_pos;         // save last machine move
 }


//// Make Machine move

 int make_machine_move()
 {

 int randnum;
 int m_pos = 0, here, mv, cnt, tpath, hcnt, mcnt;
 int best = 0;
 int multip = 1;

 for(mv=0;mv<64;mv++)           // machine calculates its best move
  if(board[mv] == '-') {        // logic by Jim Murphy

   here = 0;
   for(cnt=0;cnt<7;cnt++) {     // possible moves
                                // for all paths thru this position
    tpath = path[mv][cnt];
    if (tpath < 0)
     cnt = 7;
    else
    {
    hcnt = val[tpath][0];
    mcnt = val[tpath][1];

    if(hcnt == 0)
      here += weight[mcnt];
    else
      if(mcnt == 0) here += weight[hcnt + 3];
     }

   };   // end for cnt

  if(here > best) {
     multip = 1;
     best = here;
     m_pos = mv;
    }
    else
    {
    if (here == best) {
     multip++;
     randnum = (int)(Math.random()*231);
     if((randnum % multip) == 0) m_pos = mv;
      }
     };    // end here to best
    };     // end if possible

 return(m_pos);                    // return machine move

 }


/// Set rotation view value

 void set_rotation(int view)
 {
  rotation = view;
 }


//// Get rotation value

 int get_rotation() {
   return rotation;
 }


//// Translate external position into internal board position

 int translate(int pos)
 {

 int i=0, j=0, k=0, l, m, n;

 l = 0;
 m = 0;
 n = 63;

 switch (rotation) {

   case 1:                                                // front
           return (pos);

   case 2:                                                // back
           for (i=0 ; i<16; i++) {
            for (j=3 ; j > -1 ; j--) {
              k = n - j ;
              if ( pos == l++ ) return (k) ; }
             n = n - 4 ; }
           return (k);

   case 3:                                                // top
           for (i=3 ; i > -1; i--)
             for (j=0 ; j < 4 ; j++)
              for (k=0 ; k < 4 ; k++)
                if ( pos == m++ ) return ( i + 4*j + k*16 ) ;
            return ( i + 4*j + k*16 ) ;

   case 4:                                                 // bottom
            for (i=0 ; i < 4; i++)
              for (j=0 ; j < 4 ; j++)
               for (k=3 ; k > -1 ; k--)
                if ( pos == m++ ) return ( i + 4*j + k*16 ) ;
             return ( i + 4*j + k*16 ) ;

   case 5:                                                 // left
            for (i=3 ; i > -1; i--)
              for (j=0 ; j < 4 ; j++)
               for (k=0 ; k < 4 ; k++)
                if ( pos == m++ ) return ( k + 4*i + j*16 );
            return ( k + 4*i + j*16 );

   case 6:                                                 // right
            for (i=0 ; i < 4; i++)
              for (j=3 ; j > -1 ; j--)
               for (k=0 ; k < 4 ; k++)
                if ( pos == m++ ) return ( k + 4*i + j*16 );
            return ( k + 4*i + j*16 );

   }  // end switch

   return(0);
 }


//// Rotate view of internal board

 void rotate_board()
 {

 int i=0, j=0, k=0, l, m, n;

  l = 0;
  m = 0;
  n = 63;

 switch (rotation) {
   case 1:                                                // front
           for (i=0 ; i<64; i++)
             rot_board[i] = board[i];
           break;

   case 2:                                                // back
           for (i=0 ; i<16; i++) {
             for (j=3 ; j > -1 ; j--) {
               k = n - j ;
               rot_board[k] = board[l++]; }
             n = n - 4 ; }
            break;

   case 3:                                                // top
            for (i=3 ; i > -1; i--)
              for (j=0 ; j < 4 ; j++)
               for (k=0 ; k < 4 ; k++)
                rot_board[ i + 4*j + k*16 ] = board[m++];
            break;

   case 4:                                                 // bottom
            for (i=0 ; i < 4; i++)
              for (j=0 ; j < 4 ; j++)
               for (k=3 ; k > -1 ; k--)
                rot_board[ i + 4*j + k*16 ] = board[m++];
            break;

case 5:                                                 // left
            for (i=3 ; i > -1; i--)
              for (j=0 ; j < 4 ; j++)
               for (k=0 ; k < 4 ; k++)
                rot_board[ k + 4*i + j*16 ] = board[m++];
            break;

   case 6:                                                 // right
            for (i=0 ; i < 4; i++)
              for (j=3 ; j > -1 ; j--)
               for (k=0 ; k < 4 ; k++)
                rot_board[ k + 4*i + j*16 ] = board[m++];
            break;


  }  // end switch

 }


}  //// end class Move


////// GUI Class


class GUI extends Panel implements Runnable {

 final static int NUMBER = 64;     // number of squares

 TTT ttt;                         // this applet class
 Move move;                       // move manager class
 Thread doit;
 Point points[]      = new Point[NUMBER];
 Rectangle regions[] = new Rectangle[NUMBER];
 String message;

 final static int xy_posit[][] = {
 {20,20}, {20,120}, {20,220}, {20,320}, {120,20},{120,120},{120,220},{120,320},
 {220,20},{220,120},{220,220},{220,320},{320,20},{320,120},{320,220},{320,320},
 {45,40}, {45,140}, {45,240}, {45,340}, {145,40},{145,140},{145,240},{145,340},
 {245,40},{245,140},{245,240},{245,340},{345,40},{345,140},{345,240},{345,340},
 {70,60}, {70,160}, {70,260}, {70,360}, {170,60},{170,160},{170,260},{170,360},
 {270,60},{270,160},{270,260},{270,360},{370,60},{370,160},{370,260},{370,360},
 {95,80}, {95,180}, {95,280}, {95,380}, {195,80},{195,180},{195,280},{195,380},
 {295,80},{295,180},{295,280},{295,380},{395,80},{395,180},{395,280},{395,380},
  };


//// GUI Constructor

 GUI(TTT ttt) {

   super();            // call Panel constructor
   this.ttt = ttt;

   move = new Move();

   message = new String("                 YOUR MOVE  ");

   for (int i = 0; i<16; i++) {
     points[i]  = new Point(xy_posit[i][0], xy_posit[i][1]);
     regions[i] = new Rectangle(points[i].x - 10, points[i].y - 10, 21, 21);
     }

   for (int i = 16; i<32; i++) {
     points[i]  = new Point(xy_posit[i][0], xy_posit[i][1]);
     regions[i] = new Rectangle(points[i].x - 9, points[i].y - 9, 19, 19);
     }

   for (int i = 32; i<48; i++) {
     points[i]  = new Point(xy_posit[i][0], xy_posit[i][1]);
     regions[i] = new Rectangle(points[i].x - 8, points[i].y - 8, 17, 17);
     }

   for (int i = 48; i<64; i++) {
     points[i]  = new Point(xy_posit[i][0], xy_posit[i][1]);
     regions[i] = new Rectangle(points[i].x - 7, points[i].y - 7, 15, 15);
     }

 }


 public void run() {
   repaint();
 }


 public synchronized boolean mouseUp(Event evt, int x, int y) {

   if (move.get_rotation() != 1) return true;      // check for valid view

   for (int i = 0; i<points.length; i++) {

     if (regions[i].inside(x, y)) {                // check for valid click 
       if (move.make_move(i)) {
         repaint();
         if (move.is_human_won())   message = "     GAME OVER, HUMAN WON ";
         if (move.is_machine_won()) message = "     GAME OVER, COMPUTER WON ";
         if (move.is_no_winner())   message = "     GAME OVER, NO WINNER";
        return true;
       }
      }

    }  // end for

   return true;
 }


 public void start() {
   doit = new Thread(this);
   doit.start();
 }


 public void stop() {
   doit.stop();
 }


//// Paint Method

 public void paint(Graphics g) {

  // draw grid  - ugly, but fast ...

  g.setColor(Color.gray);

  // level one outer box
  g.drawLine(points[0].x,  points[0].y,  points[3].x,  points[3].y);
  g.drawLine(points[3].x,  points[3].y,  points[15].x, points[15].y);
  g.drawLine(points[15].x, points[15].y, points[12].x, points[12].y);
  g.drawLine(points[12].x, points[12].y, points[0].x,  points[0].y);

  // level two outer box
  g.drawLine(points[16].x, points[16].y, points[19].x, points[19].y);
  g.drawLine(points[19].x, points[19].y, points[31].x, points[31].y);
  g.drawLine(points[31].x, points[31].y, points[28].x, points[28].y);
  g.drawLine(points[28].x, points[28].y, points[16].x, points[16].y);

  // level three outer box
  g.drawLine(points[32].x, points[32].y, points[35].x, points[35].y);
  g.drawLine(points[35].x, points[35].y, points[47].x, points[47].y);
  g.drawLine(points[47].x, points[47].y, points[44].x, points[44].y);
  g.drawLine(points[44].x, points[44].y, points[32].x, points[32].y);

  // level four outer box
  g.drawLine(points[48].x, points[48].y, points[51].x, points[51].y);
  g.drawLine(points[51].x, points[51].y, points[63].x, points[63].y);
  g.drawLine(points[63].x, points[63].y, points[60].x, points[60].y);
  g.drawLine(points[60].x, points[60].y, points[48].x, points[48].y);

  // level one inner lines
  g.drawLine(points[1].x, points[1].y, points[13].x, points[13].y);
  g.drawLine(points[14].x, points[14].y, points[2].x, points[2].y);
  g.drawLine(points[4].x, points[4].y, points[7].x, points[7].y);
  g.drawLine(points[11].x, points[11].y, points[8].x, points[8].y);

  // level two inner lines
  g.drawLine(points[17].x, points[17].y, points[29].x, points[29].y);
  g.drawLine(points[30].x, points[30].y, points[18].x, points[18].y);
  g.drawLine(points[20].x, points[20].y, points[23].x, points[23].y);
  g.drawLine(points[27].x, points[27].y, points[24].x, points[24].y);

  // level three inner lines
  g.drawLine(points[33].x, points[33].y, points[45].x, points[45].y);
  g.drawLine(points[46].x, points[46].y, points[34].x, points[34].y);
  g.drawLine(points[36].x, points[36].y, points[39].x, points[39].y);
  g.drawLine(points[43].x, points[43].y, points[40].x, points[40].y);

  // level four inner lines
  g.drawLine(points[49].x, points[49].y, points[61].x, points[61].y);
  g.drawLine(points[62].x, points[62].y, points[50].x, points[50].y);
  g.drawLine(points[52].x, points[52].y, points[55].x, points[55].y);
  g.drawLine(points[59].x, points[59].y, points[56].x, points[56].y);

  // diagnal lines
  g.drawLine(points[0].x, points[0].y, points[48].x, points[48].y);
  g.drawLine(points[1].x, points[1].y, points[49].x, points[49].y);
  g.drawLine(points[2].x, points[2].y, points[50].x, points[50].y);
  g.drawLine(points[3].x, points[3].y, points[51].x, points[51].y);
  g.drawLine(points[4].x, points[4].y, points[52].x, points[52].y);
  g.drawLine(points[5].x, points[5].y, points[53].x, points[53].y);
  g.drawLine(points[6].x, points[6].y, points[54].x, points[54].y);
  g.drawLine(points[7].x, points[7].y, points[55].x, points[55].y);
  g.drawLine(points[8].x, points[8].y, points[56].x, points[56].y);
  g.drawLine(points[9].x, points[9].y, points[57].x, points[57].y);
  g.drawLine(points[10].x, points[10].y, points[58].x, points[58].y);
  g.drawLine(points[11].x, points[11].y, points[59].x, points[59].y);
  g.drawLine(points[12].x, points[12].y, points[60].x, points[60].y);
  g.drawLine(points[13].x, points[13].y, points[61].x, points[61].y);
  g.drawLine(points[14].x, points[14].y, points[62].x, points[62].y);
  g.drawLine(points[15].x, points[15].y, points[63].x, points[63].y);


  // paint rectangles on GUI board

  move.rotate_board(); 

  for (int i = 0; i<points.length; i++) {
     g.setColor(Color.gray);
     if (move.isHuman(i))   g.setColor(Color.cyan.darker());
     if (move.isMachine(i)) g.setColor(Color.red.darker());
     g.fillOval(regions[i].x, regions[i].y,
                regions[i].width, regions[i].height); 
     }

  // display current status

  g.setColor(Color.blue.darker());
  g.drawString(message , 100, 425);

 }


 void new_game() {

   move.initialize();           // reset private date members
   move.set_rotation(1);        // reset to front view
   message = "                 YOUR MOVE  ";
   repaint();                   // redraw GUI
 }


 void set_view(int view) {

   move.set_rotation(view);      // set new view

   if (move.is_human_won()) {
     repaint(); 
     return;
     }

   if (move.is_machine_won()) {
     repaint(); 
     return;
     }

   if (view == 1) message = "                 YOUR MOVE  ";
   if (view != 1) message = "USE FRONT VIEW TO MAKE YOUR MOVE";

   repaint();                    // redraw GUI
 }


}   //// end class GUI


////// The TTT Applet Class


public class TTT extends Applet {

 GUI   gui;
 Panel bottom_row;
 Choice choice;


 public void init() {
   setLayout(new BorderLayout());

   gui = new GUI(this);
   add("Center", gui);

   bottom_row = new Panel();
   add("South", bottom_row);

   bottom_row.add(new Button("NEW GAME"));
   bottom_row.add(new Label("           CURRENT VIEW:"));

   choice = new Choice();

   choice.addItem("FRONT");
   choice.addItem("BACK");
   choice.addItem("TOP");
   choice.addItem("BOTTOM");
   choice.addItem("LEFT");
   choice.addItem("RIGHT");

   bottom_row.add(choice);

 }


 public void start() {
   gui.start();
 }


 public void stop() {
   gui.stop();
 }


 public boolean action(Event e, Object arg) {

   if ("NEW GAME".equals(arg)) {
     gui.new_game();
     choice.select(0);
     return true;
    }

   if (e.target instanceof Choice) {
     gui.set_view(choice.getSelectedIndex()+1);
     return true;
    }

   return false;
 }


}   //// end class TTT


//// end applet