public
Last active

  • Download Gist
TicTacToe.scala
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
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/ и формулировку задачи

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.