Implementing Run-length Encoding

This teaching codec represents each run as a pair (symbol,count), where symbol is one Python character and count is a positive integer. AAABB becomes [("A",3),("B",2)]. A count and symbol stored as separate fields avoid ambiguity when input symbols themselves are digits. This is a structured in-memory representation, not a finished byte-file format.

Runs must be consecutive. In ABA, the two As are separate runs because a B lies between them. Start the current run from the first character, extend it while the next character matches, and emit the pair when the character changes. After the loop, emit the final pending run. An empty input has no first character, so handle it with an immediate empty-list result.

The decoder repeats each symbol by its count and joins the pieces. Validate that each symbol is a one-character string and each count is a positive integer; explicitly exclude booleans even though they are int subclasses. A decoder taking externally supplied runs should also limit the total expanded length before allocating each repetition.

The original function uses a maximum number of decoded characters, default 10,000. It accumulates the expected total and raises ValueError if a new run would exceed that limit. This protects the stated teaching exercise from a tiny run list requesting a huge allocation. A full storage codec also needs a defined byte encoding, count width, file validation and transport format; those concerns are not solved merely by returning Python tuples.

RLE is lossless because the sequence of symbols and counts reconstructs every character in order. It works well when long repeated runs are common, such as a simple monochrome image region. Alternating symbols create many short runs and can expand the representation. An encoder must not report success solely because it produced fewer Python list items than source characters; those objects have different storage costs.

For a toy model charging two storage units per run and one per original symbol, AAAAAABB has eight symbols and two runs, costing four units instead of eight. ABABABAB has eight runs and costs sixteen. State this model explicitly: it assumes counts and symbols fit the allotted units. Actual Python object overhead and a real file’s encoding would produce different byte counts.

def rle_encode(text):
    if not text:
        return []
    runs = []
    symbol, count = text[0], 1
    for character in text[1:]:
        if character == symbol:
            count += 1
        else:
            runs.append((symbol, count))
            symbol, count = character, 1
    runs.append((symbol, count))
    return runs

def rle_decode(runs, max_length=10000):
    if type(max_length) is not int or max_length < 0:
        raise ValueError('Use a non-negative integer size limit')
    parts = []
    total = 0
    for symbol, count in runs:
        if not isinstance(symbol, str) or len(symbol) != 1 or type(count) is not int or count <= 0:
            raise ValueError('Use one-character symbols and positive integer counts')
        total += count
        if total > max_length:
            raise ValueError('Decoded text exceeds the size limit')
        parts.append(symbol * count)
    return ''.join(parts)

text = 'AAAAAABB'
encoded = rle_encode(text)
print(encoded)
print(rle_decode(encoded))
print(rle_encode(''))
print(rle_encode('ABA'))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.