Run-length encoding

A type-level compressor and decompressor: AAABCCXXXXXXY becomes 3AB2C6XY and turns back again.

The encoder takes a string of letters such as AAABCCXXXXXXY and returns its run-length encoded form, 3AB2C6XY. The decoder turns the encoded string back into the original. Run-length encoding is one of the simplest real compression schemes, and implementing both directions in the type system forces you to combine nearly every string-type technique: character-by-character template literal inference, string accumulators, tuple counters for counting runs, and a trick for converting a digit character back into a number of repetitions.

Detailed Explanation

Both directions, in one namespace:

namespace RLE {
  type Run<Ch extends string, Count extends 1[]> = Count['length'] extends 0 | 1
    ? Ch
    : `${Count['length']}${Ch}`
 
  export type Encode<
    S extends string,
    Prev extends string = '',
    Count extends 1[] = [],
    Acc extends string = '',
  > = S extends `${infer Ch}${infer Rest}`
    ? Ch extends Prev
      ? Encode<Rest, Prev, [...Count, 1], Acc>
      : Encode<Rest, Ch, [1], `${Acc}${Run<Prev, Count>}`>
    : `${Acc}${Run<Prev, Count>}`
 
  type Repeat<
    Ch extends string,
    N extends string,
    Acc extends string = '',
    Count extends 1[] = [],
  > = `${Count['length']}` extends N
    ? Acc
    : Repeat<Ch, N, `${Acc}${Ch}`, [...Count, 1]>
 
  export type Decode<
    S extends string,
    Acc extends string = '',
  > = S extends `${infer Ch}${infer Rest}`
    ? Ch extends `${number}`
      ? Rest extends `${infer Letter}${infer Tail}`
        ? Decode<Tail, `${Acc}${Repeat<Letter, Ch>}`>
        : Acc
      : Decode<Rest, `${Acc}${Ch}`>
    : Acc
}

Two independent machines, both driven by the same engine: the pattern `${infer Ch}${infer Rest}`. When two infer placeholders sit side by side in a template literal, the first matches exactly one character and the second swallows the remainder. That's the type-level equivalent of s[0] and s.slice(1), and it's how both Encode and Decode walk their input one character at a time.

Encoding: tracking the current run

Encode carries three pieces of state through the recursion:

• Prev: the character of the run currently being counted.
• Count: a tuple of 1s whose length is the run length so far (types can't do + 1, but appending to a tuple increments its length).
• Acc: the encoded output built up so far.

Each step peels off one character Ch and compares it to Prev:

• Same character (Ch extends Prev): the run continues. Push another 1 onto Count and move on; nothing is emitted yet.
• Different character: the previous run is over. Flush it into the accumulator via Run<Prev, Count>, then start a new run with Prev = Ch and Count = [1].

When the input is exhausted (the template pattern no longer matches), the final run is still in flight, so the base case flushes it one last time. Forgetting this final flush is the classic bug in run-length encoders, at the type level just as much as at runtime.

Tracing Encode<'AAAB...'> for the first few steps:

// step 1: Ch='A', Prev=''  → new run:   Prev='A', Count=[1],       Acc=''
// step 2: Ch='A', Prev='A' → continue:  Count=[1, 1]
// step 3: Ch='A', Prev='A' → continue:  Count=[1, 1, 1]
// step 4: Ch='B', Prev='A' → flush 'A': Acc='3A', Prev='B', Count=[1]

Run: formatting one run

type Run<Ch extends string, Count extends 1[]> = Count['length'] extends 0 | 1
  ? Ch
  : `${Count['length']}${Ch}`

Run-length encoding only writes the count when it's greater than 1. That's why B stays B instead of becoming 1B. The 0 case handles the very first flush: Encode starts with Prev = '' and Count = [], so Run<'', []> evaluates to '' and contributes nothing to the output. Embedding Count['length'] in a template literal converts the numeric literal to its string form: [1, 1, 1]['length'] is 3, so the run becomes '3A'.

Decoding: reading digits and re-inflating

Decode walks the encoded string with the same one-character pattern and asks a different question about each character: is it a digit?

[object Object]

`${number}` matches any string that looks like a number, so '3' extends $ is `true` while `'A' extends `${number} is false. On a digit, the next character is the letter to repeat, so a nested pattern pulls out Letter and Tail, and Repeat<Letter, Ch> expands the run. A plain letter (an implicit count of 1) is copied through unchanged.

Repeat: counting up to a digit string

There's a subtle problem inside Repeat: the count arrives as the string '3', not the number 3, and there's no built-in string-to-number conversion. The solution turns the comparison around. Instead of converting the target down to a number, it converts the running counter up to a string:

[object Object]

Each iteration appends one Ch to the accumulator and one 1 to the counter tuple; when the stringified counter length equals the digit N, the accumulated string is done. Repeat<'X', '6'> runs six iterations and produces 'XXXXXX'.

Edge cases the tests cover

• Single-character runs in both directions: B and Y must encode without a 1 prefix, and decode back as-is.
• The trailing run (Y at the end of AAABCCXXXXXXY): only emitted by the base-case flush.
• A long run (XXXXXX → 6X): the tuple counter and Repeat must agree on the count in both directions, so Decode<Encode<S>> round-trips.
• One limitation worth knowing: Decode reads exactly one digit character per run, so it assumes single-digit counts. A run of 10 or more (encoded as 10A) would decode incorrectly. The tests never exceed nine repetitions, so this simple reader is enough here.

Both types are written tail-recursively: the recursive call is the entire branch result, with all state in accumulator parameters. They scale to long strings without hitting TypeScript's instantiation-depth limit.