Implement a Versioned Recipe Manager

Question

Build an in-memory recipe service with unique names, search, users, and rollback.

```python
class RecipeManager:
    def add_recipe(self, recipe_id, name, ingredients) -> bool: ...
    def get_recipe(self, recipe_id) -> dict | None: ...
    def update_recipe(self, recipe_id, name, ingredients) -> bool: ...
    def delete_recipe(self, recipe_id) -> bool: ...
    def search_recipes(self, query) -> list[dict]: ...
    def get_all_recipes(self) -> list[dict]: ...
    def add_user(self, user_id, username) -> bool: ...
    def edit_recipe(self, user_id, recipe_id, name, ingredients) -> bool: ...
    def get_recipe_history(self, recipe_id) -> list[dict] | None: ...
    def rollback_recipe(self, user_id, recipe_id, version) -> bool: ...
```

Recipe IDs and names are unique; name comparison and search are case-insensitive while original casing is preserved. Returned recipes must be defensive copies. Search results sort by ingredient count and then recipe ID. Successful adds and edits append immutable, one-based versions.

IDs and names are nonempty strings; ingredients are lists of strings, preserving order and repetitions. Name uniqueness and substring search compare Python-style lowercase strings, without trimming or accent normalization. An empty search query matches every recipe. Both search and get_all_recipes use the same ordering: ingredient count ascending; then ASCII decimal IDs before other IDs, decimal IDs by integer value and original string as a tie-break, and other IDs lexicographically. For example, equal-sized recipes with IDs `01`, `1`, `a` appear in that order.

Current recipe output is `{"id": recipe_id, "name": name, "ingredients": [...]}`. History is oldest-first, with entries `{"version": integer, "name": name, "ingredients": [...]}` and no ID field. Reads and writes must not share mutable ingredient lists with callers or historical versions. Missing recipe reads/history return `None`; missing updates/deletes return `False`. Failed writes leave current state, name ownership and history unchanged.

Users are registered by unique user ID; duplicate registration returns `False`. Usernames need not be unique. Any registered user may edit or roll back any existing recipe; ownership permissions are not part of this interface. update_recipe is the non-user-scoped editing operation and also appends a version. Deletion removes the recipe and its history and releases its current name and ID for later reuse; a recreated recipe starts at version one. Historical names are not reserved. Every successful write, including an unchanged edit or rollback, creates a new version.

Each independent input case starts a new RecipeManager and contains `calls`, a list of the ten operation names followed by their declared positional arguments. Return one result per call in order. Rollback versions are integers; out-of-range versions return `False`.

Rollback appends a copy of the selected historical version as a new current version; it never truncates history. It must fail atomically if the historical name now belongs to another recipe.

## Suggested implementation approach

These milestones cover the complete required contract, not additional assessed stages.

1. Implement CRUD and name uniqueness.
2. Add deterministic search and listing.
3. Add users and authenticated edits.
4. Add immutable history and rollback.

## Design discussion

How would you extend this interface with ownership, permissions, concurrent edits and audit metadata? These extensions are not required by the current interface.