Game of Life
Compute the next generation of a Conway’s Game of Life board.
Adapted from Exercism’s problem specification (MIT). Listed under Grids & Matrices.
// FILE: game_of_life.nomi
//# Conway's Game of Life: one generation of a board of live and dead cells.
once neighbours = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
/// The next generation of `board`, whose cells are `1` for live and `0`
/// for dead, row by row: a live cell with two or three live
/// neighbours lives on, a dead cell with three comes alive, and every other
/// cell is dead.
pub fn tick(board: Vector<Vector<Int>>) -> Vector<Vector<Int>>
board
|> Iter.with_index()
|> Iter.map(fn (row, cells) ->
cells
|> Iter.with_index()
|> Iter.map(fn (column, cell) -> next_state(cell, live_neighbours(board, row, column)))
|> Iter.to_vector()
end)
|> Iter.to_vector()
end
fn live_neighbours(board: Vector<Vector<Int>>, row: Int, column: Int) -> Int
neighbours
|> Iter.flat_map(fn (dr, dc) -> cell_at(board, row + dr, column + dc))
|> Iter.sum()
end
/// The cell at `row` and `column`, or None off the board.
fn cell_at(board: Vector<Vector<Int>>, row: Int, column: Int) -> Maybe<Int>
cells = Vector.get(board, row)?
Vector.get(cells, column)
end
fn next_state(cell: Int, live_neighbours: Int) -> Int
case (cell, live_neighbours)
(1, 2) or (_, 3) -> 1
_ -> 0
end
end
// FILE: game_of_life_test.nomi
import game_of_life.tick
test "tick"
[
("empty matrix", Vector[], Vector[]),
(
"live cells with zero live neighbors die",
Vector[Vector[0, 0, 0], Vector[0, 1, 0], Vector[0, 0, 0]],
Vector[Vector[0, 0, 0], Vector[0, 0, 0], Vector[0, 0, 0]],
),
(
"live cells with only one live neighbor die",
Vector[Vector[0, 0, 0], Vector[0, 1, 0], Vector[0, 1, 0]],
Vector[Vector[0, 0, 0], Vector[0, 0, 0], Vector[0, 0, 0]],
),
(
"live cells with two live neighbors stay alive",
Vector[Vector[1, 0, 1], Vector[1, 0, 1], Vector[1, 0, 1]],
Vector[Vector[0, 0, 0], Vector[1, 0, 1], Vector[0, 0, 0]],
),
(
"live cells with three live neighbors stay alive",
Vector[Vector[0, 1, 0], Vector[1, 0, 0], Vector[1, 1, 0]],
Vector[Vector[0, 0, 0], Vector[1, 0, 0], Vector[1, 1, 0]],
),
(
"dead cells with three live neighbors become alive",
Vector[Vector[1, 1, 0], Vector[0, 0, 0], Vector[1, 0, 0]],
Vector[Vector[0, 0, 0], Vector[1, 1, 0], Vector[0, 0, 0]],
),
(
"live cells with four or more neighbors die",
Vector[Vector[1, 1, 1], Vector[1, 1, 1], Vector[1, 1, 1]],
Vector[Vector[1, 0, 1], Vector[0, 0, 0], Vector[1, 0, 1]],
),
(
"bigger matrix",
Vector[
Vector[1, 1, 0, 1, 1, 0, 0, 0],
Vector[1, 0, 1, 1, 0, 0, 0, 0],
Vector[1, 1, 1, 0, 0, 1, 1, 1],
Vector[0, 0, 0, 0, 0, 1, 1, 0],
Vector[1, 0, 0, 0, 1, 1, 0, 0],
Vector[1, 1, 0, 0, 0, 1, 1, 1],
Vector[0, 0, 1, 0, 1, 0, 0, 1],
Vector[1, 0, 0, 0, 0, 0, 1, 1],
],
Vector[
Vector[1, 1, 0, 1, 1, 0, 0, 0],
Vector[0, 0, 0, 0, 0, 1, 1, 0],
Vector[1, 0, 1, 1, 1, 1, 0, 1],
Vector[1, 0, 0, 0, 0, 0, 0, 1],
Vector[1, 1, 0, 0, 1, 0, 0, 1],
Vector[1, 1, 0, 1, 0, 0, 0, 1],
Vector[1, 0, 0, 0, 0, 0, 0, 0],
Vector[0, 0, 0, 0, 0, 0, 1, 1],
],
),
]
|> subtests (description, board, expected), description
assert tick(board) == expected
end
endok tick (8 cases)
test result: ok. 8 passed, 0 failed
How it’s written
Section titled “How it’s written”- The board is
Vector<Vector<Int>>, with cells as the canonical0and1. ABoolor aCellenum would read better in the solution, but the test grids ofVector[1, 0, 1]read as the board;next_stateis the only place that knows1means alive. - Neighbours are counted by indexed reads (
cell_at), with an off-board neighbour read asNone. AMaybeis anIterof zero or one elements, soIter.flat_mapover the offsets drops the off-board ones beforeIter.sum. ASet<(Int, Int)>of live cells, as flower-field uses, was the other natural form; I chose the vector because the input already is one andVector.get’sNoneis exactly “off the board”. - The next generation is built by mapping over rows and cells with
Iter.with_index, not by updating cells of a copy, so no indexed update is needed. This was the natural form, not a retreat fromVector.set. - The eight offsets are a
onceliteral, as in flower-field. next_stateis onecaseon(cell, live_neighbours)with the or-pattern(1, 2) or (_, 3).Iter.sumtotals the neighbours (style §33).- The cases are one
subteststable of(description, board, expected)rows. The table is three compound levels deep, sonomi fmtbreaks it one row per line; each row is too wide for one line and breaks into its three parts, and a 3x3 grid fits on one line inside it. The 8x8 grids are written one board row per line, whichnomi fmtkeeps because each breaks after itsVector[.