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 10, 2011

Isn't this a side effect ->

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

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

@OlegIlyenko
Copy link
Author

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.

@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