Skip to content

Run-Length Encoding

Encode runs of repeated characters as a count and the character, and decode them back.

Adapted from Exercism’s problem specification (MIT). Listed under Encoding & Ciphers.

// FILE: run_length_encoding.nomi
//# Run-length encoding and decoding of text.

import std::regex.Regex

/// `text` with each run of a repeated character written as its length and
/// the character once. A character that is not repeated keeps no count.
pub fn encode(text: String) -> String
    text
    |> Iter.chunk_equal()
    |> Iter.map(encode_run)
    |> String.join()
end

fn encode_run(run: List<String>) -> String
    letter = List.first(run)!

    case Iter.count(run)
        1     -> letter
        count -> "${count}${letter}"
    end
end

/// The text `encode` was given for `encoded`: each character is repeated as
/// many times as the number before it says, or once when there is none.
pub fn decode(encoded: String) -> String
    encoded
    |> String.captures_all(Regex`(\d*)(\D)`)
    |> Iter.map(fn (count, letter) ->
        times =
            String.to_int(count)
            |> Maybe.flat_map(NonNegativeInt.try_from)
            |> Maybe.with_default(1)

        String.repeat(letter, times)
    end)
    |> String.join()
end

// FILE: run_length_encoding_test.nomi
import run_length_encoding

test "run-length encode a string"
    [
        ("empty string",                                     "",          ""),
        ("single characters only are encoded without count", "XYZ",       "XYZ"),
        ("string with no single characters",                 "AABBBCCCC", "2A3B4C"),
        (
            "single characters mixed with repeated characters",
            "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB",
            "12WB12W3B24WB",
        ),
        ("multiple whitespace mixed in string", "  hsqq qww  ", "2 hs2q q2w2 "),
        ("lowercase characters",                "aabbbcccc",    "2a3b4c"),
    ]
    |> subtests (description, text, expected), description
        assert run_length_encoding.encode(text) == expected
    end
end

test "run-length decode a string"
    [
        ("empty string",                     "",       ""),
        ("single characters only",           "XYZ",    "XYZ"),
        ("string with no single characters", "2A3B4C", "AABBBCCCC"),
        (
            "single characters with repeated characters",
            "12WB12W3B24WB",
            "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB",
        ),
        ("multiple whitespace mixed in string", "2 hs2q q2w2 ", "  hsqq qww  "),
        ("lowercase string",                    "2a3b4c",       "aabbbcccc"),
    ]
    |> subtests (description, encoded, expected), description
        assert run_length_encoding.decode(encoded) == expected
    end
end

test "encode and then decode"
    text = "zzz ZZ  zZ"

    assert text |> run_length_encoding.encode() |> run_length_encoding.decode() == text
end
  • encode is Iter.chunk_equal on the string’s graphemes, which cuts them into runs of one character, then each run written out by encode_run, then String.join.
  • decode reads the runs with String.captures_all(Regex`(\d*)(\D)`): an optional count, then one character. The literal’s type gives each match as a (String, String), since both groups take part in every match, so a destructuring lambda repeats the character count times, or once when the count group matched empty. The other way is an Iter.reduce over graphemes that threads (count, text) and builds the count digit by digit; the pattern is clearer because it states the encoded format in one line, where the reducer spreads it over a tuple accumulator and an if count == 0 fallback. The cost is that \D matches one code point, not one grapheme, so a run of a character written with a combining mark would decode wrongly; the canonical cases are all single code points.
  • Each canonical group is a test named by the group’s description, holding one subtests table; the round-trip case is a plain test.
  • A run from Iter.chunk_equal is never empty, so encode_run takes its letter with List.first(run)!, which traps rather than inventing a letter if that ever failed.