Kolmogorov Structure Function Lite

Problem

Each candidate model is a pair [program_bits, data_bits]. The lite structure function at model budget alpha is the smallest program_bits + data_bits among candidates whose program_bits is at most alpha. Return that minimum total, or -1 when no candidate fits the budget.

Hint

A more expressive model costs more program bits but describes the data in fewer bits.

Test cases

case 1

in: [[[10,90],[20,70],[30,50]],25]

expected: 90

case 2

in: [[[10,90],[20,70],[30,50]],5]

expected: -1

case 3

in: [[[10,90],[20,70],[30,50]],100]

expected: 80

case 4

in: [[],10]

expected: -1

Starter codePython

def kolmogorov_structure_function(candidates, alpha):
    # Your code here
    pass

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