tic tac toe.scala

object CellState extends Enumeration {
  type CellState = Value
  val X, O, EMPTY = Value
}
import CellState._

object GameStatus extends Enumeration {
  type GameStatus = Value
  val X_WON, O_WON, DRAW, NOT_DECIDED = Value
}
import GameStatus._

type Triplet = Vector[CellState]
type Game = Vector[Triplet]

val emptyTriplet = Vector(EMPTY, EMPTY, EMPTY)
val xTriplet = Vector(X, X, X)
val oTriplet = Vector(O, O, O)
val emptyGame = Vector(emptyTriplet, emptyTriplet, emptyTriplet)

def checkTriplet(triplet: Triplet): GameStatus = {
  if (triplet == xTriplet)
    X_WON
  else if (triplet == oTriplet)
    O_WON
  else
    NOT_DECIDED
}

def diagonals(game: Game): Seq[Triplet] = Seq(
  Vector(game(0)(0), game(1)(1), game(2)(2)),
  Vector(game(0)(2), game(1)(1), game(2)(0))
)

def whoWon(game: Game) = {

  val transposed = game.transpose
  val triplets =
    game ++ transposed ++ diagonals(game)
  val results = for { triplet <- triplets } yield checkTriplet(triplet)
  if (results.contains(X_WON))
    X_WON
  else if (results.contains(O_WON))
    O_WON
  else if (game.flatten.contains(EMPTY))
    NOT_DECIDED
  else
    DRAW
}

def game2String(game: Game): String = {
  def row2String(row: Triplet): String = {
    row.map(cell => if (cell == EMPTY) " " else cell).mkString("|")
  }
  game.flatMap(row => List("-+-+-", row2String(row))).tail.mkString("\n")
}

def otherTurn(turn: CellState): CellState = if (turn == X) O else X

def remainingCells(game: Game): Seq[(Int, Int)] = {
  for {
    i <- game.indices
    j <- game(i).indices
    if game(i)(j) == EMPTY
  } yield (i, j)
}

def updateGame(game: Game, i: Int, j: Int, turn: CellState) =
  game.updated(i, game(i).updated(j, turn))

def solveGameHelper(game: Game, turn: CellState): GameStatus = {
  val winner = whoWon(game)
  if (winner != NOT_DECIDED) winner
  else {
    val statuses = remainingCells(game).map { case (i, j) =>
      solveGameHelper(updateGame(game, i, j, turn), otherTurn(turn))
    }

    if (turn == X) {
      if (statuses.contains(X_WON)) {
        X_WON
      } else if (statuses.contains(DRAW)) {
        DRAW
      } else {
        O_WON
      }
    } else {
      if (statuses.contains(O_WON)) {
        O_WON
      } else if (statuses.contains(DRAW)) {
        DRAW
      } else {
        X_WON
      }
    }
  }
}

println("if X starts he can force a " + solveGameHelper(emptyGame, X))

def checkMoves(game: Game, turn: CellState) = {
  println("-------------------------------------")
  println("Given the game:")
  println()
  println(game2String(game))
  println()
  println("And it is " + turn + "\'s turn")
  println("-------------------------------------")

  val remaining = remainingCells(game)
  remaining.foreach { case (i, j) =>
    println("if " + turn + " plays")
    println()

    val newGame = updateGame(game, i, j, turn)
    println(game2String(newGame))
    println()
    println(
      "" + otherTurn(turn) + " can force a " + solveGameHelper(
        newGame,
        otherTurn(turn)
      )
    )
    println("-------------------------------------")

  }
}

checkMoves(emptyGame, X)

checkMoves(Vector(Vector(X, EMPTY, EMPTY), emptyTriplet, emptyTriplet), O)
checkMoves(Vector(Vector(EMPTY, X, EMPTY), emptyTriplet, emptyTriplet), O)
checkMoves(Vector(emptyTriplet, Vector(EMPTY, X, EMPTY), emptyTriplet), O)