py-04-lru-ttl-cache

# LRU Cache with TTL

Implement a file **`solution.py`** containing a class:

```python
class LRUCache:
    def __init__(self, capacity: int, ttl: float, now=time.monotonic):
        ...

    def get(self, key):
        ...

    def put(self, key, value):
        ...

    def __len__(self) -> int:
        ...
```

A bounded cache that evicts by **least-recently-used** order and also **expires**
entries by age.

Behavior:

- `capacity` is the maximum number of live entries. `ttl` is the maximum age, in
  seconds, an entry may live before it is considered expired.
- `get(key)` returns the stored value, or `None` if the key is absent or expired.
  A successful `get` counts as a **use** (it refreshes recency, but **not** the
  entry's age / expiry time).
- `put(key, value)` inserts or updates an entry, marking it most-recently-used and
  **resetting its age** (its timestamp becomes "now"). If inserting a new key
  would exceed `capacity`, evict the least-recently-used live entry first.
- An **expired** entry must never be returned by `get` and must not count toward
  `__len__`. Expired entries may be purged lazily.
- `__len__` returns the number of **live (non-expired)** entries.

## Injectable clock

The constructor takes a `now` callable (defaulting to `time.monotonic`) that
returns the current time as a float. **All time decisions must use `now()`**, not
a hardcoded clock. This lets tests pass a controllable clock for deterministic
behavior. An entry inserted at time `t0` is expired once `now() - t0 >= ttl`
(i.e. an age strictly less than `ttl` is still live).

Example:

```python
clock = [0.0]
cache = LRUCache(capacity=2, ttl=10.0, now=lambda: clock[0])
cache.put("a", 1)
clock[0] = 5.0
assert cache.get("a") == 1     # age 5 < ttl 10 -> live
clock[0] = 10.0
assert cache.get("a") is None  # age 10 >= ttl 10 -> expired
```

from solution import LRUCache


def make(capacity=2, ttl=10.0):
    clock = [0.0]
    cache = LRUCache(capacity=capacity, ttl=ttl, now=lambda: clock[0])
    return cache, clock


def test_basic_get_put():
    cache, _ = make()
    cache.put("a", 1)
    cache.put("b", 2)
    assert cache.get("a") == 1
    assert cache.get("b") == 2
    assert cache.get("missing") is None


def test_lru_eviction_on_capacity():
    cache, _ = make(capacity=2)
    cache.put("a", 1)
    cache.put("b", 2)
    cache.put("c", 3)  # exceeds capacity -> evict LRU ("a")
    assert cache.get("a") is None
    assert cache.get("b") == 2
    assert cache.get("c") == 3
    assert len(cache) == 2


def test_get_refreshes_recency():
    cache, _ = make(capacity=2)
    cache.put("a", 1)
    cache.put("b", 2)
    assert cache.get("a") == 1   # "a" now most-recently-used
    cache.put("c", 3)            # should evict "b", not "a"
    assert cache.get("a") == 1
    assert cache.get("b") is None
    assert cache.get("c") == 3


def test_ttl_expiry_boundary():
    cache, clock = make(ttl=10.0)
    cache.put("a", 1)
    clock[0] = 9.999
    assert cache.get("a") == 1   # age < ttl -> live
    clock[0] = 10.0
    assert cache.get("a") is None  # age == ttl -> expired


def test_get_does_not_reset_age():
    cache, clock = make(ttl=10.0)
    cache.put("a", 1)
    clock[0] = 5.0
    assert cache.get("a") == 1   # use does not refresh age
    clock[0] = 10.0
    assert cache.get("a") is None  # still expires at original t0 + ttl


def test_put_resets_age():
    cache, clock = make(ttl=10.0)
    cache.put("a", 1)
    clock[0] = 8.0
    cache.put("a", 99)           # re-put resets age and value
    clock[0] = 15.0              # 7s after re-put -> still live
    assert cache.get("a") == 99


def test_len_excludes_expired():
    cache, clock = make(capacity=5, ttl=10.0)
    cache.put("a", 1)
    cache.put("b", 2)
    assert len(cache) == 2
    clock[0] = 11.0
    assert len(cache) == 0


def test_expired_entry_does_not_count_against_capacity():
    cache, clock = make(capacity=2, ttl=10.0)
    cache.put("a", 1)
    cache.put("b", 2)
    clock[0] = 11.0              # both expired
    cache.put("c", 3)
    cache.put("d", 4)           # should fit; expired ones purged
    assert cache.get("c") == 3
    assert cache.get("d") == 4
    assert cache.get("a") is None
    assert len(cache) == 2

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
import time
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int, ttl: float, now=time.monotonic):
        self.capacity = capacity
        self.ttl = ttl
        self.now = now
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return None

        entry = self.cache[key]
        if self.now() - entry['timestamp'] >= self.ttl:
            del self.cache[key]
            return None

        # Move to end to mark as recently used
        self.cache.move_to_end(key)
        return entry['value']

    def put(self, key, value):
        current_time = self.now()

        if key in self.cache:
            # Update existing entry
            self.cache.move_to_end(key)
            self.cache[key] = {'value': value, 'timestamp': current_time}
        else:
            # Add new entry
            if len(self.cache) >= self.capacity:
                # Remove least recently used entry
                self.cache.popitem(last=False)
            self.cache[key] = {'value': value, 'timestamp': current_time}

    def __len__(self) -> int:
        current_time = self.now()
        # Remove expired entries
        keys_to_remove = []
        for key, entry in self.cache.items():
            if current_time - entry['timestamp'] >= self.ttl:
                keys_to_remove.append(key)

        for key in keys_to_remove:
            del self.cache[key]

        return len(self.cache)
```