Bencoding

Every part of BitTorrent that stores or ships metadata — the .torrent file, tracker responses, DHT messages — speaks bencoding. Bram Cohen designed it in 2001, pre-JSON, and it has exactly four types and one killer property: for any value there is exactly one valid encoding. Hold that thought — it is the reason half of the rules below exist.

Read the dict example byte by byte: d opens the dict, 3:age is the first key (a bencoded string), i42e is its value, 4:name is the second key, 5:Alice is its value — note that the value carries its own 5: length prefix; it is a complete bencoded string in its own right — and the final e closes the dict. Everything nests: a value can be a list of dicts of lists.

The strict rules:

• Integers are base-10 with no leading zeros (i03e is invalid; zero is exactly i0e). Negatives are fine (i-7e), but i-0e is forbidden.
• String lengths count bytes, not characters. Bencoded strings are binary-safe: a 20-byte SHA-1 digest is 20: followed by 20 raw bytes, printable or not.
• Dict keys must be strings, and must appear sorted ascending by raw byte value: cow before spam — and, because Z is 0x5A while a is 0x61, Zebra sorts before apple.

Why so strict? One value, one encoding

JSON will happily serialize the same object a dozen different ways — key order, whitespace, escape choices. Bencoding forbids every one of those degrees of freedom on purpose. BitTorrent identifies a torrent by the SHA-1 hash of its bencoded info dict (the infohash — next lesson). If two clients could encode the same dict differently, they would compute different hashes for the same data and join different swarms, never finding each other. Mandatory key sorting and the no-leading-zeros rule make the encoding canonical, and canonical bytes are what make a hash usable as an identifier.

Decoding: dispatch on the first byte

The format is self-describing — peek one byte to know what follows:

Give every helper the same contract: take (data, i), return (value, next_index). Lists and dicts then become loops — keep decoding elements until the byte at the current index is the closing e, then skip it. Dicts decode a key (always a string), then a value, pair after pair.

The classic trap

Do not scan for delimiters. Searching for the e that ends an integer happens to work; applying the same idea to anything containing strings is a disaster, because string bodies may contain e, :, digits — anything. 12:i3e:spam:egg is one 12-byte string, not an integer followed by garbage. Strings have no terminator at all: read the length before the :, then consume exactly that many bytes. This is also why the (value, next_index) shape matters — bencoded data only makes sense as a strict left-to-right walk with an explicit cursor.

Your exercise

Implement the ENCODE/DECODE commands from the starter. Two mistakes the grader catches, straight from the real tests:

1. Sloppy output formatting on DECODE. DECODE li1ei2ei3ee must print exactly [1, 2, 3] — comma and space — and DECODE d3:agei42e4:name5:Alicee must print {'age': 42, 'name': 'Alice'}: single-quoted strings, : between key and value, keys in sorted order. Printing [1,2,3] or double quotes fails the tests.
2. Non-recursive encoding. The hidden test ENCODE dict {"a":1,"b":[1,2]} expects d1:ai1e1:bli1ei2eee — the list value must be bencoded inside the dict. If your encoder only handles flat values, or forgets that dict keys get a length prefix too, this test fails.