Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
import io.Source
import scala.util.control.Breaks._
* Scala TicTacToe game without any side effects
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 {
} catch {
case _ : java.lang.NumberFormatException => None
object TicTacToeGame extends Application {
import TicTacToe._
val game = createGame(3, 3)
println("Welcome to Tic Tac Toe!")
breakable {"\\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
def prompt(game: InProgress[Board]): InProgress[Board] = {
print("\n" + draw(game) + "\n" + whoseTurn(game) + "> ");
Copy link

ssanj commented Jan 10, 2011

Isn't this a side effect ->

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

Copy link

Raynes commented Jan 10, 2011

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.

Copy link

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.

Copy link

ssanj commented Jan 11, 2011

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.

Copy link

@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...

Copy link

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

Copy link

также думаю, в комментарии стоит включить ссылку на и формулировку задачи

Copy link

wmhtet commented Nov 5, 2011

I have studied and blogged about this project here

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment