Skip to content

Spiral Matrix

Fill a square grid with 1 to n² in a clockwise spiral from the top left corner.

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

// FILE: spiral_matrix.nomi
//# A square matrix of the numbers from 1 up, spiralling clockwise inwards.

/// The `size` by `size` grid holding 1 to `size * size`, starting at the top
/// left corner and spiralling clockwise inwards.
pub fn spiral_matrix(size: Int) -> Vector<Vector<Int>>
    empty_row = Iter.repeat(0) |> Iter.take(size) |> Iter.to_vector()
    grid = Iter.repeat(empty_row) |> Iter.take(size) |> Iter.to_vector()

    fill(grid, (0, 0), (0, 1), 1, size * size)
end

/// Writes `value` at `position`, then moves on along `heading`, turning
/// clockwise when the next square is off the grid or already written, until
/// `last` is written.
fn fill(
    grid:     Vector<Vector<Int>>,
    position: (Int, Int),
    heading:  (Int, Int),
    value:    Int,
    last:     Int,
) -> Vector<Vector<Int>>
    if value > last then return grid

    grid = set_cell(grid, position, value)

    heading = if is_empty(grid, step(position, heading)) then
        heading
    else
        turn(heading)
    end

    fill(grid, step(position, heading), heading, value + 1, last)
end

fn step((row, column): (Int, Int), (dr, dc): (Int, Int)) -> (Int, Int)
    (row + dr, column + dc)
end

fn turn((dr, dc): (Int, Int)) -> (Int, Int)
    (dc, -dr)
end

/// Whether `position` is on the grid and not written yet.
fn is_empty(grid: Vector<Vector<Int>>, position: (Int, Int)) -> Bool
    cell_at(grid, position) == Some(0)
end

fn cell_at(grid: Vector<Vector<Int>>, (row, column): (Int, Int)) -> Maybe<Int>
    cells = Vector.get(grid, row)?
    Vector.get(cells, column)
end

/// `grid` with `value` at `position`, which is on the grid: `fill` only
/// steps onto a square `is_empty` accepted.
fn set_cell(grid: Vector<Vector<Int>>, (row, column): (Int, Int), value: Int) -> Vector<Vector<Int>>
    cells = Vector.get(grid, row)! |> Vector.set(column, value)!
    Vector.set(grid, row, cells)!
end

// FILE: spiral_matrix_test.nomi
import spiral_matrix.spiral_matrix

test "spiral_matrix"
    [
        ("empty spiral",     0, Vector[]),
        ("trivial spiral",   1, Vector[Vector[1]]),
        ("spiral of size 2", 2, Vector[Vector[1, 2], Vector[4, 3]]),
        ("spiral of size 3", 3, Vector[Vector[1, 2, 3], Vector[8, 9, 4], Vector[7, 6, 5]]),
        (
            "spiral of size 4",
            4,
            Vector[
                Vector[1, 2, 3, 4],
                Vector[12, 13, 14, 5],
                Vector[11, 16, 15, 6],
                Vector[10, 9, 8, 7],
            ],
        ),
        (
            "spiral of size 5",
            5,
            Vector[
                Vector[1, 2, 3, 4, 5],
                Vector[16, 17, 18, 19, 6],
                Vector[15, 24, 25, 20, 7],
                Vector[14, 23, 22, 21, 8],
                Vector[13, 12, 11, 10, 9],
            ],
        ),
    ]
    |> subtests (description, size, expected), description
        assert spiral_matrix(size) == expected
    end
end
  • The grid is Vector<Vector<Int>>, filled by walking the spiral and writing one cell at a time. This is the algorithm the problem describes, and it needs indexed reads (is the next square free?) and indexed updates. A closed form per cell (which ring, which side) or a Map<(Int, Int), Int> of the walk turned into rows were the alternatives; the walk is the more direct form of the problem’s description.

  • 0 marks an unwritten square, so “free” is cell_at(grid, position) == Some(0), which is False both off the grid and on a written square. One comparison does both checks.

  • The walk is a tail-recursive fn fill with the position and heading as tuples; turning clockwise is (dr, dc) -> (dc, -dr). It stops after writing size * size, so size 0 needs no special case.

  • set_cell returns the new grid. It reads the row with Vector.get(...)! and writes with Vector.set(...)!, both of which trap on an index outside the vector; fill only steps onto a square is_empty accepted, so the position is always on the grid.

  • The cases are one subtests table of (description, size, expected) rows. The 4x4 and 5x5 grids are written one grid row per line, which nomi fmt keeps because each breaks after its Vector[.