/* Sample code for assignment 2 question 3 */
/* The sample code has everything for the game rules, but nothing for AI */

#include <iostream>
#include <string>
using namespace std;

static const char MIN_PLAYER = -1, EMPTY_CELL = 0, MAX_PLAYER = 1;
static const char MIN_PLAYER_CHAR = 'X',
  EMPTY_CELL_CHAR = '.', MAX_PLAYER_CHAR = 'O';

struct game_config_t {
  /* The board representation */
  char board[8][8];
  char next_to_move;
  /* Defined to be char instead of bool to save space */
  char last_move_is_pass;

  /* Create the initial board */
  void make_init_state() {
    next_to_move = MAX_PLAYER;
    last_move_is_pass = false;
    for (int y = 0; y < 8; ++y)
      for (int x = 0; x < 8; ++x)
	board[y][x] = EMPTY_CELL;
    board[3][3] = board[4][4] = MAX_PLAYER;
    board[3][4] = board[4][3] = MIN_PLAYER;
  }

  /* Determine whether a player must pass */
  bool must_pass() {
    for (int y = 0; y < 8; ++y)
      for (int x = 0; x < 8; ++x)
	if (can_play(y, x))
	  return false;
    return true;
  }

  /* Determine whether a piece can be put at a position */
  bool can_play(int y, int x) {
    if (board[y][x] != EMPTY_CELL)
      return false;
    for (int dy = -1; dy <= 1; ++dy)
      for (int dx = -1; dx <= 1; ++dx)
	if (dy || dx)
	  if (can_flip_at_direction(y, x, dy, dx))
	    return true;
    return false;
  }

  /* See if a direction has a flipping opportunity */
  /* Expect that board[y][x] has be checked to be empty */
  /* Should be considered internal */
  bool can_flip_at_direction(int y, int x, int dy, int dx) {
    y += dy;
    x += dx;
    if (y < 0 || y >= 8 || x < 0 || x >= 8)
      return false;
    if (board[y][x] != -next_to_move)
      return false;
    for (;;) {
      y += dy;
      x += dx;
      if (y < 0 || y >= 8 || x < 0 || x >= 8)
	return false;
      if (board[y][x] == next_to_move)
	return true;
      if (board[y][x] != -next_to_move)
	return false;
    }
  }

  /* Make a move */
  /* One can use the result argument put the result to another place */
  /* Assume that the move is checked to be valid before, so no further check */
  void make_move(int y, int x) {
    last_move_is_pass = false;
    board[y][x] = next_to_move;
    for (int dy = -1; dy <= 1; ++dy)
      for (int dx = -1; dx <= 1; ++dx)
	if (dy || dx)
	  try_to_flip_at_direction(y, x, dy, dx);
    next_to_move = -next_to_move;
  }

  void make_move(int y, int x, game_config_t &result) {
    result = *this;
    return result.make_move(y, x);
  }

  /* Try to flip the pieces towards a direction */
  /* Expect that board[y][x] has be a newly placed piece */
  /* Should be considered internal */
  void try_to_flip_at_direction(int y, int x, int dy, int dx) {
    y += dy;
    x += dx;
    if (y < 0 || y >= 8 || x < 0 || x >= 8)
      return;
    if (board[y][x] != -next_to_move)
      return;
    for (;;) {
      y += dy;
      x += dx;
      if (y < 0 || y >= 8 || x < 0 || x >= 8)
	return;
      if (board[y][x] == next_to_move)
	break;
      if (board[y][x] != -next_to_move)
	return;
    }
    for (;;) {
      y -= dy;
      x -= dx;
      if (board[y][x] == next_to_move)
	return;
      board[y][x] = next_to_move;
    }
  }

  /* Make a pass move, assume checked */
  void make_pass_move() {
    next_to_move = -next_to_move;
    last_move_is_pass = true;
  }

  /* Print the current board */
  void print() {
    cout << "  1 2 3 4 5 6 7 8\n";
    for (int y = 0; y < 8; ++y) {
      cout << char('A'+y);
      for (int x = 0; x < 8; ++x) {
	cout << ' ';
	switch (board[y][x]) {
	case MAX_PLAYER:
	  cout << MAX_PLAYER_CHAR;
	  break;
	case EMPTY_CELL:
	  cout << EMPTY_CELL_CHAR;
	  break;
	case MIN_PLAYER:
	  cout << MIN_PLAYER_CHAR;
	  break;
	}
      }
      cout << endl;
    }
  }

  /* Count the number of a particular type of piece in the board */
  int count(char piece) {
    int ret = 0;
    for (int y = 0; y < 8; ++y)
      for (int x = 0; x < 8; ++x)
	if (board[y][x] == piece)
	  ++ret;
    return ret;
  }

  /* Get an input.  Return false if failed. */
  bool get_move(int &y, int &x) {
    string s;
    getline(cin, s);
    if (s.length() != 2)
      return false;
    if (s[0] >= 'a' && s[0] <= 'h')
      y = s[0] - 'a';
    else if (s[0] >= 'A' && s[0] <= 'H')
      y = s[0] - 'A';
    else
      return false;
    if (s[1] >= '1' && s[1] <= '8')
      x = s[1] - '1';
    else
      return false;
    return can_play(y, x);
  }

};

#if 0
int main() {
  game_config_t state;
  bool v;
  state.make_init_state();
  for (int i = 0; i < 100000; ++i) {
    for (int j = 0; j < 8; ++j)
      for (int k = 0; k < 8; ++k)
        v &= state.can_play(j, k);
  }
}
#endif

/* Main program with no AI at all */
int
main()
{
  game_config_t state;
  state.make_init_state();
  for (;;) {
    state.print();
    if (state.next_to_move == MAX_PLAYER)
      cout << "MAX(" << MAX_PLAYER_CHAR << ")";
    else
      cout << "MIN(" << MIN_PLAYER_CHAR << ")";
    cout << "'s move: ";
    if (state.must_pass()) {
      cout << "pass" << endl;
      if (state.last_move_is_pass)
	break;
      state.make_pass_move();
    } else {
      int y, x;
      while (!state.get_move(y, x)) {
	cout << "Invalid move, please try again.\n";
	if (state.next_to_move == MAX_PLAYER)
	  cout << "MAX(" << MAX_PLAYER_CHAR << ")";
	else
	  cout << "MIN(" << MIN_PLAYER_CHAR << ")";
	cout << "'s move: ";
      }
      state.make_move(y, x);
    }
  }
  cout << "Game ended with MAX " << state.count(MAX_PLAYER)
       << ", MIN " << state.count(MIN_PLAYER) << endl;
}