Skip to content

Transpose

Transpose lines of text, padding short lines on the left of a column with spaces and never on the right.

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

// FILE: transpose.nomi
//# Transposes lines of text, rows into columns.

/// The lines of `lines` read down its columns: the nth line of the result is
/// the nth character of each line. A line shorter than one below it is padded
/// with spaces on the right first, so a character never moves left; nothing
/// pads past the last line that reaches a column.
pub fn transpose(lines: List<String>) -> List<String>
    lines
    |> padded()
    |> Iter.transpose()
    |> Iter.map(String.join)
    |> Iter.to_list()
end

/// Each line padded with spaces on the right to the width of the longest line
/// from it to the end. The widths never grow down the lines, so the lines
/// that reach a column are always the first ones.
fn padded(lines: List<String>) -> List<String>
    (_width, rows) =
        lines
        |> Iter.reverse()
        |> Iter.map_reduce(0, fn width, line ->
            width = Int.max(width, String.length(line))
            (width, String.pad_end(line, width))
        end)

    Iter.reverse(rows)
end

// FILE: transpose_test.nomi
import transpose.transpose

test "transpose"
    [
        ("empty string",               [],             []),
        ("two characters in a row",    ["A1"],         ["A", "1"]),
        ("two characters in a column", ["A", "1"],     ["A1"]),
        ("simple",                     ["ABC", "123"], ["A1", "B2", "C3"]),
        (
            "single line",
            ["Single line."],
            ["S", "i", "n", "g", "l", "e", " ", "l", "i", "n", "e", "."],
        ),
        (
            "first line longer than second line",
            ["The fourth line.", "The fifth line."],
            [
                "TT",
                "hh",
                "ee",
                "  ",
                "ff",
                "oi",
                "uf",
                "rt",
                "th",
                "h ",
                " l",
                "li",
                "in",
                "ne",
                "e.",
                ".",
            ],
        ),
        (
            "second line longer than first line",
            ["The first line.", "The second line."],
            [
                "TT",
                "hh",
                "ee",
                "  ",
                "fs",
                "ie",
                "rc",
                "so",
                "tn",
                " d",
                "l ",
                "il",
                "ni",
                "en",
                ".e",
                " .",
            ],
        ),
        (
            "mixed line length",
            ["The longest line.", "A long line.", "A longer line.", "A line."],
            [
                "TAAA",
                "h   ",
                "elll",
                " ooi",
                "lnnn",
                "ogge",
                "n e.",
                "glr",
                "ei ",
                "snl",
                "tei",
                " .n",
                "l e",
                "i .",
                "n",
                "e",
                ".",
            ],
        ),
        (
            "square",
            ["HEART", "EMBER", "ABUSE", "RESIN", "TREND"],
            ["HEART", "EMBER", "ABUSE", "RESIN", "TREND"],
        ),
        (
            "rectangle",
            ["FRACTURE", "OUTLINED", "BLOOMING", "SEPTETTE"],
            ["FOBS", "RULE", "ATOP", "CLOT", "TIME", "UNIT", "RENT", "EDGE"],
        ),
        (
            "triangle",
            ["T", "EE", "AAA", "SSSS", "EEEEE", "RRRRRR"],
            ["TEASER", " EASER", "  ASER", "   SER", "    ER", "     R"],
        ),
        (
            "jagged triangle",
            ["11", "2", "3333", "444", "555555", "66666"],
            ["123456", "1 3456", "  3456", "  3 56", "    56", "    5"],
        ),
    ]
    |> subtests (description, lines, expected), description
        assert transpose(lines) == expected
    end
end
  • Each line is padded on the right to the width of the longest line from it to the end. After that, the rows that reach column i are always a prefix of the rows, so output line i is every row’s character at i where it has one, which is what Iter.transpose gives: a short row adds nothing past its end. No row needs trailing-space bookkeeping.
  • The padding widths are a running maximum from the bottom up: one Iter.map_reduce over the reversed lines, whose state is the width so far and whose output is each padded line. The rows come out bottom first, so one Iter.reverse puts them back in order. Iter.scan over the widths, reversed and zipped back with the lines, is the other spelling; it needs a reverse and a zip where map_reduce needs one reverse.
  • The padded lines go to Iter.transpose as they are: a String is an Iter of its graphemes, so each column comes back as a List<String> of characters, which String.join puts back together. Nothing is indexed.
  • One subtests table: the cases share one shape, and a table of string lists is shallow enough for nomi fmt to keep.