Canonical Code Words

Problem

Given symbols and their codeword lengths, assign canonical code words. Sort the pairs by (length, symbol), give the first code word that many zeros, and obtain each next code word by incrementing the previous code and shifting left by the increase in length. Return a dict mapping each symbol to its binary code string.

Hint

Canonical codes need only the sorted lengths to be reconstructed.

Test cases

case 1

in: [["a","b","c","d"],[1,2,3,3]]

expected: {"a":"0","b":"10","c":"110","d":"111"}

case 2

in: [["x","y"],[1,1]]

expected: {"x":"0","y":"1"}

case 3

in: [["a","b","c"],[2,2,2]]

expected: {"a":"00","b":"01","c":"10"}

case 4

in: [["z"],[1]]

expected: {"z":"0"}

case 5

in: [["d","b","a","c"],[3,2,1,3]]

expected: {"a":"0","b":"10","c":"110","d":"111"}

Starter codePython

def canonical_codes(symbols, lengths):
    # Your code here
    pass

5 test cases · run your code against them in the editor