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
endok winner (12 cases)
test result: ok. 12 passed, 0 failed
How it’s written
Section titled “How it’s written”winnerreturnsMaybe<Player>, aPlayerenum ofXandO, 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. connectssets the start and goal edges per player as a pair of predicates, andreachesis 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. Cellis atypealiasfor(Int, Int), so the search’s signature says what its tuples are.- The twelve canonical cases are one
subteststable named by the description column, each board one row per line as the canonical data draws it.