lru-cache

total 40
drwxr-xr-x  7 jaykumar  staff   224 Jun 17 16:04 .
drwx------  4 jaykumar  staff   128 Jun 17 16:04 ..
drwxr-xr-x  3 jaykumar  staff    96 Jun 17 14:36 data
drwxr-xr-x  3 jaykumar  staff    96 Jun 17 14:36 environment
-rw-r--r--  1 jaykumar  staff  9746 Jun 17 14:36 instruction.md
-rw-r--r--  1 jaykumar  staff  1049 Jun 17 14:36 main.py
-rw-r--r--  1 jaykumar  staff   323 Jun 17 14:36 task.toml

<tmp>/workspace
data/operations.json
main.py
task.toml
environment/README.md
instruction.md

# 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)

{'capacity': 9, 'protected_capacity': 4, 'default_ttl': 8, 'miss': -1, 'reset_interval': 7}
ops 22
first [['put', 1, 100, 2], ['put', 2, 200, 2], ['put', 3, 300, 1], ['get', 1], ['get', 2], ['get', 1], ['put', 4, 400, 2], ['get', 3], ['get', 1], ['put', 5, 500, 2]]
last [['put', 6, 600, 3], ['get', 4], ['put', 7, 700, 4], ['get', 1], ['get', 2], ['put', 8, 800, 1], ['get', 3], ['put', 1, 150, 2], ['get', 8], ['get', 77]]

{
    "capacity": 9,
    "protected_capacity": 4,
    "default_ttl": 8,
    "miss": -1,
    "reset_interval": 7,
    "operations": [
        [
            "put",
            1,
            100,
            2
        ],
        [
            "put",
            2,
            200,
            2
        ],
        [
            "put",
            3,
            300,
            1
        ],
        [
            "get",
            1
        ],
        [
            "get",
            2
        ],
        [
            "get",
            1
        ],
        [
            "put",
            4,
            400,
            2
        ],
        [
            "get",
            3
        ],
        [
            "get",
            1
        ],
        [
            "put",
            5,
            500,
            2
        ],
        [
            "get",
            2
        ],
        [
            "get",
            99
        ],
        [
            "put",
            6,
            600,
            3
        ],
        [
            "get",
            4
        ],
        [
            "put",
            7,
            700,
            4
        ],
        [
            "get",
            1
        ],
        [
            "get",
            2
        ],
        [
            "put",
            8,
            800,
            1
        ],
        [
            "get",
            3
        ],
        [
            "put",
            1,
            150,
            2
        ],
        [
            "get",
            8
        ],
        [
            "get",
            77
        ]
    ]
}

3:The trace lives at data/operations.json. It is a JSON object. The field capacity is a positive integer: it is the total weight budget the whole cache is allowed to hold. The field protected_capacity is a positive integer no larger than capacity: it is the weight budget of the protected segment specifically. The field default_ttl is a positive integer used to compute expiry times, explained below. The field miss is an integer that you must return as the result of any lookup that does not find a live entry, instead of the conventional minus one. The field reset_interval is a positive integer that controls how often the frequency estimates are aged, explained below. The field operations is a list of operations to apply in order. A write looks like the four element list put, then an integer key, then an integer value, then an integer cost of at least one, which is that entry's weight. A read looks like the two element list get, then an integer key.
7:The cache keeps a frequency estimate for every key it has ever seen. The estimate starts at zero for a key that has never appeared. At the very start of handling each operation, after the expiry sweep, increment the frequency estimate of the key named in that operation by one. Do this for both reads and writes, and do it whether or not the key is currently resident and whether or not the operation will ultimately succeed; it is a tally of references, not of hits. This frequency estimate survives eviction: if a key is evicted and later seen again, its estimate continues from where it left off rather than resetting. Separately, the estimates are aged over time. Keep a count of how many operations have been processed, and every time that count becomes a multiple of reset_interval, that is, right after finishing the operation whose position is a multiple of reset_interval, halve every frequency estimate using integer division that rounds toward zero. The halving applies to the estimate of every key the cache has ever tracked,
… (+3953 chars truncated)

We run a small caching layer in front of an expensive service, and I have captured a trace of operations that hit it. I need you to replay that trace exactly and report what the cache ends up doing. The catch is that this is not a plain least-recently-used cache. It is segmented, entries expire on a logical clock, the capacity is measured in weight rather than in a count of keys, and admission of a new key is gated by how often that key has been seen. The eviction behaviour is therefore fussier than the textbook version, so please follow the rules below to the letter, because several of them are exactly where a casual implementation goes wrong.

The trace lives at data/operations.json. It is a JSON object. The field capacity is a positive integer: it is the total weight budget the whole cache is allowed to hold. The field protected_capacity is a positive integer no larger than capacity: it is the weight budget of the protected segment specifically. The field default_ttl is a positive integer used to compute expiry times, explained below. The field miss is an integer that you must return as the result of any lookup that does not find a live entry, instead of the conventional minus one. The field reset_interval is a positive integer that controls how often the frequency estimates are aged, explained below. The field operations is a list of operations to apply in order. A write looks like the four element list put, then an integer key, then an integer value, then an integer cost of at least one, which is that entry's weight. A read looks like the two element list get, then an integer key.

