State of Tic-Tac-Toe
Decide whether a tic-tac-toe board is a win, a draw or a game still going, or explain why no game played by the rules could have left it.
Adapted from Exercism’s problem specification (MIT). Listed under Games & Simulation.
// FILE: state_of_tic_tac_toe.nomi
//# Where a game of tic-tac-toe stands, and whether its board is valid.
/// Where a valid game stands.
pub enum State
Win
Draw
Ongoing
end
/// Why a board cannot come from a game played by the rules.
pub enum Error
XWentTwice
OStarted
PlayedAfterWin
end
impl Display for Error
fn to_string(error: Error) -> String
case error
.XWentTwice -> "Wrong turn order: X went twice"
.OStarted -> "Wrong turn order: O started"
.PlayedAfterWin -> "Impossible board: game should have ended after the game was won"
end
end
end
/// The positions of the eight lines that win, in a board read row by row:
/// three rows, three columns and two diagonals.
once lines = [
Vector[0, 1, 2],
Vector[3, 4, 5],
Vector[6, 7, 8],
Vector[0, 3, 6],
Vector[1, 4, 7],
Vector[2, 5, 8],
Vector[0, 4, 8],
Vector[2, 4, 6],
]
/// The state of the game on `board`, three rows of three cells, each `X`,
/// `O` or a space. X plays first, and the game stops at the first line of
/// three.
pub fn gamestate(board: List<String>) -> Result<State, Error>
cells =
board
|> Iter.flat_map(String.to_codepoints)
|> Iter.to_vector()
xs = marks(cells, 'X')
os = marks(cells, 'O')
x_won = has_won(cells, 'X')
o_won = has_won(cells, 'O')
case
os > xs -> Err(.OStarted)
xs > os + 1 -> Err(.XWentTwice)
x_won and (o_won or xs == os) or o_won and xs > os -> Err(.PlayedAfterWin)
x_won or o_won -> Ok(.Win)
xs + os == 9 -> Ok(.Draw)
_ -> Ok(.Ongoing)
end
end
/// How many cells hold `mark`.
fn marks(cells: Vector<Codepoint>, mark: Codepoint) -> Int
Iter.count_by(cells, &(&1 == mark))
end
/// Whether `mark` fills one of the lines.
fn has_won(cells: Vector<Codepoint>, mark: Codepoint) -> Bool
Iter.any_match(lines, fn line -> Iter.all_match(line, &(Vector.get(cells, &1)! == mark)))
end
// FILE: state_of_tic_tac_toe_test.nomi
import state_of_tic_tac_toe
test "won games"
[
("Finished game where X won via left column victory", ["XOO", "X ", "X "]),
("Finished game where X won via middle column victory", ["OXO", " X ", " X "]),
("Finished game where X won via right column victory", ["OOX", " X", " X"]),
("Finished game where O won via left column victory", ["OXX", "OX ", "O "]),
("Finished game where O won via middle column victory", ["XOX", " OX", " O "]),
("Finished game where O won via right column victory", ["XXO", " XO", " O"]),
("Finished game where X won via top row victory", ["XXX", "XOO", "O "]),
("Finished game where X won via middle row victory", ["O ", "XXX", " O "]),
("Finished game where X won via bottom row victory", [" OO", "O X", "XXX"]),
("Finished game where O won via top row victory", ["OOO", "XXO", "XX "]),
("Finished game where O won via middle row victory", ["XX ", "OOO", "X "]),
("Finished game where O won via bottom row victory", ["XOX", " XX", "OOO"]),
("Finished game where X won via falling diagonal victory", ["XOO", " X ", " X"]),
("Finished game where X won via rising diagonal victory", ["O X", "OX ", "X "]),
("Finished game where O won via falling diagonal victory", ["OXX", "OOX", "X O"]),
("Finished game where O won via rising diagonal victory", [" O", " OX", "OXX"]),
("Finished game where X won via a row and a column victory", ["XXX", "XOO", "XOO"]),
("Finished game where X won via two diagonal victories", ["XOX", "OXO", "XOX"]),
]
|> subtests (description, board), description
assert state_of_tic_tac_toe.gamestate(board) == Ok(.Win)
end
end
test "drawn games"
[
("Draw", ["XOX", "XXO", "OXO"]),
("Another draw", ["XXO", "OXX", "XOO"]),
]
|> subtests (description, board), description
assert state_of_tic_tac_toe.gamestate(board) == Ok(.Draw)
end
end
test "ongoing games"
[
("Ongoing game: one move in", [" ", "X ", " "]),
("Ongoing game: two moves in", ["O ", " X ", " "]),
("Ongoing game: five moves in", ["X ", " XO", "OX "]),
]
|> subtests (description, board), description
assert state_of_tic_tac_toe.gamestate(board) == Ok(.Ongoing)
end
end
test "invalid boards"
[
(
"Invalid board: X went twice",
["XX ", " ", " "],
"Wrong turn order: X went twice",
),
("Invalid board: O started", ["OOX", " ", " "], "Wrong turn order: O started"),
(
"Invalid board: X won and O kept playing",
["XXX", "OOO", " "],
"Impossible board: game should have ended after the game was won",
),
(
"Invalid board: players kept playing after a win",
["XXX", "OOO", "XOX"],
"Impossible board: game should have ended after the game was won",
),
(
"Invalid board: O kept playing after X wins",
["OO ", "XXX", " O "],
"Impossible board: game should have ended after the game was won",
),
(
"Invalid board: X kept playing after O wins",
["XX ", "OOO", " XX"],
"Impossible board: game should have ended after the game was won",
),
]
|> subtests (description, board, message), description
assert Err(error) = state_of_tic_tac_toe.gamestate(board)
assert "${error}" == message
end
endok won games (18 cases)
ok drawn games (2 cases)
ok ongoing games (3 cases)
ok invalid boards (6 cases)
test result: ok. 29 passed, 0 failed
How it’s written
Section titled “How it’s written”gamestatereturnsResult<State, Error>.Stateis the three canonical answers andErrorthe three ways a board breaks the rules;Error’sDisplaygives the canonical messages, so the variants carry no text.- The board is read into one
Vector<Codepoint>of nine cells, row by row, and the eight winning lines are aoncelist of position vectors.has_wonisIter.any_matchover the lines ofIter.all_matchover their cells. - The rules are counts and wins: O never has more marks than X, X never more than one more than O, and the game stops at a win, so an X win leaves X one mark ahead and an O win leaves the counts equal. A win either way round, or both players winning, is the canonical “game should have ended” error.
- The checks run in the canonical order of precedence: turn order first, then play after a win, then the state. A board with every cell full and no line is a draw.
- The cases are four
subteststables by expected outcome. The invalid-board table asserts each error’s message, which is what the canonical data gives. The two cases that newer ones reimplement (a middle-row win that broke the turn order, and an older error message) are left out.