Skip to content

Instantly share code, notes, and snippets.

@OlegIlyenko
Created January 9, 2011 17:41
Show Gist options
  • Save OlegIlyenko/771842 to your computer and use it in GitHub Desktop.
Save OlegIlyenko/771842 to your computer and use it in GitHub Desktop.
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
}
}
@ssanj
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.

@OlegIlyenko
Copy link
Author

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

@annoynimouse
Copy link

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

@annoynimouse
Copy link

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

@wmhtet
Copy link

wmhtet commented Nov 5, 2011

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

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