<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P025-run-length-compressor/ | updated: 2026-10-05 -->

# P025 Run-length compressor

Compresses a line of text by writing each long run of one character as ~count~character - only where that is shorter - with ~~ for a ~ in the text, so digits need no escaping; expands it back with the position and reason of any error, gives the compression ratio, and checks that every compressed text expands to the original.

EML-P project `projects/run-length-compressor` in the EML language repo: 3 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/run-length-compressor` runs it and `eml project verify projects/run-length-compressor` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: run-length-encoder (https://efficientnewlanguage.org/cases/036-run-length-encoder/), run-length-encoding (https://efficientnewlanguage.org/cases/149-run-length-encoding/), run-length-escaping (https://efficientnewlanguage.org/cases/208-run-length-escaping/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
x
0
5
1

2

1
ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababc
aaaaaaaaaa
2
~
2
ab~
2
a~b
2
~12c
2
~0~a
2
~012~a
2
~12345~a
2
~5~
2
~9999~a~9999~b
2
~~
4
```

Screen:

```text

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> x
Pick 1, 2, 3 or 4.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 0
Pick 1, 2, 3 or 4.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 5
Pick 1, 2, 3 or 4.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 1
text> 
Cancelled.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> 
Cancelled.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 1
text> ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababc
That is 301 characters; at most 300 fit here. Type it again, or nothing to cancel.
text> aaaaaaaaaa
Compressed: ~10~a
10 characters -> 5 (50%).
Written as counts: 'a' x 10.
Expanded again, it matches the original.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~
Position 1: a '~' at the end needs a second '~' or a count after it.
  ~
  ^

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ab~
Position 3: a '~' at the end needs a second '~' or a count after it.
  ab~
    ^

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> a~b
Position 2: a '~' must be followed by a second '~' or a count.
  a~b
   ^

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~12c
Position 1: the count after this '~' needs a closing '~'.
  ~12c
  ^

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~0~a
Position 1: a count is a whole number from 1 to 9999, written without leading zeros.
  ~0~a
  ^

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~012~a
Position 1: a count is a whole number from 1 to 9999, written without leading zeros.
  ~012~a
  ^

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~12345~a
Position 1: a count is a whole number from 1 to 9999, written without leading zeros.
  ~12345~a
  ^

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~5~
Position 1: the run that starts here has no character to repeat.
  ~5~
  ^

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~9999~a~9999~b
That would expand to more than 5000 characters.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~~
Expanded: ~
2 characters -> 1.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 4
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
2
~12~WB~12~WBBB~24~WB~14~W
1
Room 101, 2nd floor
1
a~b~c
1
3333333 and ~~~~~ and ......
3
2
x~3~3y
4
```

Screen:

```text

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 1
text> WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Compressed: ~12~WB~12~WBBB~24~WB~14~W
67 characters -> 25 (37%).
Written as counts: 'W' x 12, 'W' x 12, 'W' x 24 and 'W' x 14.
Expanded again, it matches the original.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> ~12~WB~12~WBBB~24~WB~14~W
Expanded: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
25 characters -> 67.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 1
text> Room 101, 2nd floor
Compressed: Room 101, 2nd floor
19 characters -> 19 (100%).
No run is long enough to write as a count.
Expanded again, it matches the original.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 1
text> a~b~c
Compressed: a~~b~~c
5 characters -> 7 (140%).
No run is long enough to write as a count.
That is longer than the text: each '~' in it is written as '~~'.
Expanded again, it matches the original.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 1
text> 3333333 and ~~~~~ and ......
Compressed: ~7~3 and ~5~~ and ~6~.
28 characters -> 22 (79%).
Written as counts: '3' x 7, '~' x 5 and '.' x 6.
Expanded again, it matches the original.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 3
- A run of one character is written ~count~character when that is
  shorter than writing it out: aaaaaa becomes ~6~a.
- A ~ in the text is written ~~.
- Everything else stays as it is. Digits need no escaping, because a
  count only ever comes right after a ~: a3 stays a3, and 3333333
  becomes ~7~3.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 2
compressed> x~3~3y
Expanded: x333y
6 characters -> 5.

== Run-length compressor ==
1) compress  2) expand  3) the format  4) quit
choice> 4
Bye.
```

## Modules

### main.eml

