Skip to content

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
end
  • gamestate returns Result<State, Error>. State is the three canonical answers and Error the three ways a board breaks the rules; Error’s Display gives 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 a once list of position vectors. has_won is Iter.any_match over the lines of Iter.all_match over 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 subtests tables 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.