You will be given a sequence of memory requests and a cache size. You must return the least possible number of cache misses under any cache replacement strategy.
An optimal strategy is Belady's algorithm, which you can use if you want to.
A caching system works as follows: The cache starts out empty. Memory requests come in. If the request asks for a piece of data in the cache, all is well. If not, you incur a cache miss. At this point you may insert the data that was request into the cache for future use. If the cache was full and you want to insert new data, you must evict data that was previously in the cache. You may never insert data that was not just in the cache.
Your goal is to find the minimum possible number of cache misses for a given memory request sequence and cache size.
You will be given the cache size, a positive integer, and the memory request sequence, which is a list of tokens. These tokens can be whatever kind of tokens you like, as long as at least 256 different tokens are possible (bytes are fine, bools are not). For instance, ints, strings, lists are all fine. Ask for clarification if needed.
3 [5, 0, 1, 2, 0, 3, 1, 2, 5, 2] 6
See wikipedia for a replacement policy that achieves this.
2 [0, 1, 2, 0, 1, 0, 1] 3
Simply avoid adding
2 to the cache.
3 [0, 1, 2, 1, 4, 3, 1, 0, 2, 3, 4, 5, 0, 2, 3, 4] 9
One way to achieve this is by never evicting
2, and evicting
1 as soon as possible after its last use.
Scoring: This is code golf. Fewest bytes wins.