Tournament Tree

Source: https://github.com/ScalaWilliam/scala-game-tournament

Explanation

This is necessary for implementing an online gaming system that is expecting events for completed games. If an expected 'nextGame' is played, then we automatically want to advance the tournament forward.

There's not enough description for this to be clear, so you might want to avoid reading this one.

Tournament tree

The interface

Source

sealed trait TournamentTree[T] {

  def win(player: T): TournamentTree[T]

  def nextGames: Set[(T, T)]

  def winner: Option[T]

}

The specification

Source

class TournamentTreeSpec extends FunSuite {
  val Drakas = "Drakas"
  val Lucas = "Lucas"
  val Sanzo = "Sanzo"
  private val tourney = TournamentTree(Drakas, Lucas, Sanzo)

  test("First iteration is correct") {
    tourney.nextGames should contain theSameElementsAs Set(Drakas -> Lucas)
    tourney.winner shouldBe empty
  }
  test("Sanzo win does nothing") {
    tourney.win(Sanzo).nextGames shouldEqual tourney.nextGames
    tourney.win(Sanzo).winner shouldEqual tourney.winner
  }
  test("Drakas win pushes to next stage") {
    tourney.win(Drakas).nextGames should contain theSameElementsAs Set(Drakas -> Sanzo)
    tourney.win(Drakas).winner shouldBe empty
  }
  test("Drakas win 2x pushes to final stage") {
    tourney.win(Drakas).win(Drakas).nextGames shouldBe empty
    tourney.win(Drakas).win(Drakas).winner shouldBe Some(Drakas)
  }

}

Solutioning

We want to meet the specification with minimal possible work. We shall represent the solution as a tree structure because it looks like a tree.

In this solution, a Tournament is in either an Undecided state or a Decided state. An Undecided state will contain two Tournaments, one to the left and one to the right.

Solution for generating the tree

Source

/** Bottom up build: take every 2 consecutive items, create an UndefinedPlayer,
  * then reprocess the new list of trees until we're left with only 1.
  */
@tailrec
private def buildTree[T](tournamentTree: TournamentTree[T]*): TournamentTree[T] = {
  tournamentTree.toList match {
    case tree :: Nil => tree
    case other =>
      buildTree {
        other.grouped(2).map(_.toList).map {
          case a :: b :: Nil => UndefinedPlayer(a, b)
          case a :: _ => a
          case Nil => ???
        }.toList: _*
      }
  }
}

Solution for a Decided state

Source

case class DefinedPlayer[T](player: T) extends TournamentTree[T] {
  def win(player: T): TournamentTree[T] = this

  def nextGames: Set[(T, T)] = Set.empty

  def winner: Option[T] = Some(player)
}

Solution for an Undecided state

Source

case class UndefinedPlayer[T](left: TournamentTree[T], right: TournamentTree[T]) extends TournamentTree[T] {
  def win(player: T): TournamentTree[T] = (left, right) match {
    case (DefinedPlayer(`player`), DefinedPlayer(_)) => DefinedPlayer(player)
    case (DefinedPlayer(_), DefinedPlayer(`player`)) => DefinedPlayer(player)
    case _ => UndefinedPlayer(left.win(player), right.win(player))
  }

  def nextGames: Set[(T, T)] = (left, right) match {
    case (DefinedPlayer(a), DefinedPlayer(b)) => Set(a -> b)
    case _ => left.nextGames ++ right.nextGames
  }

  def winner: Option[T] = None
}