```eml
# P025 run-length compressor: runs of one character written as counts, with an
# escape for the "~" the format uses, both ways, and a check that every
# compressed text expands back to the original.
import rle
import text

300 => longest_text
5000 => longest_expansion

def ask_text(prompt, most):
    # A line of at most `most` characters, kept as typed, spaces included;
    # an empty line cancels and gives "".
    while True:
        input(prompt) => s
        if s == "" or len(s) <= most:
            return s
        ("That is " + str(len(s)) + " characters; at most " + str(most) + " fit here. Type it again, or nothing to cancel.") ^0

def compress_one(s):
    rle.compress(s) => c
    ("Compressed: " + c) ^0
    (text.plural(len(s), "character") + " -> " + str(len(c)) + " (" + str(text.percent(len(c), len(s))) + "%).") ^0
    rle.counted_runs(s) => counted
    if len(counted) == 0:
        "No run is long enough to write as a count." ^0
    else:
        [] => named
        for r in counted:
            if len(named) < 5:
                named + ["'" + r[0] + "' x " + str(r[1])] => named
        if len(counted) > 5:
            named + [str(len(counted) - 5) + " more"] => named
        ("Written as counts: " + text.listed(named) + ".") ^0
    if len(c) > len(s):
        "That is longer than the text: each '~' in it is written as '~~'." ^0
    rle.expand(c, longest_expansion) => back
    if back[0] == "ok" and back[1] == s:
        "Expanded again, it matches the original." ^0
    else:
        "Expanded again, it does NOT match the original." ^0

def expand_one(s):
    rle.expand(s, longest_expansion) => r
    if r[0] == "ok":
        ("Expanded: " + r[1]) ^0
        (text.plural(len(s), "character") + " -> " + str(len(r[1])) + ".") ^0
    elif r[0] == "long":
        ("That would expand to more than " + str(longest_expansion) + " characters.") ^0
    else:
        ("Position " + str(r[1]) + ": " + r[2]) ^0
        ("  " + s) ^0
        ("  " + text.spaces(r[1] - 1) + "^") ^0

True => running
while running:
    "" ^0
    "== Run-length compressor ==" ^0
    "1) compress  2) expand  3) the format  4) quit" ^0
    text.trim(input("choice> ")) => choice
    if choice == "1":
        ask_text("text> ", longest_text) => s
        if s == "":
            "Cancelled." ^0
        else:
            compress_one(s)
    elif choice == "2":
        ask_text("compressed> ", 2 * longest_text) => s
        if s == "":
            "Cancelled." ^0
        else:
            expand_one(s)
    elif choice == "3":
        "- A run of one character is written ~count~character when that is" ^0
        "  shorter than writing it out: aaaaaa becomes ~6~a." ^0
        "- A ~ in the text is written ~~." ^0
        "- Everything else stays as it is. Digits need no escaping, because a" ^0
        "  count only ever comes right after a ~: a3 stays a3, and 3333333" ^0
        "  becomes ~7~3." ^0
    elif choice == "4":
        False => running
    else:
        "Pick 1, 2, 3 or 4." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import rle
import text
longest_text = 300
longest_expansion = 5000

def ask_text(prompt, most):
    while True:
        s = input(prompt)
        if s == "" or len(s) <= most:
            return s
        print("That is " + str(len(s)) + " characters; at most " + str(most) + " fit here. Type it again, or nothing to cancel.")

def compress_one(s):
    c = rle.compress(s)
    print("Compressed: " + c)
    print(text.plural(len(s), "character") + " -> " + str(len(c)) + " (" + str(text.percent(len(c), len(s))) + "%).")
    counted = rle.counted_runs(s)
    if len(counted) == 0:
        print("No run is long enough to write as a count.")
    else:
        named = []
        for r in counted:
            if len(named) < 5:
                named = named + ["'" + r[0] + "' x " + str(r[1])]
        if len(counted) > 5:
            named = named + [str(len(counted) - 5) + " more"]
        print("Written as counts: " + text.listed(named) + ".")
    if len(c) > len(s):
        print("That is longer than the text: each '~' in it is written as '~~'.")
    back = rle.expand(c, longest_expansion)
    if back[0] == "ok" and back[1] == s:
        print("Expanded again, it matches the original.")
    else:
        print("Expanded again, it does NOT match the original.")

def expand_one(s):
    r = rle.expand(s, longest_expansion)
    if r[0] == "ok":
        print("Expanded: " + r[1])
        print(text.plural(len(s), "character") + " -> " + str(len(r[1])) + ".")
    elif r[0] == "long":
        print("That would expand to more than " + str(longest_expansion) + " characters.")
    else:
        print("Position " + str(r[1]) + ": " + r[2])
        print("  " + s)
        print("  " + text.spaces(r[1] - 1) + "^")

running = True
while running:
    print("")
    print("== Run-length compressor ==")
    print("1) compress  2) expand  3) the format  4) quit")
    choice = text.trim(input("choice> "))
    if choice == "1":
        s = ask_text("text> ", longest_text)
        if s == "":
            print("Cancelled.")
        else:
            compress_one(s)
    elif choice == "2":
        s = ask_text("compressed> ", 2 * longest_text)
        if s == "":
            print("Cancelled.")
        else:
            expand_one(s)
    elif choice == "3":
        print("- A run of one character is written ~count~character when that is")
        print("  shorter than writing it out: aaaaaa becomes ~6~a.")
        print("- A ~ in the text is written ~~.")
        print("- Everything else stays as it is. Digits need no escaping, because a")
        print("  count only ever comes right after a ~: a3 stays a3, and 3333333")
        print("  becomes ~7~3.")
    elif choice == "4":
        running = False
    else:
        print("Pick 1, 2, 3 or 4.")
print("Bye.")
```

