Design a Space-Efficient Versioned Recipe Shopping Cart

Problem Statement

You are building an in-memory shopping cart service for a recipe-based meal kit platform. Users add or remove full recipes from their cart. Each recipe specifies required ingredients and quantities. Multiple recipes often share common ingredients (e.g., "garlic", "chicken breast"). Bulk pricing discounts apply to the total aggregated quantity of an ingredient across all recipes currently in the cart.

Every successful modification creates a new sequential version version_id (starting at 0 for an empty cart). The cart must be space-efficient: duplicating the full cart state on every mutation will exhaust memory. Users can inspect any historical version's total cost, or check out an earlier version, which makes that version the active head and discards any later versions.

Implement the VersionedRecipeCart class with the following methods:

• __init__(ingredient_catalog: dict[str, dict]): Initializes the cart. ingredient_catalog maps ingredient_name to its pricing rules: {"base_price": float, "bulk_threshold": int, "bulk_price": float}. If the total quantity of ingredient_name across all recipes in the cart is >= bulk_threshold, every unit of that ingredient is charged at bulk_price; otherwise, each unit is charged at base_price.
• add_recipe(recipe_id: str, ingredients: dict[str, int]) -> int: Adds a recipe with its ingredient quantities. Fails and returns -1 if the recipe is already in the current version of the cart. On success, records a new version and returns the new version_id.
• remove_recipe(recipe_id: str) -> int: Removes a recipe from the current cart. Fails and returns -1 if the recipe does not exist in the current cart. On success, records a new version and returns the new version_id.
• get_total_cost(version_id: int | None = None) -> float: Calculates the total cost for the specified version_id. If version_id is None, evaluates the latest version. Raises ValueError if version_id is invalid.
• checkout(version_id: int) -> float: Checks out the cart at version_id. Discards all versions strictly greater than version_id, making version_id the current active version. Returns the total cost at that version. Raises ValueError if version_id does not exist.

Constraints

• 1 = 0
• Deep copying the entire cart state per mutation is not permitted.

Example

catalog = {
    "garlic": {"base_price": 1.0, "bulk_threshold": 5, "bulk_price": 0.6},
    "chicken": {"base_price": 8.0, "bulk_threshold": 2, "bulk_price": 7.0}
}
cart = VersionedRecipeCart(catalog)
# version 0: empty cart, cost = 0.0

v1 = cart.add_recipe("curry", {"garlic": 3, "chicken": 1})  # v1 = 1
# garlic: 3 * 1.0 = 3.0; chicken: 1 * 8.0 = 8.0; total = 11.0
cart.get_total_cost(v1) # returns 11.0

v2 = cart.add_recipe("roast", {"garlic": 3, "chicken": 1})  # v2 = 2
# garlic: 6 >= 5 -> 6 * 0.6 = 3.6; chicken: 2 >= 2 -> 2 * 7.0 = 14.0; total = 17.6
cart.get_total_cost()   # returns 17.6

# Checkout version 1 (discards version 2)
cost = cart.checkout(1) # returns 11.0

# Attempting to access version 2 now raises ValueError
# Current version is 1