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).
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.
Scala concepts & Hints
'collect' allows you to use Pattern Matching, to filter and map items.
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 in Scala lets you quickly identify what you are looking for in a data, and also extract it.
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.
A state machine is the use of `sealed trait` to represent all the possible states (and transitions) of a 'machine' in a hierarchical form.
In Scala, tail recursion enables you to rewrite a mutable structure such as a while-loop, into an immutable algorithm.