### rle.eml

```eml
# P025 run-length compressor - the format, both ways.
#
# A run of one character is written ~count~character when that is shorter
# than writing the run out; a "~" in the text is written "~~"; everything else
# is written as it is. A count only ever comes right after a "~", so digits in
# the text need no escaping - the ambiguity a plain "a3b2" format has with
# digits does not arise.

"0123456789" => digits

def runs(s):
    # [[character, count], ...], one for each run of a single character.
    [] => out
    0 => i
    while i < len(s):
        s[i] => c
        1 => n
        while i + n < len(s) and s[i + n] == c:
            n + 1 => n
        out + [[c, n]] => out
        i + n => i
    return out

def as_count(c, n):
    # True when ~n~c is shorter than the run written out ("~" is two each).
    n => written
    if c == "~":
        2 * n => written
    return len(str(n)) + 3 < written

def compress(s):
    "" => out
    for r in runs(s):
        if as_count(r[0], r[1]):
            out + "~" + str(r[1]) + "~" + r[0] => out
        elif r[0] == "~":
            out + "~~" * r[1] => out
        else:
            out + r[0] * r[1] => out
    return out

def counted_runs(s):
    # The runs compress() writes as counts.
    [] => out
    for r in runs(s):
        if as_count(r[0], r[1]):
            out + [r] => out
    return out

def expand(s, limit):
    # ["ok", text], or ["error", position, reason] with the position counted
    # from 1, or ["long"] when the text would pass limit characters.
    "" => out
    0 => i
    while i < len(s):
        s[i] => c
        if c != "~":
            out + c => out
            i + 1 => i
        elif i + 1 >= len(s):
            return ["error", i + 1, "a '~' at the end needs a second '~' or a count after it."]
        elif s[i + 1] == "~":
            out + "~" => out
            i + 2 => i
        elif s[i + 1] in digits:
            i + 1 => j
            0 => count
            while j < len(s) and s[j] in digits:
                if j - i <= 5:
                    count * 10 + int(s[j]) => count
                j + 1 => j
            if j >= len(s) or s[j] != "~":
                return ["error", i + 1, "the count after this '~' needs a closing '~'."]
            if s[i + 1] == "0" or j - i - 1 > 4:
                return ["error", i + 1, "a count is a whole number from 1 to 9999, written without leading zeros."]
            if j + 1 >= len(s):
                return ["error", i + 1, "the run that starts here has no character to repeat."]
            if len(out) + count > limit:
                return ["long"]
            out + s[j + 1] * count => out
            j + 2 => i
        else:
            return ["error", i + 1, "a '~' must be followed by a second '~' or a count."]
        if len(out) > limit:
            return ["long"]
    return ["ok", out]
```

Python projection of rle.eml:

```python
digits = "0123456789"

def runs(s):
    out = []
    i = 0
    while i < len(s):
        c = s[i]
        n = 1
        while i + n < len(s) and s[i + n] == c:
            n = n + 1
        out = out + [[c, n]]
        i = i + n
    return out

def as_count(c, n):
    written = n
    if c == "~":
        written = 2 * n
    return len(str(n)) + 3 < written

def compress(s):
    out = ""
    for r in runs(s):
        if as_count(r[0], r[1]):
            out = out + "~" + str(r[1]) + "~" + r[0]
        elif r[0] == "~":
            out = out + "~~" * r[1]
        else:
            out = out + r[0] * r[1]
    return out

def counted_runs(s):
    out = []
    for r in runs(s):
        if as_count(r[0], r[1]):
            out = out + [r]
    return out

def expand(s, limit):
    out = ""
    i = 0
    while i < len(s):
        c = s[i]
        if c != "~":
            out = out + c
            i = i + 1
        elif i + 1 >= len(s):
            return ["error", i + 1, "a '~' at the end needs a second '~' or a count after it."]
        elif s[i + 1] == "~":
            out = out + "~"
            i = i + 2
        elif s[i + 1] in digits:
            j = i + 1
            count = 0
            while j < len(s) and s[j] in digits:
                if j - i <= 5:
                    count = count * 10 + int(s[j])
                j = j + 1
            if j >= len(s) or s[j] != "~":
                return ["error", i + 1, "the count after this '~' needs a closing '~'."]
            if s[i + 1] == "0" or j - i - 1 > 4:
                return ["error", i + 1, "a count is a whole number from 1 to 9999, written without leading zeros."]
            if j + 1 >= len(s):
                return ["error", i + 1, "the run that starts here has no character to repeat."]
            if len(out) + count > limit:
                return ["long"]
            out = out + s[j + 1] * count
            i = j + 2
        else:
            return ["error", i + 1, "a '~' must be followed by a second '~' or a count."]
        if len(out) > limit:
            return ["long"]
    return ["ok", out]
```