There is a logical clock. It starts at zero, and it advances by one just before each operation is processed, so the first operation in the trace happens at clock time one, the second at time two, and so on. Whenever an entry is written or is successfully read, its expiry time is set to the current clock time plus default_ttl. An entry is considered expired, and must be treated as if 
… (+7746 chars truncated)

{
    "get_results": [
        100,
        200,
        100,
        300,
        100,
        200,
        -1,
        400,
        100,
        200,
        -1,
        800,
        -1
    ],
    "final_probation": [
        [
            2,
            200
        ]
    ],
    "final_protected": [
        [
            1,
            150
        ],
        [
            8,
            800
        ]
    ],
    "total_weight": 5,
    "rejected": 2
}

True
['get_results', 'final_probation', 'final_protected', 'total_weight', 'rejected']
reads 13
probation [[2, 200]]
protected [[1, 150], [8, 800]]
weight 5
rejected 2

fatal: not a git repository (or any of the parent directories): .git

diff --git a/main.py b/output/result.json
index c9dfad2..2a9a0e3 100644
--- a/main.py
+++ b/output/result.json
@@ -1,173 +1 @@
-import json
-import os
-from collections import OrderedDict, defaultdict
-
-
-INPUT_PATH = "data/operations.json"
-OUTPUT_PATH = "output/result.json"
-
-
-def segment_weight(segment):
-    return sum(entry["cost"] for entry in segment.values())
-
-
-def main():
-    with open(INPUT_PATH) as f:
-        data = json.load(f)
-
-    capacity = data["capacity"]
-    protected_capacity = data["protected_capacity"]
-    default_ttl = data["default_ttl"]
-    miss_value = data["miss"]
-    reset_interval = data["reset_interval"]
-    operations = data["operations"]
-
-    probation = OrderedDict()
-    protected = OrderedDict()
-    frequencies = defaultdict(int)
-    get_results = []
-    rejected = 0
-    total_weight = 0
-
-    def sweep_expired(now):
-        nonlocal total_weight
-        for segment in (probation, protected):
-            for key in list(segment.keys()):
-                if segment[key]["expiry"] <= now:
-                    total_weight -= segment[key]["cost"]
-                    del segment[key]
-
-    def demote_until_protected_fits():
-        while segment_weight(protected) > protected_capacity:
-            key, entry = protected.popitem(last=False)
-            probation[key] = entry
-
-    def evict_for_update(updated_key):
-        nonlocal total_weight
-        while total_weight > capacity:
-            victim_segment = None
-            victim_key = None
-
-            for key in probation:
-                if key != updated_key:
-                    victim_segment = probation
-                    victim_key = key
-                    break
-
-            if victim_key is None:
-                for key in protected:
-                    if key != updated_key:
-                        victim_segment = protected
-                        victim_key = key
-                        break
-
-            if victim_key is
… (+3868 chars truncated)

output/result.json

./__pycache__

import json
import os
from collections import OrderedDict, defaultdict


INPUT_PATH = "data/operations.json"
OUTPUT_PATH = "output/result.json"


def segment_weight(segment):
    return sum(entry["cost"] for entry in segment.values())


def main():
    with open(INPUT_PATH) as f:
        data = json.load(f)

    capacity = data["capacity"]
    protected_capacity = data["protected_capacity"]
    default_ttl = data["default_ttl"]
    miss_value = data["miss"]
    reset_interval = data["reset_interval"]
    operations = data["operations"]

    probation = OrderedDict()
    protected = OrderedDict()
    frequencies = defaultdict(int)
    get_results = []
    rejected = 0
    total_weight = 0

    def sweep_expired(now):
        nonlocal total_weight
        for segment in (probation, protected):
            for key in list(segment.keys()):
                if segment[key]["expiry"] <= now:
                    total_weight -= segment[key]["cost"]
                    del segment[key]

    def demote_until_protected_fits():
        while segment_weight(protected) > protected_capacity:
            key, entry = protected.popitem(last=False)
            probation[key] = entry

    def evict_for_update(updated_key):
        nonlocal total_weight
        while total_weight > capacity:
            victim_segment = None
            victim_key = None

            for key in probation:
                if key != updated_key:
                    victim_segment = probation
                    victim_key = key
                    break

            if victim_key is None:
                for key in protected:
                    if key != updated_key:
                        victim_segment = protected
                        victim_key = key
                        break

            if victim_key is None:
                break

            total_weight -= victim_segment[victim_key]["cost"]
            del victim_segment[victim_key]

    def try_admit(key, value, cost, now):
        nonl
… (+3353 chars truncated)

{
    "get_results": [
        100,
        200,
        100,
        300,
        100,
        200,
        -1,
        400,
        100,
        200,
        -1,
        800,
        -1
    ],
    "final_probation": [
        [
            2,
            200
        ]
    ],
    "final_protected": [
        [
            1,
            150
        ],
        [
            8,
            800
        ]
    ],
    "total_weight": 5,
    "rejected": 2
}