Rectangles
Count the rectangles in an ASCII diagram: + corners joined by - sides along the rows and | sides down the columns, where a + may also stand in a side.
Adapted from Exercism’s problem specification (MIT). Listed under Grids & Matrices.
// FILE: rectangles.nomi
//# Counts the rectangles in an ASCII diagram.
/// How many rectangles the ASCII diagram `lines` draws: four `+` corners
/// joined by sides of `-` along the rows and `|` down the columns, where a
/// `+` may also stand in a side.
//! assert count(["+-+", "| |", "+-+"]) == 1
//
pub fn count(lines: List<String>) -> Int
grid =
lines
|> Iter.map(Iter.to_vector)
|> Iter.to_vector()
corners =
grid
|> Iter.with_index()
|> Iter.flat_map(fn (row, line) ->
line
|> Iter.with_index()
|> Iter.filter(fn (_, symbol) -> symbol == "+")
|> Iter.map(fn (column, _) -> (row, column))
end)
|> Iter.to_list()
corners
|> Iter.flat_map(fn top_left -> Iter.map(corners, &(top_left, &1)))
|> Iter.count_by(fn (top_left, bottom_right) -> is_rectangle(grid, top_left, bottom_right))
end
/// Whether `top_left` and `bottom_right` are opposite corners of a
/// rectangle: below and right of each other, the other two corners `+`, and
/// every side whole.
fn is_rectangle(
grid: Vector<Vector<String>>,
(top, left): (Int, Int),
(bottom, right): (Int, Int),
) -> Bool
bottom > top
and right > left
and Iter.all_match([(top, right), (bottom, left)], fn (row, column) ->
symbol_at(grid, row, column) == Some("+")
end)
and Iter.all_match([top, bottom], &is_line_across(grid, &1, left, right))
and Iter.all_match([left, right], &is_line_down(grid, &1, top, bottom))
end
/// Whether row `row` is a side from column `left` to column `right`.
fn is_line_across(grid: Vector<Vector<String>>, row: Int, left: Int, right: Int) -> Bool
Iter.all_match(left..=right, fn column -> symbol_at(grid, row, column) is Some("-" or "+"))
end
/// Whether column `column` is a side from row `top` to row `bottom`.
fn is_line_down(grid: Vector<Vector<String>>, column: Int, top: Int, bottom: Int) -> Bool
Iter.all_match(top..=bottom, fn row -> symbol_at(grid, row, column) is Some("|" or "+"))
end
/// The symbol at `row` and `column`, or `None` off the diagram: a line may
/// be shorter than the others.
fn symbol_at(grid: Vector<Vector<String>>, row: Int, column: Int) -> Maybe<String>
grid |> Vector.get(row)? |> Vector.get(column)
end
// FILE: rectangles_test.nomi
import rectangles
test "rectangles"
[
("no rows", [], 0),
("no columns", [""], 0),
("no rectangles", [" "], 0),
(
"one rectangle",
[
"+-+",
"| |",
"+-+",
],
1,
),
(
"two rectangles without shared parts",
[
" +-+",
" | |",
"+-+-+",
"| | ",
"+-+ ",
],
2,
),
(
"five rectangles with shared parts",
[
" +-+",
" | |",
"+-+-+",
"| | |",
"+-+-+",
],
5,
),
(
"rectangle of height 1 is counted",
[
"+--+",
"+--+",
],
1,
),
(
"rectangle of width 1 is counted",
[
"++",
"||",
"++",
],
1,
),
(
"1x1 square is counted",
[
"++",
"++",
],
1,
),
(
"only complete rectangles are counted",
[
" +-+",
" |",
"+-+-+",
"| | -",
"+-+-+",
],
1,
),
(
"rectangles can be of different sizes",
[
"+------+----+",
"| | |",
"+---+--+ |",
"| | |",
"+---+-------+",
],
3,
),
(
"corner is required for a rectangle to be complete",
[
"+------+----+",
"| | |",
"+------+ |",
"| | |",
"+---+-------+",
],
2,
),
(
"large input with many rectangles",
[
"+---+--+----+",
"| +--+----+",
"+---+--+ |",
"| +--+----+",
"+---+--+--+-+",
"+---+--+--+-+",
"+------+ | |",
" +-+",
],
60,
),
(
"rectangles must have four sides",
[
"+-+ +-+",
"| | | |",
"+-+-+-+",
" | | ",
"+-+-+-+",
"| | | |",
"+-+ +-+",
],
5,
),
]
|> subtests (description, lines, expected), description
assert rectangles.count(lines) == expected
end
endok rectangles (14 cases)
test result: ok. 14 passed, 0 failed
How it’s written
Section titled “How it’s written”- The diagram is a
Vectorof rows, each aVectorof one-grapheme strings, andsymbol_atreads a cell as aMaybe, so a line shorter than the others, as in “two rectangles without shared parts”, reads as no symbol rather than a trap. countlists every+once, pairs every corner with every other, and counts the pairs that are the top left and bottom right of a rectangle.is_rectangleasks that the second is below and right of the first, that the other two corners are+, and that the two rows and two columns between them are whole sides, each anIter.all_matchover the corners or the sides.is_line_acrossandis_line_downwalk one side and accept-or+along a row and|or+down a column, each symbol anistest whose pattern joins the two withor(symbol_at(grid, row, column) is Some("-" or "+")). A+in the middle of a side is where another line crosses it, which “rectangles must have four sides” and the large input rely on.- The 14 canonical cases are one
subteststable named by the description column, each diagram written one line per row so it reads as the picture.