Simulate an **in-memory LRU (Least Recently Used) memoization cache** over a sequence of pure-function calls, and report each call's result together with how many real computations were actually performed. ## What to implement ```python def solution(capacity, calls): ... ``` Process the `calls` in order against a cache that can hold at most `capacity` distinct entries. For each call, either return its cached result (a **hit**) or compute it fresh and cache it (a **miss**), evicting the least recently used entry whenever the cache would exceed `capacity`. ## Input - **`capacity`** — a non-negative integer, the maximum number of entries the cache may hold. - **`calls`** — a list of calls, each a 3-tuple `(func_name, args, kwargs)`: - `func_name` — a string naming the function to invoke (see below). - `args` — a list of positional arguments. - `kwargs` — a dict of keyword arguments. ## Supported functions `func_name` is always one of: | Name | Signature | Result | |------|-----------|--------| | `'add'` | `add(a, b)` | `a + b` | | `'mul'` | `mul(a, b)` | `a * b` | | `'pow'` | `pow(base, exp)` | `base ** exp` | | `'affine'` | `affine(x, scale=1, bias=0)` | `scale * x + bias` | Every call's `args`/`kwargs` are valid for the named function (so `scale` and `bias` may be passed positionally or by keyword, or omitted to use their defaults). ## Cache key A cache entry is identified by the combination of: 1. the **function name**, 2. the **positional arguments** (`args`, in order), and 3. the **keyword arguments** (`kwargs`). **Keyword order must not matter.** Two calls with the same keyword pairs in a different order refer to the *same* cache entry — e.g. `affine(5, scale=2, bias=1)` and `affine(5, bias=1, scale=2)` share one entry. ## Per-call behavior For each call, in order: - **Hit** — if its key is already in the cache: return the cached value and mark that entry as **most recently used** (do **not** recompute). - **Miss** — otherwise: invoke the function to compute the value, count this as one real computation, and return the value. Then, **only if `capacity > 0`**, store the value under its key as the most recently used entry; if this makes the cache size exceed `capacity`, **evict the least recently used entry**. Note that when `capacity == 0`, nothing is ever stored, so every call is a miss and is recomputed. ## Output Return a tuple `(results, computed_count)` where: - **`results`** — the list of returned values, one per call, in call order. - **`computed_count`** — the total number of misses, i.e. the number of times a value was actually computed (cache hits are not counted). ## Constraints - `0 <= capacity <= 100000` - `0 <= len(calls) <= 100000` - `func_name` is one of `'add'`, `'mul'`, `'pow'`, `'affine'` - All provided calls are valid for the named function - All argument values are integers and keyword arguments are hashable

Reconstruct the exact state of an **LRU cache** after a crash by replaying its **write-ahead journal**. ## Background The cache persists durably: before any operation is considered successful, it appends a journal record describing that operation. After a crash, only a **prefix** of the journal survived (passed to you as `journal`). Replaying that surviving prefix in order, with LRU eviction, reproduces the exact recovered cache state. Implement: ```python def solution(capacity, journal): ... ``` ## Input - **`capacity`** — the maximum number of entries the cache may hold. - **`journal`** — a list of records, already in durable (chronological) order. Each record is a tuple/list of one of two forms: - **PUT:** `('PUT', func_name, args, kwargs, value)` — the computed `value` for this key is now stored, and the key becomes the **most-recently-used (MRU)** entry. - **HIT:** `('HIT', func_name, args, kwargs)` — an existing key was read, so it becomes the **MRU** entry. In every record, `func_name` is a string, `args` is a **list**, and `kwargs` is a **dict**. ## Canonical key Each record identifies a cache entry by a **canonical key** built as: ```python (func_name, tuple(args), tuple(sorted(kwargs.items()))) ``` Sorting the `kwargs` items by name means different keyword-argument orders map to the **same** key (e.g. `{'scale': 2, 'bias': 1}` and `{'bias': 1, 'scale': 2}` are identical). ## Replay rules Process records in order, maintaining LRU recency: - **PUT:** Store the value under the canonical key and mark that key as **MRU**. If this makes the number of stored entries exceed `capacity`, evict the **least-recently-used (LRU)** entry. - **HIT:** If the canonical key is **currently present**, mark it as **MRU**. If the key is **not present** during replay, **ignore** the record (no insertion, no error). ## Output Return the recovered cache contents ordered from **most-recently-used to least-recently-used**, as a list of `(canonical_key, value)` pairs, where `canonical_key` is the tuple described above. ## Edge cases - If `capacity` is `0`, no entry can ever be stored — return an empty list. - If `journal` is empty, return an empty list. ## Constraints - `0 <= capacity <= 100000` - `0 <= len(journal) <= 100000` - Each record's operation is either `'PUT'` or `'HIT'`. - All argument values and stored values are integers. - Records are already in durable journal order.