String to integer (atoi) and run-length encoding

String to integer, often called atoi after the C function, means reading the number at the start of a piece of text: skip leading spaces, accept one sign, read digits until the first other character, and clamp the value to the 32-bit range instead of letting it overflow. Run-length encoding stores a string as runs, each a letter and how many times it repeats, so aaabcc becomes a3bc2. Both are simulations whose difficulty lies in the edge cases: a number or a count with many digits, a value past the limit, a sign with nothing after it. This lesson states both problems, shows where the direct code breaks at the stated sizes, and what to notice before writing the loops.

Two problems on a meter’s data

Problem A: string to integer. A smart-meter app receives readings typed by people. Write parse_clamped(s): skip leading spaces, read at most one + or -, then the ASCII digits that follow, and stop at the first other character. Return the value clamped to −2³¹ … 2³¹ − 1, or 0 if no digit follows. Limits: 0 ≤ len(s) ≤ 10⁵.

• " -0042 kWh" gives −42, and "+-12" gives 0, because the second sign is not a digit.
• "9999999999" gives 2,147,483,647, and " + 7" gives 0: a space after the sign ends the number.

Problem B: run-length encoding. The meter’s sensors report status letters, sent run-length encoded: each run is its letter followed by its length, which is left out when it is 1. Write rle_decode(code), and compress(chars), which rewrites a list of letters in place with its encoding and returns the new length. Counts can have several digits, and runs can be 10⁵ letters long.

• "a3bc2" decodes to "aaabcc", and "x12" to twelve x’s.
• compress(list("aaabcc")) returns 5, the list starting a3bc2; compress(list("abc")) returns 3.

The direct code, and the inputs that break it

The first idea for problem A reads all the digits into one variable and clamps at the end. A reading of 10⁵ digits overflows any fixed-size integer long before the end, and a 64-bit variable silently wraps: 18446744073709551621, which is 2⁶⁴ + 5, comes out as 5. Python’s integers never overflow, but int() refuses more than 4,300 digits by default, the limit CPython sets on decimal conversion. For problem B, reading each digit as a separate count turns x12 into one x.

# The direct versions of both problems, and the inputs that break them.
LOW, HIGH = -(2**31), 2**31 - 1


def wrap64(x):
    """What a signed 64-bit variable holds after x overflows it (Java's long, Go's int64)."""
    x %= 2**64
    return x - 2**64 if x >= 2**63 else x


def parse_then_clamp(s, wrap):
    """Read the number into one variable and clamp at the end; wrap=True imitates a 64-bit variable."""
    i = 0
    while i < len(s) and s[i] == " ":
        i += 1
    sign = -1 if i < len(s) and s[i] == "-" else 1
    if i < len(s) and s[i] in "+-":
        i += 1
    value = 0
    while i < len(s) and "0" <= s[i] <= "9":
        value = value * 10 + int(s[i])
        if wrap:
            value = wrap64(value)
        i += 1
    return min(max(sign * value, LOW), HIGH)


for reading in ["  -0042 kWh", "9999999999", "18446744073709551621 kWh"]:
    print(f"{reading!r:28} 64-bit: {parse_then_clamp(reading, True):>11}   exact: {parse_then_clamp(reading, False):>11}")

try:
    int("7" * 5000)
except ValueError as e:
    print(f"\nint() on 5,000 digits: ValueError: {str(e).split(';')[0]}")


def decode_one_digit(code):
    """Treats every digit as a whole count, so a count of 12 becomes a 1 and then a 2."""
    out = []
    for c in code:
        if c.isdigit():
            out.append(out[-1] * (int(c) - 1))
        else:
            out.append(c)
    return "".join(out)


print(f"\none digit per count: 'a3bc2' -> {decode_one_digit('a3bc2')!r}, 'x12' -> {decode_one_digit('x12')!r}")

'  -0042 kWh'                64-bit:         -42   exact:         -42
'9999999999'                 64-bit:  2147483647   exact:  2147483647
'18446744073709551621 kWh'   64-bit:           5   exact:  2147483647

int() on 5,000 digits: ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 5000 digits

one digit per count: 'a3bc2' -> 'aaabcc', 'x12' -> 'x'

What to notice

In problem A, decide the clamp before each digit is added, with a comparison that never leaves the 32-bit range: then the remaining digits cannot matter. In problem B, a count is a number like A’s, accumulated digit by digit. And the encoding of a run is never longer than the run, so the encoded letters can be written over the input as it is read.

Parsing, step by step, with an exact overflow check Pro: opens with a Pro, Premium or Ultimate pass