### text.eml

```eml
# P025 run-length compressor - small text and number helpers. The interpreter
# that checks every session does not run string methods yet, so these are
# written out here.

def trim(s):
    # s without the spaces at either end.
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def spaces(n):
    return " " * n

def quotient(a, b):
    # a divided by b, rounded down, for a >= 0 and b > 0; exact for the
    # sizes used here.
    return int((a - a % b) / b)

def percent(part, whole):
    # part as a whole-number percentage of whole, halves rounded up.
    return quotient(200 * part + whole, 2 * whole)

def listed(items):
    # ["a", "b", "c"] as "a, b and c".
    "" => out
    0 => i
    while i < len(items):
        if i > 0 and i == len(items) - 1:
            out + " and " => out
        elif i > 0:
            out + ", " => out
        out + items[i] => out
        i + 1 => i
    return out

def plural(n, word):
    if n == 1:
        return "1 " + word
    return str(n) + " " + word + "s"
```

Python projection of text.eml:

```python
def trim(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def spaces(n):
    return " " * n

def quotient(a, b):
    return int((a - a % b) / b)

def percent(part, whole):
    return quotient(200 * part + whole, 2 * whole)

def listed(items):
    out = ""
    i = 0
    while i < len(items):
        if i > 0 and i == len(items) - 1:
            out = out + " and "
        elif i > 0:
            out = out + ", "
        out = out + items[i]
        i = i + 1
    return out

def plural(n, word):
    if n == 1:
        return "1 " + word
    return str(n) + " " + word + "s"
```

## README

# P025 - Run-length compressor

Compresses a line of text by writing each long run of one character as a
count, expands such text back, and shows what the compression saved. Every
compressed text is expanded again on the spot and compared with the original.

- `main.eml` - the menu, the questions and their checks, and what the screen
  shows
- `rle.eml` - the format: runs, compressing, and expanding with errors
- `text.eml` - trimming, spaces, a percentage rounded half up, lists in words

The format:

- A run of one character is written `~count~character` when that is shorter
  than writing it out: `aaaaaa` becomes `~6~a`. A run of 4 stays as it is
  (`~4~a` is no shorter); a run of 5 or more becomes a count.
- A `~` in the text is written `~~`, and a run of three or more `~` becomes a
  count too: `~~~~~` is `~5~~`.
- Everything else stays as it is. Digits need no escaping, because a count
  only ever comes right after a `~`: `a3` stays `a3`, and `3333333` becomes
  `~7~3`. A format that writes `a3b2` cannot tell a count from a digit in the
  text; the `~` before every count removes that ambiguity.

How each part works:

- Compressing splits the text into runs and writes each one the shorter way,
  so no other way of writing the same runs in this format is shorter.
- Expanding reads the text left to right. A `~` must be followed by a second
  `~` or by a count of 1 to 9999 (no leading zeros), a closing `~` and the
  character to repeat; anything else is an error, reported with its position
  and a caret under it. An expansion longer than 5000 characters is refused
  before it is built.
- The ratio is the compressed length as a percentage of the original, halves
  rounded up.

What is checked: a text to compress is 1 to 300 characters, a text to expand
1 to 600 (a compressed text is at most twice its original); a longer one is
asked for again, and an empty line cancels. A menu choice other than 1 to 4
is asked again.

Sessions: `sessions/basic.in` compresses the classic 67-character W/B line to
25 characters (37%) and expands it back, leaves `Room 101, 2nd floor` as it is
(100%), shows `a~b~c` growing to 140% because each `~` is written twice,
compresses runs of digits, `~` and `.`, shows the format, and expands
`x~3~3y`; `sessions/bad-input.in` types menu choices that are not 1 to 4,
empty texts that cancel, a text of 301 characters, and compressed texts with
a lone `~` at the end, a `~` before a letter, a count with no closing `~`,
counts of 0, 012 and 12345, a run with no character, an expansion of 19998
characters, and `~~`.

Built on the verified corpus cases `run-length-encoder` (runs counted while
walking the text), `run-length-encoding` (encoding, its inverse, and the round trip as the test) and
`run-length-escaping` (why digits in the text break a plain count format, and
what an explicit boundary fixes).