One wire, many labels

The dispatch radio carries one text field per run. Whatever the depot puts in it has to come back out as the same list of labels — including the labels that contain the character you were about to use as a separator.

The problem

A night dispatcher hands the radio operator the labels for tonight's parcels: hand-typed strings such as BAY-7 or fragile #2. The link carries exactly one text field, so the list travels as a single string, and the depot at the other end rebuilds it character for character.

Nothing cleans the labels first. A label may hold spaces, punctuation, a comma, a #, or nothing at all; the list may be empty. Joining on a comma dies the first night a label contains a comma, and it cannot tell a two-label list whose second label is empty from a one-label list.

Write one routine that runs both ways: pack takes the list and returns the wire string, unpack takes a wire string your packer produced and returns the list.

Input. mode — the string 'pack' or 'unpack'. payload — the list of labels when packing, the wire string when unpacking.

Output. The wire string, or the list of labels.

Example.

solve('pack', ['BAY-7', 'fragile #2', ''])  ->  '5#BAY-710#fragile #20#'
solve('unpack', '5#BAY-710#fragile #20#')   ->  ['BAY-7', 'fragile #2', '']

Each label travels as its length, a #, then the label. The second label contains a # of its own and it costs nothing, because the reader never searches for one.

A second example, where a label is disguised as a header:

solve('pack', ['12#34'])   ->  '5#12#34'
solve('unpack', '5#12#34') ->  ['12#34']

The reader takes the digits up to the first #, gets 5, then takes the next five characters whatever they look like.

Constraints.

• 0 <= len(labels) <= 10^4
• 0 <= len(label) <= 10^4, any printable characters
• every wire string passed to unpack was produced by your own pack

Hints

Approach

Brute force

Reserve # as the separator and escape it: double every # inside a label, join on a single #, un-double on the way back. Both directions stay one pass, O(L) over the total length L, so the cost is not time — it is a four-case state machine, one case of which is wrong the first time you write it.

The insight

A separator has to be escaped because the reader searches for it; a length header is never searched for, so nothing inside a label needs special treatment.

The reader's position is always known. It reads digits until the first #, and those digits cannot be mistaken for content because content has not started yet. Then it takes exactly that many characters — the label is consumed by counting, not scanning, so a #, a comma or a run of digits inside it is just data.

Algorithm

1. To pack, append each label's length in decimal, then #, then the label; an empty list gives the empty string.
2. To unpack, put the cursor at index 0.
3. Find the next # from the cursor; the digits before it are size.
4. Take the size characters after that # as one label.
5. Move the cursor past them and repeat until the wire is exhausted.

Complexity

Time O(L) in both directions, L being the total length of the labels plus their headers: each character is written once and read once. Space O(L) for the output, and O(1) beyond it.

Solution

"""One wire, many labels — length-prefixed framing, so no character is reserved."""


def pack(labels):
    """Each label becomes '<length>#<label>'; concatenating them loses nothing."""
    return "".join(f"{len(label)}#{label}" for label in labels)


def unpack(wire):
    labels = []
    cursor = 0
    while cursor < len(wire):
        # invariant: cursor sits on the first digit of a header, never inside a label
        divider = wire.index("#", cursor)
        size = int(wire[cursor:divider])
        start = divider + 1
        labels.append(wire[start:start + size])
        cursor = start + size
    return labels


def solve(mode, payload):
    return pack(payload) if mode == "pack" else unpack(payload)

TESTS = [
    (("pack", ["BAY-7", "fragile #2", ""]), "5#BAY-710#fragile #20#"),
    (("unpack", "5#BAY-710#fragile #20#"), ["BAY-7", "fragile #2", ""]),
    (("pack", ["12#34"]), "5#12#34"),
    (("unpack", "5#12#34"), ["12#34"]),
    (("pack", []), ""),
    (("unpack", ""), []),
    (("pack", ["", ""]), "0#0#"),
    (("unpack", "0#0#"), ["", ""]),
    (("pack", ["pallet 9, bay 2"]), "15#pallet 9, bay 2"),
    (("unpack", "15#pallet 9, bay 2"), ["pallet 9, bay 2"]),
]

Pitfalls

• Splitting the wire on #. The label 12#34 packs to 5#12#34, which splits into four pieces instead of two. The # terminates a header only; never look for it again.
• Dropping empty labels. ['a', ''] packs to 1#a0#. A decoder that skips a label of size 0 returns ['a'] — the same silent loss the comma join has.
• Advancing the cursor by size alone. The next header starts at hash_index + 1 + size; miss the header's own width and the decoder reads a length out of the tail of the previous label.

Variants

• The permissions desk — also one long string read in fixed-width pieces, but the pieces are searched for rather than framed and unpacked.