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 OrderedDict

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

    capacity = config["capacity"]
    protected_capacity = config["protected_capacity"]
    default_ttl = config["default_ttl"]
    miss = config["miss"]
    reset_interval = config["reset_interval"]
    operations = config["operations"]

    probation = OrderedDict()
    protected = OrderedDict()
    frequency = {}

    get_results = []
    rejected_count = 0
    operations_count = 0

    for op_index, op in enumerate(operations):
        clock = op_index + 1

        # Expire entries
        to_remove_probation = [k for k in probation if probation[k]["expiry"] <= clock]
        to_remove_protected = [k for k in protected if protected[k]["expiry"] <= clock]

        for k in to_remove_probation:
            del probation[k]
        for k in to_remove_protected:
            del protected[k]

        # Increment frequency
        key = op[1]
        if key not in frequency:
            frequency[key] = 0
        frequency[key] += 1

        # Process operation
        if op[0] == "get":
            if key in protected and protected[key]["expiry"] > clock:
                result = protected[key]["value"]
                protected[key]["expiry"] = clock + default_ttl
                protected.move_to_end(key)
                get_results.append(result)
            elif key in probation and probation[key]["expiry"] > clock:
                result = probation[key]["value"]
                probation[key]["expiry"] = clock + default_ttl
                cost = probation[key]["cost"]
                del probation[key]
                protected[key] = {
                    "value": result,
                    "cost": cost,
                    "expiry": clock + default_ttl,
                }
                protected.move_to_end(key)
                get_results.append(result)

                # Demote if protected is over capacity
                while sum(e["cost"] for e in protected.values()) > protected_capacity:
                    lru_key = next(iter(protected))
                    entry = protected.pop(lru_key)
                    probation[lru_key] = entry
                    probation.move_to_end(lru_key)
            else:
                get_results.append(miss)

        elif op[0] == "put":
            new_value = op[2]
            new_cost = op[3]

            # Check if key is already live
            is_live = False
            if key in protected and protected[key]["expiry"] > clock:
                is_live = True
                segment = "protected"
            elif key in probation and probation[key]["expiry"] > clock:
                is_live = True
                segment = "probation"

            if is_live:
                # Update existing entry
                if segment == "protected":
                    protected[key]["value"] = new_value
                    protected[key]["cost"] = new_cost
                    protected[key]["expiry"] = clock + default_ttl
                    protected.move_to_end(key)
                else:
                    probation[key]["value"] = new_value
                    probation[key]["cost"] = new_cost
                    probation[key]["expiry"] = clock + default_ttl
                    probation.move_to_end(key)

                # Evict if over capacity
                total_weight = sum(e["cost"] for e in probation.values()) + sum(
                    e["cost"] for e in protected.values()
                )
                while total_weight > capacity:
                    total_weight -= evict_one(probation, protected, key)
            else:
                # Admit new entry
                if new_cost > capacity:
                    rejected_count += 1
                else:
                    current_weight = sum(e["cost"] for e in probation.values()) + sum(
                        e["cost"] for e in protected.values()
                    )
                    needed_room = max(0, current_weight + new_cost - capacity)

                    if needed_room == 0:
                        probation[key] = {
                            "value": new_value,
                            "cost": new_cost,
                            "expiry": clock + default_ttl,
                        }
                        probation.move_to_end(key)
                    else:
                        # Get eviction candidates
                        candidates = list(probation.keys()) + list(protected.keys())
                        accumulated_weight = 0
                        will_evict = []

                        for cand_key in candidates:
                            if accumulated_weight >= needed_room:
                                break
                            will_evict.append(cand_key)
                            if cand_key in probation:
                                accumulated_weight += probation[cand_key]["cost"]
                            else:
                                accumulated_weight += protected[cand_key]["cost"]

                        # Check frequency gate
                        new_key_freq = frequency[key]
                        admits = True

                        for cand_key in will_evict:
                            cand_freq = frequency[cand_key]
                            if new_key_freq <= cand_freq:
                                admits = False
                                break

                        if admits:
                            for cand_key in will_evict:
                                if cand_key in probation:
                                    del probation[cand_key]
                                elif cand_key in protected:
                                    del protected[cand_key]

                            probation[key] = {
                                "value": new_value,
                                "cost": new_cost,
          
… (+1447 chars truncated)