TicTacToe.scala

import io.Source
import scala.util.control.Breaks._

/**
 * Scala TicTacToe game without any side effects
 * 
 * Written in response to following post (which also contains task description):
 *   http://blog.tmorris.net/scala-exercise-with-types-and-abstraction/
 */
object TicTacToe {
  val WinCount = 3

  sealed trait Move
  case object O extends Move
  case object X extends Move

  sealed abstract class Game[T](val board: T)
  case class InProgress[T](override val board: T) extends Game[T](board)
  case class Finished[T](override val board: T) extends Game[T](board)
  case class Broken[T](override val board: T, val problem: String) extends Game[T](board)

  case class Position(x: Int, y: Int)
  type Board = Seq[Seq[Option[Move]]]

  def createGame(width: Int, height: Int): InProgress[Board] =
    InProgress(for (x <- 0 until width) yield for(y <- 0 until height) yield None)

  def move(game: InProgress[Board], p: Position): Game[Board] =
    (game.board(p.x)(p.y), placeMove(game.board, p, whoseTurn(game))) match {
      case (Some(move),  board) => Broken(board, "Position was already taken by " + move)
      case (None, board) if finished_?(board) => Finished(board)
      case (None, board)  => InProgress(board)
    }

  def whoseTurn(game: InProgress[Board]): Move =
    game.board.flatMap(_.flatten).foldLeft((0, 0)) {
      case ((x, o), X) => (x + 1, o)
      case ((x, o), O) => (x, o + 1)
    } match {
      case (x, o) if x - o <= 0 => X
      case _ => O
    }

  def whoWon(game: Finished[Board]): Option[Move] =
    (for {
      x <- 0 until game.board.size
      y <- 0 until game.board(0).size
      curr <- game.board(x)(y)
      if won_?(game.board, curr, x, y)
    } yield Some(curr)) find (_.isDefined) getOrElse None

  def playerAt(game: Game[Board], p: Position): Option[Move] = game.board(p.x)(p.y)

  def draw(game: Game[Board]) = (for (y <- 0 until game.board(0).size) yield horizMoves(game.board, 0, y) map {
    case Some(m) => m.toString
    case None => " "
  } mkString " | ") mkString ("\n" + ("-" * game.board.size).mkString("-+-") + "\n")

  private def won_?(board: Board, m: Move, x: Int, y: Int): Boolean =
    won_?(horizMoves(board, x, y), m) || won_?(vertMoves(board, x, y), m) ||
        won_?(diagRightMoves(board, x, y), m) || won_?(diagRightMoves(board, x, y), m)

  private def won_?(moves: Seq[Option[Move]], m: Move): Boolean = moves.foldLeft(List(0)) {
    case (count :: rest, Some(`m`)) => count + 1 :: rest
    case (counts, _) => 0 :: counts
  }.max >= WinCount

  private def horizMoves(board: Board, x: Int, y: Int) = for (xx <- x until board.size) yield board(xx)(y)
  private def vertMoves(board: Board, x: Int, y: Int) = for (yy <- y until board(x).size) yield board(x)(yy)
  private def diagRightMoves(board: Board, x: Int, y: Int) =
    for ((xx, yy) <- (x until board.size) zip (y until board(x).size)) yield board(xx)(yy)
  private def diagLeftMoves(board: Board, x: Int, y: Int) =
    for ((xx, yy) <- (0 to x by -1) zip (y until board(x).size)) yield board(xx)(yy)

  private def placeMove(board: Board, p: Position, m: Move) =
    board.updated(p.x, board(p.x).updated(p.y, Some(m)))

  private def finished_?(board: Board) =
    board.flatMap(_.flatten).size == board.size * board(0).size || whoWon(Finished(board)).isDefined
}

object Int {
  def unapply(s: String): Option[Int] = try {
    Some(s.toInt)
  } catch {
    case _ : java.lang.NumberFormatException => None
  }
}

object TicTacToeGame extends Application {
  import TicTacToe._

  val game = createGame(3, 3)

  println("Welcome to Tic Tac Toe!")
  prompt(game)

  breakable {
    Source.stdin.getLines.map(_.split("\\s*,\\s*").toList match {
      case List(Int(x), Int(y)) if x < 3 && y < 3 => Some(Position(x, y))
      case _ => println("Invalid position, should be: x, y"); None
    }).filter(_.isDefined).map(_.get).foldLeft(game: Game[Board]) {
      case (g @ InProgress(_), p) =>
        move(g, p) match {
          case game @ InProgress(_) => prompt(game)
          case game @ Broken(_, problem) => print("Problem: " + problem); prompt(g)
          case game @ Finished(_) =>
            println(draw(game) + "\n" + "Game finished, " + whoWon(game) + " won!"); break; game
        }
      case _ => println("Wrong state!"); game
    }
  }

  println("Bye!")

  def prompt(game: InProgress[Board]): InProgress[Board] = {
    print("\n" + draw(game) + "\n" + whoseTurn(game) + "> ");
    game
  }
}

Isn't this a side effect ->

case Some(move) => throw new IllegalArgumentException("Position is already taken by " + move)

I wouldn't go as far as to call it "side-effect free" but it's a nice functional implementation. I enjoyed it. Would read again.

Thanks for the feedback!

@Raynes: I agree with you, It's hard to call code , that makes IO, side-effect free :), but I hope at least TicTacToe object has none (except this exception, as ssanj noticed)

@ssanj: yes, I think it can be described as side effect. I think cew game class can be introduced in order to get rid of it like this:

case class BrokenGame[T](override val board: T) extends Game[T](board)

and then return it instead of throwing an exception. But from the other, I'm not sure whether I like it.... exception feels better in this case (may be it's just my java background prevents my mind to absorb functional concepts... by I working on it :), but anyway you are right about side effect.

Great job with the implementation btw! :) I am struggling to understand Referencial Transparency and was looking at how your code eliminates side effects - hence the previous comment.

The only problem with the Exception is that it exits the program - which is a little undesirable. So if you enter something like 1,1 (twice) you get thrown out of the game. It might be better to display an error message and keep the game going.

Your 3rd state (BrokenGame) would work. Basically the Exception is another exit condition from the move method. Wrapping all exit conditions through subclasses of Game makes a lot of sense and removes the need for Exceptions.

so move is a function where:

(game: InProgress[Board], p: Position) => Game[Board]

For any combination of game and p, a Game[Board] is returned.

@ssanj: Thanks for the good words! I also noticed that program exits, when you enter position twice, but was too lazy to fix this :) But now I introduced Broken game state and I love it :). It's simplified move method and I can now pattern match on it. If I will load game from file, I can also return Broken game if board validation fails, and if I will add map and flatMap to Game class I can nicely use in in for comprehension... in other words when I think more deeply about it I see more advantages of new game state compared to exception.

The only thing remains is get rid of this breakable in main application... I don't like it, but I have nothing better. Seems that I need something between foldLeft and map operations - map that gives me previous mapped value as parameters like this:

def foldMap[T, A](initialValue: T)(op: (T /*this value of previous result or initial value*/, A) => T)

But unfortunately I have not found such operation in standard collections...

Line 58: на обе диагонали глядеть надоть :-) а компилятор не выдал ворнингов про unreachable code ?

также думаю, в комментарии стоит включить ссылку на http://blog.tmorris.net/scala-exercise-with-types-and-abstraction/ и формулировку задачи

I have studied and blogged about this project here http://blog.aunndroid.com/2011/11/chewy-code-scala-tictactoe-part-1.html