Skip to content

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
end
  • The board is Vector<Vector<Int>>, with cells as the canonical 0 and 1. A Bool or a Cell enum would read better in the solution, but the test grids of Vector[1, 0, 1] read as the board; next_state is the only place that knows 1 means alive.
  • Neighbours are counted by indexed reads (cell_at), with an off-board neighbour read as None. A Maybe is an Iter of zero or one elements, so Iter.flat_map over the offsets drops the off-board ones before Iter.sum. A Set<(Int, Int)> of live cells, as flower-field uses, was the other natural form; I chose the vector because the input already is one and Vector.get’s None is 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 from Vector.set.
  • The eight offsets are a once literal, as in flower-field.
  • next_state is one case on (cell, live_neighbours) with the or-pattern (1, 2) or (_, 3).
  • Iter.sum totals the neighbours (style §33).
  • The cases are one subtests table of (description, board, expected) rows. The table is three compound levels deep, so nomi fmt breaks 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, which nomi fmt keeps because each breaks after its Vector[.