Scala algorithm: Single-elimination tournament tree
Published
Algorithm goal
The single-elimination tournament is popular in team games. Represent a tournament tree which enables us to know what games to expect next, and who the overall winner of the tournament is, once the wins have been submitted. Here is a visual representation:

Test cases in Scala
assert(
tourney.nextGames == Set(Drakas -> Lucas),
"The first iteration has a specific next game"
)
assert(tourney.winner.isEmpty, "The first iteration does not have a winner")
assert(
tourney.win(Sanzo).nextGames == tourney.nextGames,
"A win by an unscheduled player does nothing to affect next games"
)
assert(
tourney.win(Sanzo).winner.isEmpty,
"A win by an unscheduled player does not give a new winner"
)
assert(
tourney.win(Drakas).nextGames == Set(Drakas -> Sanzo),
"A Drakas win pushes the next game to be Drakas v Sanzo"
)
assert(
tourney.win(Drakas).winner.isEmpty,
"A Drakas win still does not yield an overall winner"
)
assert(
tourney.win(Drakas).win(Drakas).nextGames.isEmpty,
"Drakas win 2x means final stage has no more expected games"
)
assert(
tourney.win(Drakas).win(Drakas).winner.contains(Drakas),
"Drakas win 2x means he is now set a winner of the tournament"
)
Algorithm in Scala
65 lines of Scala (compatible versions 2.13 & 3.0).
Get the full algorithm !
or
'Unlimited Scala Algorithms' gives you access to all the 100 published Scala Algorithms!
Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.
Explanation
There are two aspects of this algorithm: first is to build the tree in-memory, the second is to process inputs in each iteration.
In building the tree, we take every 2 sibling players, and create a sub-tournament. Then each sibling sub-tournament gets combined with the next; we repeat until we are left with no siblings, and that becomes the root of our tournament tree. (this is © from www.scala-algorithms.com)
The leaf nodes are filled in, so they are 'DefinedPlayer', and those games that were not played yet are 'UndefinedPlayer'. Each 'UndefinedPlayer' has a left and a right, which represent the sub-trees that are either defined or not defined by themselves. When both children of an Undefined are defined, it means we now expect a face-off.
Full explanation is available to subscribers
Scala concepts & Hints
Collect
'collect' allows you to use Pattern Matching, to filter and map items.
Option Type
The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!
Pattern Matching
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
Stack Safety
Stack safety is present where a function cannot crash due to overflowing the limit of number of recursive calls.
This function will work for n = 5, but will not work for n = 2000 (crash with java.lang.StackOverflowError) - however there is a way to fix it :-)
In Scala Algorithms, we try to write the algorithms in a stack-safe way, where possible, so that when you use the algorithms, they will not crash on large inputs. However, stack-safe implementations are often more complex, and in some cases, overly complex, for the task at hand.
State machine
A state machine is the use of `sealed trait` to represent all the possible states (and transitions) of a 'machine' in a hierarchical form.
Tail Recursion
In Scala, tail recursion enables you to rewrite a mutable structure such as a while-loop, into an immutable algorithm.