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
endok run-length encode a string (6 cases)
ok run-length decode a string (6 cases)
ok encode and then decode
test result: ok. 13 passed, 0 failed
How it’s written
Section titled “How it’s written”encodeisIter.chunk_equalon the string’s graphemes, which cuts them into runs of one character, then each run written out byencode_run, thenString.join.decodereads the runs withString.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 charactercounttimes, or once when the count group matched empty. The other way is anIter.reduceover 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 anif count == 0fallback. The cost is that\Dmatches 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
subteststable; the round-trip case is a plain test. - A run from
Iter.chunk_equalis never empty, soencode_runtakes its letter withList.first(run)!, which traps rather than inventing a letter if that ever failed.