Partial-Observability Memory Length

Problem

Find the shortest suffix of the observation history that contains at least distinct_required distinct observations.

Scan from the most recent observation backward and return the suffix length; return -1 if even the full history does not contain enough distinct values.

Hint

The memory length is the smallest frame stack that reveals enough distinct observations.

Test cases

case 1

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

expected: 2

case 2

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

expected: 3

case 3

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

expected: -1

case 4

in: [["a","b","a"],1]

expected: 1

Starter codePython

def partial_observability_memory_length(observations, distinct_required):
    # Your code here
    pass

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