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
endok spiral_matrix (6 cases)
test result: ok. 6 passed, 0 failed
How it’s written
Section titled “How it’s written”-
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 aMap<(Int, Int), Int>of the walk turned into rows were the alternatives; the walk is the more direct form of the problem’s description. -
0marks an unwritten square, so “free” iscell_at(grid, position) == Some(0), which isFalseboth off the grid and on a written square. One comparison does both checks. -
The walk is a tail-recursive
fn fillwith the position and heading as tuples; turning clockwise is(dr, dc) -> (dc, -dr). It stops after writingsize * size, so size 0 needs no special case. -
set_cellreturns the new grid. It reads the row withVector.get(...)!and writes withVector.set(...)!, both of which trap on an index outside the vector;fillonly steps onto a squareis_emptyaccepted, so the position is always on the grid. -
The cases are one
subteststable of(description, size, expected)rows. The 4x4 and 5x5 grids are written one grid row per line, whichnomi fmtkeeps because each breaks after itsVector[.