So I've been working on Tony Morris' Tic-Tac-Toe challenge. The rules are as follows:

Write an API for playing tic-tac-toe. There should be no side-effects (or variables), at all, for real. The move function will take a game state, a Position and it will return a data type that you write yourself.

The following functions (at least) must be supported:

move (as mentioned)

whoseTurn (returns which player’s turn it is)

whoWon (returns who won or if a draw)

playerAt (returns which player, if any, is at a given position)

Importantly, the following must be true:

It is a compile-time error to call move or whoseTurn on a game that has been completed It is a compile-time error to call whoWon on a game that has not been completed The playerAt function must be supported on both complete and in-play games

Good luck and may the types be with you.

This is what I've got so far:

object TicTacToe2 {

  type Board = Map[Position, Option[Move]]

  sealed trait Winner
  case object Draw extends Winner

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

  sealed trait Position
  case object TL extends Position
  case object TM extends Position
  case object TR extends Position
  case object ML extends Position
  case object MM extends Position
  case object MR extends Position
  case object BL extends Position
  case object BM extends Position
  case object BR extends Position

  case class InProgress(override val board: Board) extends GameState(board) 
  case class Finished(override val board: Board) extends GameState(board) 

  sealed abstract class GameState(val board: Board) {
    override def toString = this.board.mkString("\n")

  private val winningPatterns: Set[Set[Position]] = Set(Set(TL,TM, TR), Set(ML, MM, MR), Set(BL, BM, BR), 
  Set(TL, ML, BL), Set(TM, MM, BM), Set(TR, MR, BR), Set(TL, MM, BR), Set(TR, MM, BL))

  def whoseTurn(gameState: InProgress): Option[Move] = {
    val xs = gameState.board.count{ case (k, v) => v == Some(X) }
    val os = gameState.board.count{ case (k, v) => v == Some(O) }
    if (xs > os) Some(O) else if (xs < os) Some(X) else None

  private def checkPlayerHasWon(gameState: GameState): Option[Winner] = {
    def hasPlayerWon(player: Move) = { 
      val playerPositions = gameState.board.filter { case (k, v) => v == Some(player) }.keys.toSet 
      winningPatterns.exists(wp => wp.subsetOf(playerPositions))
    if (hasPlayerWon(X)) Some(X) 
    else if (hasPlayerWon(O)) Some(O)
    else if(gameState.board.count{ case (k, v) => v == None } == 0) Some(Draw) 
    else None 

  def move(gameState: InProgress, position: Position, player: Move): GameState = {
    val tempGame = InProgress { gameState.board.updated(position, Some(player)) }
    checkPlayerHasWon(tempGame) match {
      case None => InProgress { tempGame.board }
      case Some(winner) => Finished { gameState.board }

  def playerAt(gameState: GameState, position: Position): Option[Move] = gameState.board.get(position).get

  def whoWonOrDraw(finishedGame: Finished): Winner = checkPlayerHasWon(finishedGame).get

object TicTacToeApplication2 {
  import TicTacToe2._

  def createGame = InProgress { List(TL, TM, TR, ML, MM, MR, BL, BM, BR).map((_, None)).toMap }

My biggest concern so far is: How do I play this game as a client without resorting to painful typechecking/casting patterns? My tests use this sort of approach:

new BlankBoardTest {
  val newGameState: InProgress = move(gameState, TR, O).asInstanceOf[InProgress]
  val newGameState2 = move(newGameState, BM, X)
  newGameState2 match {
    case game @ InProgress(_) => {
      assert(playerAt(game, TR) === Some(O))
      assert(playerAt(game, BM) === Some(X))
    case _ => fail

See how I'm pattern matching on the type like that? Is there a way to avoid doing this and chain them together so a client can play them without having to EXPLICITLY typecheck on the gameState? Perhaps using a monad and for-comprehensions?

  • \$\begingroup\$ here's the answers. github.com/tonymorris/course/tree/answers \$\endgroup\$ Dec 31, 2012 at 14:08
  • \$\begingroup\$ I'm not a Scala programmer, so I cannot comment on his Scala solution. But his Java API is worthless. \$\endgroup\$ Dec 31, 2012 at 14:14
  • \$\begingroup\$ I'm curious as to why you say it's worthless? \$\endgroup\$ Dec 31, 2012 at 23:41
  • \$\begingroup\$ First of all, an API is about simplicity, orthogonality and understandability. Trying to write Haskell code in Java results in code just as ugly as Win32 C code in Haskell. Actually reading C-style code written in C++ hurts my eyes and more importantly my brain and C++ style code written through abuse of C macros does the same. Your product does not have a smooth surface if your cutting against the grain. \$\endgroup\$ Jan 1, 2013 at 10:05
  • \$\begingroup\$ This is a learning exercise to better exploit the powers of a type system, not something you would necessarily put into production. Did you read the blog post? I actually think his Java solution reads quite well. \$\endgroup\$ Jan 1, 2013 at 10:07

2 Answers 2


why do you extend Move also of Winner?

what is the relation between every move object and winning state?

 sealed trait Move extends Winner
  • \$\begingroup\$ Good question. It's purely for code reuse. I think their IS a relation, though it's not done any favors by the naming. \$\endgroup\$ Jan 1, 2013 at 7:41

This is not an answer to the bounty question.

 def whoseTurn(gameState: InProgress): Option[Move] = {
    val xs = gameState.board.count{ case (k, v) => v == Some(X) }
    val os = gameState.board.count{ case (k, v) => v == Some(O) }
    if (xs > os) Some(O) else if (xs < os) Some(X) else None

For an in-progress game whose turn it is is always certain. this method should not return an optional type. there is a bug in the last line. It's the first player's (X I think) turn if no of X s and O s on the board are equal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.