lru-cache

# Read data/operations.json and write output/result.json.
#
# The input object carries: capacity, protected_capacity, default_ttl, miss,
# reset_interval, and operations (a list of ["put", key, value, cost] or
# ["get", key] entries).
#
# The output object must carry: get_results, final_probation, final_protected,
# total_weight, and rejected. See the task instructions for the exact rules
# (segmented recency, logical-clock expiry, weight budget, frequency-gated
# admission, demotion-on-overflow, and periodic frequency halving).
#
# TODO: implement the cache. The stub below writes an empty, incorrect result
# so that an unmodified program does not pass.
import json
import os

with open("data/operations.json") as f:
    data = json.load(f)

capacity = data["capacity"]
operations = data["operations"]

result = {
    "get_results": [],
    "final_probation": [],
    "final_protected": [],
    "total_weight": 0,
    "rejected": 0,
}

os.makedirs("output", exist_ok=True)
with open("output/result.json", "w") as f:
    json.dump(result, f)

import json
import os
from collections import defaultdict, OrderedDict

def main():
    with open('data/operations.json', 'r') as f:
        data = json.load(f)

    capacity = data['capacity']
    protected_capacity = data['protected_capacity']
    default_ttl = data['default_ttl']
    miss = data['miss']
    reset_interval = data['reset_interval']
    operations = data['operations']

    # Initialize cache state
    probation = OrderedDict()  # key -> (value, cost, expiry_time)
    protected = OrderedDict()  # key -> (value, cost, expiry_time)
    frequency = defaultdict(int)  # key -> frequency estimate

    clock = 0
    operation_count = 0
    get_results = []
    rejected_count = 0

    for op in operations:
        # Advance clock
        clock += 1

        # Expiry sweep
        keys_to_delete_probation = []
        for key in probation:
            value, cost, expiry_time = probation[key]
            if expiry_time <= clock:
                keys_to_delete_probation.append(key)
        for key in keys_to_delete_probation:
            del probation[key]

        keys_to_delete_protected = []
        for key in protected:
            value, cost, expiry_time = protected[key]
            if expiry_time <= clock:
                keys_to_delete_protected.append(key)
        for key in keys_to_delete_protected:
            del protected[key]

        # Increment frequency for current key
        op_key = op[1]
        frequency[op_key] += 1

        # Process operation
        if op[0] == 'get':
            key = op[1]
            if key in protected:
                value, cost, _ = protected[key]
                get_results.append(value)
                # Refresh expiry and make most recently used
                protected[key] = (value, cost, clock + default_ttl)
                protected.move_to_end(key)
            elif key in probation:
                value, cost, _ = probation[key]
                get_results.append(value)
                # Refresh expiry and promote to protected
                del probation[key]
                protected[key] = (value, cost, clock + default_ttl)
                # Handle demotion if protected exceeds capacity
                while sum(c for _, c, _ in protected.values()) > protected_capacity:
                    lru_key = next(iter(protected))
                    lru_value, lru_cost, lru_expiry = protected.pop(lru_key)
                    probation[lru_key] = (lru_value, lru_cost, lru_expiry)
            else:
                get_results.append(miss)

        elif op[0] == 'put':
            key = op[1]
            value = op[2]
            cost = op[3]

            if key in protected or key in probation:
                # Update existing entry
                if key in protected:
                    protected[key] = (value, cost, clock + default_ttl)
                    protected.move_to_end(key)
                else:
                    probation[key] = (value, cost, clock + default_ttl)
                    probation.move_to_end(key)

                # Check if we need to evict
                total_weight = sum(c for _, c, _ in probation.values()) + sum(c for _, c, _ in protected.values())
                while total_weight > capacity:
                    evicted = False
                    # Try to evict LRU from probation first, but not the updated key
                    for k in list(probation.keys()):
                        if k != key:
                            _, c, _ = probation[k]
                            del probation[k]
                            total_weight -= c
                            evicted = True
                            break

                    if not evicted:
                        # Evict LRU from protected, but not the updated key
                        for k in list(protected.keys()):
                            if k != key:
                                _, c, _ = protected[k]
                                del protected[k]
                                total_weight -= c
                                evicted = True
                                break

                    if not evicted:
                        # Can't evict anything (shouldn't happen)
                        break
            else:
                # Attempt to admit new entry
                if cost > capacity:
                    rejected_count += 1
                else:
                    # Calculate eviction candidates
                    total_weight = sum(c for _, c, _ in probation.values()) + sum(c for _, c, _ in protected.values())
                    needed = max(0, total_weight + cost - capacity)

                    if needed == 0:
                        # Just admit it
                        probation[key] = (value, cost, clock + default_ttl)
                    else:
                        # Collect eviction candidates in order
                        candidates = []
                        freed = 0

                        for k in list(probation.keys()):
                            v, c, _ = probation[k]
                            candidates.append((k, c, frequency[k]))
                            freed += c
                            if freed >= needed:
                                break

                        if freed < needed:
                            for k in list(protected.keys()):
                                v, c, _ = protected[k]
                                candidates.append((k, c, frequency[k]))
                                freed += c
                                if freed >= needed:
                                    break

                        # Check if new key out-ranks all candidates
                        admitted = True
                        for cand_key, cand_cost, cand_freq in candidates:
                            if frequency[key] <= cand_freq:
                                admitted = False
                                break

                        
… (+1350 chars truncated)