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


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_value = config["miss"]
    reset_interval = config["reset_interval"]
    operations = config["operations"]

    # Initialize state
    clock = 0
    operation_count = 0
    frequency = defaultdict(int)
    cache = {}  # key -> {'value': ..., 'cost': ..., 'expiry': ...}

    # Segment management - lists ordered LRU to MRU
    probation = []
    protected = []
    segment_of = {}  # key -> 'probation' or 'protected'

    get_results = []
    rejected_count = 0

    for operation in operations:
        # Step 1: Increment logical clock
        clock += 1

        # Step 2: Sweep expired entries from both segments
        new_probation = []
        for key in probation:
            if cache[key]["expiry"] > clock:
                new_probation.append(key)
            else:
                del cache[key]
                del segment_of[key]
        probation = new_probation

        new_protected = []
        for key in protected:
            if cache[key]["expiry"] > clock:
                new_protected.append(key)
            else:
                del cache[key]
                del segment_of[key]
        protected = new_protected

        # Step 3: Increment frequency estimate for this operation's key
        op_key = operation[1]
        frequency[op_key] += 1

        # Step 4: Process operation
        if operation[0] == "get":
            # Handle read operation
            if op_key in cache and cache[op_key]["expiry"] > clock:
                # Cache hit
                value = cache[op_key]["value"]
                cache[op_key]["expiry"] = clock + default_ttl

                if segment_of[op_key] == "protected":
                    # Move to MRU in protected segment
                    protected.remove(op_key)
                    protected.append(op_key)
                else:  # in probation
                    # Promote to protected as MRU
                    probation.remove(op_key)
                    protected.append(op_key)
                    segment_of[op_key] = "protected"

                    # Handle demotion if protected exceeds capacity
                    while True:
                        protected_weight = sum(cache[k]["cost"] for k in protected)
                        if protected_weight <= protected_capacity:
                            break
                        # Demote LRU of protected to MRU of probation
                        lru_key = protected.pop(0)
                        probation.append(lru_key)
                        segment_of[lru_key] = "probation"

                get_results.append(value)
            else:
                # Cache miss
                get_results.append(miss_value)

        elif operation[0] == "put":
            value = operation[2]
            cost = operation[3]

            # Check if key already exists and is not expired
            key_exists = op_key in cache and cache[op_key]["expiry"] > clock

            if key_exists:
                # Update existing entry
                cache[op_key]["value"] = value
                cache[op_key]["cost"] = cost
                cache[op_key]["expiry"] = clock + default_ttl

                # Make MRU in current segment
                segment = segment_of[op_key]
                if segment == "protected":
                    protected.remove(op_key)
                    protected.append(op_key)
                else:
                    probation.remove(op_key)
                    probation.append(op_key)

                # Evict if over total capacity, never evicting the updated entry
                while True:
                    total_weight = sum(cache[k]["cost"] for k in cache)
                    if total_weight <= capacity:
                        break

                    # Build eviction candidates (LRU order, skip updated key)
                    candidates = []
                    for key in probation:
                        if key != op_key:
                            candidates.append(key)
                    for key in protected:
                        if key != op_key:
                            candidates.append(key)

                    if not candidates:
                        break

                    # Evict first candidate (LRU)
                    evict_key = candidates[0]
                    if evict_key in probation:
                        probation.remove(evict_key)
                    else:
                        protected.remove(evict_key)
                    del cache[evict_key]
                    del segment_of[evict_key]

            else:
                # Admit new entry
                if cost > capacity:
                    # Entry larger than entire cache capacity
                    rejected_count += 1
                else:
                    total_weight = sum(cache[k]["cost"] for k in cache)
                    weight_to_free = max(0, total_weight + cost - capacity)

                    if weight_to_free == 0:
                        # Fits without eviction
                        cache[op_key] = {
                            "value": value,
                            "cost": cost,
                            "expiry": clock + default_ttl,
                        }
                        probation.append(op_key)
                        segment_of[op_key] = "probation"
                    else:
                        # Frequency gate: collect entries to evict in order
                        eviction_order = []
                        weight_freed = 0

                        # Add probation entries in LRU order
                        for key in probation:
                            weight_freed += cache[key]["cost"]
                            evicti
… (+2712 chars truncated)