Algorithm dossier

  • Category: Compression
  • Worst-case complexity: O(n)
  • Approach: Iterative
  • Data structure: No DS
  • First formalised: 1960s

Why this snippet is Run-Length Encoding

Why run-length encoding. Single pass, single accumulator. Track the previous char p and a running count k; on a switch, flush (k, p) into the output. The structure — "count then symbol" — is the unambiguous fingerprint. Where it shines. Long runs of identical bytes (bitmap headers, simple line art) compress 50:1 or better. On random data RLE *expands* the input; that's why modern formats use entropy coding instead.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.