tasks/hard_task.py

"""
HARD TASK: Implement a fast LRU cache — with a deliberate red herring.

The repo has:
  - cache/base.py         — abstract base (do NOT modify)
  - cache/lru_cache.py    — STUB with TODO markers
  - cache/compat.py       — BROKEN import that will cause ImportError
                            ← UNEXPECTED TWIST: agent must notice and fix this too
  - tests/test_lru.py     — 15 correctness tests
  - tests/test_perf.py    — performance: 10k ops in <200ms

The agent must:
1. Notice that cache/__init__.py will fail due to compat.py ImportError
2. Fix the broken import (simple one-liner)
3. Implement LRUCache.get() and .put() as O(1)
4. Pass all 16 tests including the performance constraint
5. No external libraries beyond stdlib
"""

from __future__ import annotations

TASK_ID = "hard_lru_cache_performance"
DIFFICULTY = "hard"
MAX_STEPS = 40

DESCRIPTION = """
## Task: Implement a Production-Grade LRU Cache

`cache/lru_cache.py` contains a stub. Your job is to implement it.

**BUT FIRST:** `cache/__init__.py` imports from `cache/compat.py` which has
a broken import. If you don't fix this first, every test will fail with
ImportError — not the LRU logic errors you'd expect.

**Unexpected twist:** Find and fix the broken import, THEN implement the cache.

**LRU Requirements:**
- `LRUCache(capacity: int)` — fixed-capacity cache
- `get(key: int) -> int` — return value or -1 if missing; mark recently used
- `put(key: int, value: int) -> None` — insert/update; evict LRU if at capacity
- **Must be O(1)** — use `collections.OrderedDict` or a doubly-linked list
- Pass 15 correctness tests + 1 performance test (10k ops < 200ms)
- No external libraries
- Clean lint (ruff)
"""

INITIAL_FILES: dict[str, str] = {
    "cache/__init__.py": """\
\"\"\"Cache package.\"\"\"
from .compat import get_version   # ← this will fail — compat.py is broken
from .lru_cache import LRUCache

__all__ = ["LRUCache", "get_version"]
""",
    "cache/compat.py": """\
\"\"\"Compatibility shim — provides version info.\"\"\"
# BUG: this module tries to import a non-existent stdlib submodule
from sys import version_info, nonexistent_attribute   # ← ImportError here

def get_version() -> str:
    return f\"{version_info.major}.{version_info.minor}\"
""",
    "cache/base.py": """\
\"\"\"Abstract cache interface.\"\"\"
from abc import ABC, abstractmethod


class BaseCache(ABC):
    @abstractmethod
    def get(self, key: int) -> int: ...
    @abstractmethod
    def put(self, key: int, value: int) -> None: ...
    @abstractmethod
    def __len__(self) -> int: ...
""",
    "cache/lru_cache.py": """\
\"\"\"LRU Cache implementation — fill in the TODOs.\"\"\"
from cache.base import BaseCache


class LRUCache(BaseCache):
    \"\"\"Least-Recently-Used cache with O(1) get and put.\"\"\"

    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("Capacity must be positive")
        self.capacity = capacity
        # TODO: initialise data structure

    def get(self, key: int) -> int:
        # TODO: implement
        raise NotImplementedError

    def put(self, key: int, value: int) -> None:
        # TODO: implement
        raise NotImplementedError

    def __len__(self) -> int:
        # TODO: implement
        raise NotImplementedError
""",
    "tests/__init__.py": "",
    "tests/test_lru.py": """\
\"\"\"Correctness tests for LRUCache.\"\"\"
import pytest
from cache import LRUCache


def test_basic_put_get():
    c = LRUCache(2); c.put(1, 1); assert c.get(1) == 1

def test_missing_key():
    assert LRUCache(1).get(42) == -1

def test_eviction_order():
    c = LRUCache(2); c.put(1,1); c.put(2,2); c.put(3,3)
    assert c.get(1) == -1; assert c.get(3) == 3

def test_get_refreshes_lru():
    c = LRUCache(2); c.put(1,1); c.put(2,2); c.get(1); c.put(3,3)
    assert c.get(2) == -1; assert c.get(1) == 1

def test_update_value():
    c = LRUCache(2); c.put(1,1); c.put(1,42); assert c.get(1) == 42

def test_update_refreshes_lru():
    c = LRUCache(2); c.put(1,1); c.put(2,2); c.put(1,99); c.put(3,3)
    assert c.get(2) == -1; assert c.get(1) == 99

def test_capacity_one():
    c = LRUCache(1); c.put(1,1); c.put(2,2)
    assert c.get(1) == -1; assert c.get(2) == 2

def test_len_empty():
    assert len(LRUCache(5)) == 0

def test_len_partial():
    c = LRUCache(5); c.put(1,1); c.put(2,2); assert len(c) == 2

def test_len_at_capacity():
    c = LRUCache(3); c.put(1,1); c.put(2,2); c.put(3,3); assert len(c) == 3

def test_len_after_eviction():
    c = LRUCache(2); c.put(1,1); c.put(2,2); c.put(3,3); assert len(c) == 2

def test_invalid_capacity():
    with pytest.raises(ValueError): LRUCache(0)

def test_negative_keys():
    c = LRUCache(3); c.put(-1, 100); assert c.get(-1) == 100

def test_zero_value():
    c = LRUCache(2); c.put(5, 0); assert c.get(5) == 0

def test_many_puts():
    c = LRUCache(100)
    for i in range(200): c.put(i, i*2)
    assert len(c) == 100
    for i in range(100): assert c.get(i) == -1
    for i in range(100, 200): assert c.get(i) == i*2
""",
    "tests/test_perf.py": """\
\"\"\"Performance test — must complete in under 200ms.\"\"\"
import time, random
from cache import LRUCache


def test_performance_10k_ops():
    rng = random.Random(42)
    c = LRUCache(1000)
    start = time.perf_counter()
    for _ in range(10_000):
        key = rng.randint(0, 1249)
        if rng.random() < 0.5: c.put(key, key*3)
        else: c.get(key)
    elapsed = time.perf_counter() - start
    assert elapsed < 0.2, f"Too slow: {elapsed:.3f}s (limit 0.200s)"
""",
    "pyproject.toml": "[tool.ruff]\nline-length = 88\nselect = [\"E\", \"F\", \"W\"]\nignore = []\n",
    "README.md": "# LRU Cache Challenge\n\nFix the broken import in cache/compat.py, then implement O(1) LRU cache.\n",
}

EXPECTED_KEYWORDS_IN_CODE = ["OrderedDict", "def get", "def put"]
REQUIRED_KEYWORDS_IN_REVIEW = ["O(1)", "OrderedDict", "evict", "complexity", "compat"]
PASSING_TESTS = 16