Shannon Code Length

Problem

Return the Shannon code length ceil(-log2(p)) for every probability in probs. A probability of 1.0 yields length 0.

Hint

Shannon lengths satisfy the Kraft inequality, which is exactly what makes them decodable.

case 1

in: [[0.5,0.25,0.25]]

expected: [1,2,2]

case 2

in: [[1]]

expected: [0]

case 3

in: [[0.1,0.2,0.3,0.4]]

expected: [4,3,2,2]

case 4

in: [[0.125,0.125,0.125,0.125,0.125,0.125,0.125,0.125]]

expected: [3,3,3,3,3,3,3,3]

Starter codePython

import math
def shannon_code_lengths(probs):
    # Your code here
    pass

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