lru-cache

<tmp>/workspace

total 40
drwxr-xr-x  7 jaykumar  staff   224 Jun 17 16:01 .
drwx------  4 jaykumar  staff   128 Jun 17 16:01 ..
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

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,
    "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
        ]
    ]
}

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)

total 8
drwxr-xr-x  3 jaykumar  staff   96 Jun 17 16:03 .
drwxr-xr-x  9 jaykumar  staff  288 Jun 17 16:03 ..
-rw-r--r--  1 jaykumar  staff  185 Jun 17 16:03 result.json

diff --git a/main.py b/output/result.json
index 041e062..2a9a0e3 100644
--- a/main.py
+++ b/output/result.json
@@ -1,206 +1 @@
-import json
-import os
-from collections import OrderedDict, defaultdict
-from dataclasses import dataclass
-
-
-@dataclass
-class Entry:
-    value: int
-    cost: int
-    expiry: int
-
-
-class SegmentedCache:
-    def __init__(self, capacity, protected_capacity, default_ttl, miss, reset_interval):
-        self.capacity = capacity
-        self.protected_capacity = protected_capacity
-        self.default_ttl = default_ttl
-        self.miss = miss
-        self.reset_interval = reset_interval
-
-        self.clock = 0
-        self.processed = 0
-        self.rejected = 0
-        self.get_results = []
-
-        self.frequency = defaultdict(int)
-        self.probation = OrderedDict()
-        self.protected = OrderedDict()
-
-    def total_weight(self):
-        return self.segment_weight(self.probation) + self.segment_weight(self.protected)
-
-    @staticmethod
-    def segment_weight(segment):
-        return sum(entry.cost for entry in segment.values())
-
-    def sweep_expired(self):
-        self.drop_expired_from(self.probation)
-        self.drop_expired_from(self.protected)
-
-    def drop_expired_from(self, segment):
-        expired_keys = [key for key, entry in segment.items() if entry.expiry <= self.clock]
-        for key in expired_keys:
-            del segment[key]
-
-    def refresh_expiry(self, entry):
-        entry.expiry = self.clock + self.default_ttl
-
-    def process(self, operation):
-        self.clock += 1
-        self.sweep_expired()
-
-        kind = operation[0]
-        key = operation[1]
-        self.frequency[key] += 1
-
-        if kind == "get":
-            self.get(key)
-        elif kind == "put":
-            _, _, value, cost = operation
-            self.put(key, value, cost)
-        else:
-            raise ValueError(f"unknown operation: {kind}")
-
-        self.processed += 1
-        i
… (+4635 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
}

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

warning: Not a git repository. Use --no-index to compare two paths outside a working tree
usage: git diff --no-index [<options>] <path> <path>

Diff output format options
    -p, --patch           generate patch
    -s, --no-patch        suppress diff output
    -u                    generate patch
    -U, --unified[=<n>]   generate diffs with <n> lines context
    -W, --[no-]function-context
                          generate diffs with <n> lines context
    --raw                 generate the diff in raw format
    --patch-with-raw      synonym for '-p --raw'
    --patch-with-stat     synonym for '-p --stat'
    --numstat             machine friendly --stat
    --shortstat           output only the last line of --stat
    -X, --dirstat[=<param1>,<param2>...]
                          output the distribution of relative amount of changes for each sub-directory
    --cumulative          synonym for --dirstat=cumulative
    --dirstat-by-file[=<param1>,<param2>...]
                          synonym for --dirstat=files,<param1>,<param2>...
    --check               warn if changes introduce conflict markers or whitespace errors
    --summary             condensed summary such as creations, renames and mode changes
    --name-only           show only names of changed files
    --name-status         show only names and status of changed files
    --stat[=<width>[,<name-width>[,<count>]]]
                          generate diffstat
    --stat-width <width>  generate diffstat with a given width
    --stat-name-width <width>
                          generate diffstat with a given name width
    --stat-graph-width <width>
                          generate diffstat with a given graph width
    --stat-count <count>  generate diffstat with limited lines
    --[no-]compact-summary
                          generate compact summary in diffstat
    --binary              output a binary diff that can be applied
    --[no-]full-index     show full pre- and post-image object names o
… (+5365 chars truncated)

smoke checks passed