import java.util.Random

class TicTacToe(val players:List[Player]) {
  val size = 3
  protected val field = new Array[Array[char]](size,size)
  val lines = (_stline((v,v2) => (v,v2))++_stline((v,v2) => (v2,v))++
              List(((size-1).until(-1,-1)).map(v=> (v,(size-1-v)))) ++
              List((0 until size).map(v=>(v,v)))).map(_.toList)

  def _stline(f:(int,int) => Pair[int,int]) = 
    (0 until size).map(v => (0 until size).map(v2 => f(v,v2)))

  def start:Option[Player] = {
    for(val i<-(0 until size); val j<-(0 until size)) { field(i)(j) = ' '}
    Stream.const(players).flatMap(v=>v).take(size*size).find {player => 
      val p@Pair(y,x) = player.put(this)
      if(!available_?(p)) error("Oops!")
      field(y)(x) = player.mark
      judge
    }
  }

  def judge = lines.exists(l => l.forall(!available_?(_)) && l.forall(v => at(l(0)) == at(v)))
  def available_?(pos:Pair[int,int]) = at(pos) equals ' '
  def at(pos:Pair[int,int]) = field(pos._1)(pos._2)
  def at_eq(pos:Pair[int,int], mark:char) = at(pos) equals mark
  def enemy_of(player:Player) = players.find{_.mark != player.mark}.get
}

abstract class Player{
  val mark:char
  val name:String
  def put(ttt:TicTacToe):Pair[int,int]
}

class RandomPlayer(override val mark:char, override val name:String) extends Player{
  val rnd = new Random
  override def put(ttt:TicTacToe) = {
    def _n = (rnd.nextInt(ttt.size), rnd.nextInt(ttt.size))
    def next(v:Pair[int,int]):Stream[Pair[int,int]] = Stream.cons(v, next(_n))
    next(_n).find(ttt.available_?).get
  }
}

class CleverPlayer(override val mark:char, override val name:String) extends Player {
  override def put(ttt:TicTacToe):Pair[int,int] = {
    val enemy = ttt.enemy_of(this)
    val return_if_available_find = (l:Seq[Pair[int,int]]) => l.find(ttt.available_?) match {
      case Some(pos) => return pos
      case _ => ()
    }

    def line2(v:char) = ttt.lines.filter(_.count(ttt.at_eq(_,v)) == 2)
    return_if_available_find(List(mark, enemy.mark).flatMap(line2).flatMap(v=>v))

    val all  = (for(val i<-(0 until ttt.size); val j<-(0 until ttt.size)) yield (i,j)).toList
    val center = (ttt.size/2, ttt.size/2)
    val corners = List((0,0), (ttt.size-1,ttt.size-1), (0,ttt.size-1), (ttt.size-1, 0))
    val others = all.diff(center::corners)

    if(all.count(ttt.at_eq(_, enemy.mark)) == 2 && ttt.at_eq(center, this.mark)) {
      if(!others.forall(ttt.available_?)) {
        val ps = all.filter(ttt.at_eq(_, enemy.mark))
        def vecv(a:Pair[int,int]) = (0 /: ps){(r, p) => r+(a._1 - p._1).abs+(a._2 - p._2).abs}
        return_if_available_find(corners.sort(vecv(_) < vecv(_)))
      }
      return_if_available_find(others)
    }

    return_if_available_find(List(center))
    return_if_available_find(corners)
    others.find(ttt.available_?).get
  }
}