Skip to content

Connect

Find the winner of a game of Hex: X wins by joining the left edge to the right, O by joining the top edge to the bottom.

Adapted from Exercism’s problem specification (MIT). Listed under Grids & Matrices.

// FILE: connect.nomi
//# Hex, the game of connecting two opposite sides of a rhombus of hexagons.
//# `X` joins the left edge to the right one, `O` the top edge to the bottom.

/// The two players.
pub enum Player
    X
    O
end

/// A cell on the board, `(row, column)`.
typealias Cell (Int, Int)

/// The six cells a hexagon touches. Each row is shifted half a cell right
/// of the one above, so a cell touches the one above it and the one above
/// and right, and the one below it and the one below and left.
once neighbours = [(0, -1), (0, 1), (-1, 0), (-1, 1), (1, -1), (1, 0)]

/// The player whose stones join their two sides of `board`, or `None`.
/// Each row of the board is its cells separated by spaces, `X`, `O` or `.`,
/// indented to show the shift.
pub fn winner(board: List<String>) -> Maybe<Player>
    rows =
        board
        |> Iter.map(fn line -> line |> String.trim() |> String.split(" ") |> Iter.to_list())
        |> Iter.to_list()

    Iter.find([.X, .O], &connects(rows, &1))
end

/// Whether `player`'s stones join their two sides of the board.
fn connects(rows: List<List<String>>, player: Player) -> Bool
    stones =
        rows
        |> Iter.with_index()
        |> Iter.flat_map(fn (row, cells) ->
            cells
            |> Iter.with_index()
            |> Iter.filter(fn (_column, cell) -> cell == stone(player))
            |> Iter.map(fn (column, _cell) -> (row, column))
        end)
        |> Iter.to_set()

    last_row = Iter.count(rows) - 1
    width = rows |> Iter.first() |> Maybe.map(Iter.count) |> Maybe.with_default(0)
    last_column = width - 1

    (is_start, is_goal) = case player
        .X ->
            (
                fn (_row, column): Cell -> column == 0,
                fn (_row, column): Cell -> column == last_column,
            )

        .O ->
            (fn (row, _column): Cell -> row == 0, fn (row, _column): Cell -> row == last_row)
    end

    starts = stones |> Iter.filter(is_start) |> Iter.to_list()
    reaches(stones, starts, Iter.to_set(starts), is_goal)
end

fn stone(player: Player) -> String
    case player
        .X -> "X"
        .O -> "O"
    end
end

/// Whether a path through `stones` leads from a cell of `frontier` to a
/// cell where `is_goal` holds, without stepping on a cell of `seen` again.
/// A depth-first search: the newest cells found are tried first.
fn reaches(
    stones:   Set<Cell>,
    frontier: List<Cell>,
    seen:     Set<Cell>,
    is_goal:  (Cell) -> Bool,
) -> Bool
    case frontier
        [] ->
            False

        [cell, ..rest] ->
            if is_goal(cell) then return True

            (row, column) = cell

            next =
                neighbours
                |> Iter.map(fn (dr, dc) -> (row + dr, column + dc))
                |> Iter.filter(fn n -> n in stones and not n in seen)
                |> Iter.to_list()

            reaches(stones, [..next, ..rest], Set.union(seen, Iter.to_set(next)), is_goal)
    end
end

// FILE: connect_test.nomi
import
    connect
    connect.Player
end

test "winner"
    [
        (
            "an empty board has no winner",
            [
                ". . . . .",
                " . . . . .",
                "  . . . . .",
                "   . . . . .",
                "    . . . . .",
            ],
            None,
        ),
        ("X can win on a 1x1 board", ["X"], Some(Player.X)),
        ("O can win on a 1x1 board", ["O"], Some(.O)),
        (
            "only edges does not make a winner",
            [
                "O O O X",
                " X . . X",
                "  X . . X",
                "   X O O O",
            ],
            None,
        ),
        (
            "illegal diagonal does not make a winner",
            [
                "X O . .",
                " O X X X",
                "  O X O .",
                "   . O X .",
                "    X X O O",
            ],
            None,
        ),
        (
            "nobody wins crossing adjacent angles",
            [
                "X . . .",
                " . X O .",
                "  O . X O",
                "   . O . X",
                "    . . O .",
            ],
            None,
        ),
        (
            "X wins crossing from left to right",
            [
                ". O . .",
                " O X X X",
                "  O X O .",
                "   X X O X",
                "    . O X .",
            ],
            Some(.X),
        ),
        (
            "X wins with left-hand dead end fork",
            [
                ". . X .",
                " X X . .",
                "  . X X X",
                "   O O O O",
            ],
            Some(.X),
        ),
        (
            "X wins with right-hand dead end fork",
            [
                ". . X X",
                " X X . .",
                "  . X X .",
                "   O O O O",
            ],
            Some(.X),
        ),
        (
            "O wins crossing from top to bottom",
            [
                ". O . .",
                " O X X X",
                "  O O O .",
                "   X X O X",
                "    . O X .",
            ],
            Some(.O),
        ),
        (
            "X wins using a convoluted path",
            [
                ". X X . .",
                " X . X . X",
                "  . X . X .",
                "   . X X . .",
                "    O O O O O",
            ],
            Some(.X),
        ),
        (
            "X wins using a spiral path",
            [
                "O X X X X X X X X",
                " O X O O O O O O O",
                "  O X O X X X X X O",
                "   O X O X O O O X O",
                "    O X O X X X O X O",
                "     O X O O O X O X O",
                "      O X X X X X O X O",
                "       O O O O O O O X O",
                "        X X X X X X X X O",
            ],
            Some(.X),
        ),
    ]
    |> subtests (description, board, expected), description
        assert connect.winner(board) == expected
    end
end
  • winner returns Maybe<Player>, a Player enum of X and O, where the canonical data writes "X", "O" and "" for no winner.
  • The board is read as the canonical rows: each is trimmed of its indentation and split on spaces, so cell (row, column) is the column-th symbol of the row. The indentation is only the picture of the shift, which the neighbour offsets carry: a cell touches its two sides, the cell above and the one above and right, and the cell below and the one below and left.
  • A player’s stones are collected once into a Set<Cell>, so the search asks set membership and never indexes the grid or checks bounds; a cell off the board holds no stone.
  • connects sets the start and goal edges per player as a pair of predicates, and reaches is a depth-first search from every stone on the start edge, with a frontier list and a set of cells seen. It stops at the first cell on the goal edge.
  • Both players are tried with Iter.find. A legal board has at most one winner, so the order does not matter.
  • Cell is a typealias for (Int, Int), so the search’s signature says what its tuples are.
  • The twelve canonical cases are one subtests table named by the description column, each board one row per line as the canonical data draws it.