Skip to content

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
end
  • The diagram is a Vector of rows, each a Vector of one-grapheme strings, and symbol_at reads a cell as a Maybe, so a line shorter than the others, as in “two rectangles without shared parts”, reads as no symbol rather than a trap.
  • count lists every + once, pairs every corner with every other, and counts the pairs that are the top left and bottom right of a rectangle. is_rectangle asks 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 an Iter.all_match over the corners or the sides.
  • is_line_across and is_line_down walk one side and accept - or + along a row and | or + down a column, each symbol an is test whose pattern joins the two with or (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 subtests table named by the description column, each diagram written one line per row so it reads as the picture.