Length-prefixed encoding

When to use it

Use it when several strings must become one string and come back exactly, and any character may appear in them, so no dividing mark is safe.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

A sticker printer receives all its labels as one string. Each label is written as its length, then "#", then the text of the label. Return label number want, counting from 0.

Input
packed = "2##52#ok"
want = 1

Output
"ok"

The method

1. Start at the first character, in front of label number 0
2. Read the digits up to the next "#": that is the length
3. The label is exactly that many characters after the "#"
4. Not the one wanted: jump over it without reading it

The run, one moment at a time

1. Step 1. Reading starts at position 0, in front of label 0. The label wanted is number 1.

   packed: 2 # # 5 2 # o k  (i at 0)
   number: 0
   length: empty
   answer: empty
   

2. Step 2. From position 0 the digits run up to the "#" at position 1. They say 2, so label 0 is 2 characters long.

   packed: 2 # # 5 2 # o k  (i at 0, end at 1)
   number: 0
   length: 2
   answer: empty
   

3. Step 4. Label 0 is not the one wanted. Jump over its 2 characters, positions 2 to 3. One is a "#", which is no problem because it is never read. Label 1 starts at position 4.

   packed: 2 # # 5 2 # o k  (i at 4)
   number: 1
   length: empty
   answer: empty
   

4. Step 2. From position 4 the digits run up to the "#" at position 5. They say 2, so label 1 is 2 characters long.

   packed: 2 # # 5 2 # o k  (i at 4, end at 5)
   number: 1
   length: 2
   answer: empty
   

5. Step 3. Label 1 is the one wanted. Take exactly 2 characters after the "#", positions 6 to 7. The answer is "ok".

   packed: 2 # # 5 2 # o k  (start at 6)
   number: 1
   length: 2
   answer: ok
   

The code

The numbered comments are the steps of the method.

function solve(packed, want) {
  // 1. Start at the first character, in front of label number 0
  let i = 0;
  let number = 0;
  while (i < packed.length) {
    // 2. Read the digits up to the next "#": that is the length
    const end = packed.indexOf("#", i);
    const length = Number(packed.slice(i, end));
    // 3. The label is exactly that many characters after the "#"
    const start = end + 1;
    if (number === want) return packed.slice(start, start + length);
    // 4. Not the one wanted: jump over it without reading it
    i = start + length;
    number += 1;
  }
  // The string holds fewer labels than that.
  return "";
}

def solve(packed, want):
    # 1. Start at the first character, in front of label number 0
    i = 0
    number = 0
    while i < len(packed):
        # 2. Read the digits up to the next "#": that is the length
        end = packed.index("#", i)
        length = int(packed[i:end])
        # 3. The label is exactly that many characters after the "#"
        start = end + 1
        if number == want:
            return packed[start : start + length]
        # 4. Not the one wanted: jump over it without reading it
        i = start + length
        number += 1
    # The string holds fewer labels than that.
    return ""

How to spot it

Asked: Turn a list of strings into one string and back

The reader must know where each string ends. A length written in front says so, with no searching.

Given: The strings may contain any character at all

Any mark you put between strings can also appear inside one. A length cannot be confused with the contents.

Given: An empty string, and an empty list, must also come back exactly

A length of 0 is written like any other length. So an empty string is still written as something, and an empty list as nothing.

Limits: The reader gets only the one string, nothing else

Everything needed to split the text must be inside the text. The lengths are written in the text, in front of the strings.

Looks like it, but is not

• The text holds groups inside brackets, and a group can sit inside another group. Use Last-in, first-out stack. Groups that nest close in the opposite order to the one they opened in. Lengths suit pieces that stand in a row.
• A tree must be written as one string and built again from it. Use Preorder tree recursion. The pieces are not in a row: each node has children. The order of the visit, with a mark for a missing child, keeps the shape.

Cost and mistakes

Packing and unpacking copy each character once, so time grows with the total number of characters, written O(n). Skipping a string costs only the reading of its few digits. Extra space is those digits and one marker for each string.

Watch out

• Do not split the text at every "#". A "#" inside a string would cut it in two. Read the number, then count characters.
• A length can have several digits. Read all the digits up to the "#", not only the first one: 12# means that twelve characters follow.

In the 150

One problem of the 150 uses it. Naming them gives their method away, so the list is folded.