Scala algorithm: Tic Tac Toe board check
Published
Algorithm goal
In Tic Tac Toe (also known as Naughts and Crosses), players place an X or an O onto a 3x3 grid. The winner is the player who gets three of their own in a row/column/diagonal.
Here, we verify that a Tic Tac Toe board has a winner; and whether a move is valid. To see how we could play Tic-Tac-Toe, see TicTacToeSolveMinMax.
Test cases in Scala
Algorithm in Scala
56 lines of Scala (compatible versions 2.13 & 3.0).
Explanation
The first challenge in solving these two functions is how to represent the board. In this case, the algorithm solution was implemented a TDD approach to allow for the most testable representation of the board.
There are other was of representing the board, such as Vector of Vector, or even a Map, but in this one, it is represented by a Vector, with mappings between Vector indices the the position on the board. (this is © from www.scala-algorithms.com)
A more Scala way of representing whether a position is filled is using an Option of an enumeration (O | X), rather than a Boolean or some other type.
Scala concepts & Hints
For-comprehension
The for-comprehension is highly important syntatic enhancement in functional programming languages.
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.
scanLeft and scanRight
Scala's `scan` functions enable you to do folds like foldLeft and foldRight, while collecting the intermediate results
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.
View
The
.view
syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.