Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
here's the answers. github.com/tonymorris/course/tree/answers –  abuzittin gillifirca Dec 31 '12 at 14:08
I'm not a Scala programmer, so I cannot comment on his Scala solution. But his Java API is worthless. –  abuzittin gillifirca Dec 31 '12 at 14:14
I'm curious as to why you say it's worthless? –  Dominic Bou-Samra Dec 31 '12 at 23:41
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. –  abuzittin gillifirca Jan 1 '13 at 10:05
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. –  Dominic Bou-Samra Jan 1 '13 at 10:07
show 1 more comment

2 Answers

why do you extend Move also of Winner?

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

 sealed trait Move extends Winner
share|improve this answer
Good question. It's purely for code reuse. I think their IS a relation, though it's not done any favors by the naming. –  Dominic Bou-Samra Jan 1 '13 at 7:41
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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